从队列中获取O(1)时间的最小/最大值?

How can I retrieve the max and min element from a queue at any time in 0(1) time complexity? Earlier I was using Collections.max and min to find the elements but that would be 0(n).

如何在0(1)时间复杂度的任何时候从队列中检索max和min元素?之前我用的是集合。求元素的最大值和最小值，但那是0(n)

7 个解决方案

#1

You only have 2 ways to get O(1) for a min/max operation:

你只有两种方法可以让O(1)用于最小/最大运算:

• if the structure is sorted and you know where the max / min is located
• 如果结构被排序，并且你知道最大值/最小值在哪里
• if the structure is not sorted and only allows insertion: you can recalculate the min / max every time you insert an item and store the value separately
• 如果结构没有排序，只允许插入:每次插入一个项并分别存储值时，您可以重新计算最小/最大值。
• if the structure is not sorted and allows insertions and removals: I don't think you can do better than O(n), unless you use more than one collection (but that solution does not support removal of any elements, only head / tail elements, which should be the case with a queue).
• 如果结构没有排序并允许插入和删除:我认为您不能做得比O(n)更好，除非您使用多个集合(但是该解决方案不支持删除任何元素，只支持head / tail元素，这应该是队列的情况)。

#2

There exist such a structure that acts like a queue but lets you retrieve min/max value in constant time, actually not strictly constant, it is amortized constant time (named min/max queue as you could guess). There are two ways of implementing it - using two stacks or using a queue and a deque.

存在这样一种结构，它的作用类似于队列，但允许您在固定时间内检索min/max值，实际上不是严格的常量，它是平摊的常量时间(您可以猜到它的名称为min/max queue)。实现它有两种方法——使用两个堆栈或使用队列和deque。

Deque implementation looks more less like this (language agnostic):

Deque实现看起来不像这样(语言不可知):

so we have a deque of max elements, the one on the front is the desired max, and a standard queue.

所以我们有一个max元素的deque，前面的这个是期望的max，还有一个标准的队列。

Push operation

推动操作

1. If the queue is empty, just push the element on both, the queue and the deque.
2. 如果队列为空，只需在队列和deque上同时推元素。
3. If the queue is not empty, push the element on the queue, going from the back of the deque delete all elements that are strictly less than the one we are now pushing (they will surly not be the max, since the pushed element is larger and will last on the queue for longer) and push the current element on the back of the deque
4. 如果非空队列,队列的元素,从后面的双端队列删除所有元素严格小于一个我们现在推(他们会粗暴的不是最大,因为推元素大,将持续在队列上更长时间),推动当前元素的双端队列

Remove operation

删除操作

1. If the front of the deque is equal to the front of the queue then pop both (deque from the front)
2. 如果deque的前面等于队列的前面那么就同时弹出两个(deque从前面)
3. If the front of the deque is not equal to the front of the queue then pop just the queue, the poped element surely is not the largest one.
4. 如果deque的前面不等于队列的前面，那么只弹出队列，弹出的元素肯定不是最大的。

Get max

让马克斯

1. It is just the first element of the deque.
2. 它只是deque的第一个元素。

(lots of arguments should be added to make it clear why it works, but the second version presented below may be the answer to this necessity)

(为了弄清楚它为什么有效，应该添加很多论证，但是下面给出的第二个版本可能是这种必要性的答案)

The Stack implementation is quite similar, I think it may be a bit longer to implement but perhaps easier to grasp. The first thing to note is that it is easy to store the maximal element at the stack - easy exercise (for the lazy ones - Stack with find-min/find-max more efficient than O(n)?). The second part, perhaps a bit tricky if seen the first time, is that it is quite easy to implement a queue using two stacks, it can be found here - How to implement a queue using two stacks? . And that is basically it - if we can get the maximal element of both of the stacks we can get the maximal element of the whole queue (taking maximum is associative or something like that if you want a more formal argument, but I bet you don't, it is really obvious).

栈实现是非常相似的，我认为实现它可能需要更长的时间，但可能更容易掌握。首先要注意的是，在堆栈中存储最大元素很容易(对于懒惰的元素来说)，使用find-min/find-max进行堆栈比O(n)更有效吗?第二个部分(如果第一次看到的话，可能有点棘手)是，使用两个栈实现一个队列非常容易，可以在这里找到——如何使用两个栈实现一个队列?。基本上是这样——如果我们可以得到两个栈的最大元素我们可以得到整个队列的最大元素(以最大关联之类的,如果你想要一个更正式的论点,但是我敢打赌你不,真的很明显)。

The min versions is done analogically.

最小的版本是类似的。

Everything may also be done using a set (or something of it's kind) in O(nlogn) time but it is pointless as the constant in O(n) is really small and it should be much faster, yet easy to implement.

在O(nlogn)时间内，也可以使用集合(或类似的东西)来完成所有工作，但这是没有意义的，因为O(n)中的常量非常小，应该要快得多，而且易于实现。

NON-INTERESTING parts from the first version:

第一个版本的无趣部分:

Hope I helped a little bit. And hope that didn't say anything wrong. Can give a simple implementation in C++/C if required. Would be grateful for any feedback on the form as it is my first post of this type anywhere :) (and English is not my native language). Also some confirmation on the correctness would be great.

希望我能帮点忙。希望你没说错。如果需要，可以用c++ /C提供一个简单的实现。如果您对我的表格有任何反馈，我将不胜感激，因为这是我在任何地方发布的第一个此类的帖子:)(而且英语不是我的母语)。同样，对正确性的一些确认也是很好的。

EDIT: as this answer got me some points I felt obliged to clean it up a bit, also extending it a bit.

编辑:由于这个答案给了我一些观点，我觉得有必要把它清理一下，同时也扩展一下。

#3

Implement a queue in which push_rear(), pop_front() and get_min() are all constant time operations

实现一个队列，其中push_back()、pop_front()和get_min()都是常量时间操作。

#4

I would store two fields minIndex and maxIndex that will store index positions in your data structure for the minimum and maximum value respectively.

我将存储minIndex和maxIndex两个字段，它们将分别存储数据结构中最小值和最大值的索引位置。

When new elements are added to the queue, check for two things:

当向队列添加新元素时，检查以下两点:

1. The element is less than the current minimum element at the minIndex position; if so update the value of minIndex after insertion.
2. 该元素在minIndex位置小于当前最小元素;如果是，在插入之后更新minIndex的值。
3. The element is greater than the current maximum element at the maxIndex position and update the reference accordingly.
4. 元素大于maxIndex位置的当前最大元素，并相应地更新引用。

This will give you a O(1) asymptote for the current min and max value.

这将给你一个O(1)渐近线对于当前的最小值和最大值。

#5

This isn't really a queue, but you can implement Min-Max Heap.

这并不是一个真正的队列，但是您可以实现最小最大堆。

http://en.wikipedia.org/wiki/Min-max_heap

http://en.wikipedia.org/wiki/Min-max_heap

Basically, it's a heap which has it's max heap property at even levels, and min heap property at odd levels.

基本上，它是一个堆，它有偶数级的最大堆属性，奇数级的最小堆属性。

It has both O(1) MIN() and O(1) MAX() operations. However it's rather tricky to iterate, but it works and meets your requirements.

它同时具有O(1) MIN()和O(1) MAX()操作。然而，迭代是相当复杂的，但是它可以工作并满足您的需求。

#6

I am posting the complete code here to find MIN and MAX in queue in a constant time. Please feel free to contact me if you have any doubt.

我在这里发布完整的代码，以在一个恒定的时间内找到队列中的最小值和最大值。如果您有任何疑问，请随时与我联系。

Queue

队列

// Queue Interface
package com.java.util.collection.advance.datastructure.queue;
public interface Queue<E>{
    boolean addR(E e);
    E removeL();
    E element();
    E elementR();
    boolean isFull();
    boolean isEmpty();
    void trim();
}

Deque

双端队列

package com.java.util.collection.advance.datastructure.queue;
/**
* A deque is a double-ended queue. You can insert items at either end and delete them
* from either end. The methods might be called insertLeft() and insertRight(), and 
* removeLeft() and removeRight().
* @author vsinha
*
* @param <E>
*/
public interface DeQueue<E> extends Queue<E>{

    boolean addL(E element);

    E removeR();

}

FindMinMaxQueue

FindMinMaxQueue

package com.java.util.collection.advance.datastructure.queue;


@SuppressWarnings("hiding")
public interface FindMinMaxQueue<Integer> extends Queue<Integer>{

    public Integer min();

    public Integer max();
}

MyQueue

MyQueue

package com.java.util.collection.advance.datastructure.queue;

import java.util.Arrays;

public class MyQueue<E> implements Queue<E>,DeQueue<E>{

    protected int front = 0;
    protected int rear =-1;
    protected E[] elements =null;
    private static final int DEFAULT_INTIAL_CAPACITY =100; 
    private int size =0;

    public MyQueue(){
        this(DEFAULT_INTIAL_CAPACITY);
    }
    @SuppressWarnings("unchecked")
    public MyQueue(int intialCapacity){
        if(intialCapacity < 0){
            throw new IllegalArgumentException("intial capacity can't be null");
        }
        elements =(E[]) new Object[intialCapacity];
    }
    @Override
    public boolean addR(E e) {
        if(! isFull()) {
            elements[++rear] = e;
            size++;
            return true;
        }
        return false;
    }

    @Override
    public E removeL() {
        E element =null;
        if(!isEmpty()){
            element=elements[front];
            // Nullify the reference
            elements[front] =null;
            ++front;
            --size;
        }
        return element;
    }

    @Override
    public E element() {
        E element =null;
        if(!isEmpty()){
            element=elements[front];
        }
        return element;
    }

    @Override
    public E elementR() {
        E element =null;
        if(!isEmpty()){
            element=elements[rear];
        }
        return element;
    }

    public boolean isFull() {
        return rear == elements.length;
    }


    public boolean isEmpty() {
        return size == 0;
    }
    Override
    public String toString() {
        return "MyQueue [front=" + front + ", rear=" + rear + ", elements="
                + Arrays.toString(elements) + ", size=" + size + "]";
    }
    @Override
    public void trim() {
        @SuppressWarnings("unchecked")
        E[] dest =(E[]) new Object[size];
        System.arraycopy(elements, front, dest, 0, size);
        elements = dest;
        front =0;
        rear=size-1;
    }
    @Override
    public boolean addL(E element) {
        if(front != 0) {
            elements[--front] = element;
            size++;
            return true;
        }
        return false;
    }

    @Override
    public E removeR() {
        E element =null;
        if(size > 0) {
            element=elements[rear];
            // Nullify the reference
            elements[rear] =null;
            --rear;
            --size;
        }
        return element;
    }

}

MinAndMaxFinderQueue

MinAndMaxFinderQueue

package com.java.util.collection.advance.datastructure.queue;

public class MinAndMaxFinderQueue extends MyQueue<Integer> implements FindMinMaxQueue<Integer> {

    private Queue<Integer> maxValuesQueue =null;

    private Queue<Integer> minValuesQueue =null;


    public MinAndMaxFinderQueue (int intialCapacity){
        super(intialCapacity);
        maxValuesQueue =new MyQueue<Integer>(intialCapacity);
        minValuesQueue =new MyQueue<Integer>(intialCapacity);

    }
    @Override
    public boolean addR(Integer e) {
        if(super.addR(e)){
            if(max() == null || max() <= e){
                maxValuesQueue.addR(e);
            }

            if(min() == null || min() >= e){
                minValuesQueue.addR(e);
            }
            return true;
        }
        return false;
    }

    @Override
    public Integer removeL() {
        Integer element =super.removeL();
        if(element !=null){
            if(maxValuesQueue.element() == element){
                maxValuesQueue.removeL();
            }

            if(minValuesQueue.element() == element){
                minValuesQueue.removeL();
            }
        }
        //Need to re-generate MIN and MAX queue when the main queue is not empty and min/max queue is empty
        regenerateMin();
        regenerateMax();

        return element;
    }

    private void regenerateMin(){
        Integer current =null;
        if(!super.isEmpty() && min() ==null){
            for(int front = super.front; front<= super.rear;front++){
                current = (Integer)elements[front];
                if(min() == null || min() >= current){
                    minValuesQueue.addR(current);
                }

            }
        }
    }

    private void regenerateMax(){
        Integer current =null;
        if(!super.isEmpty() && max() ==null){
            for(int front = super.front; front<= super.rear;front++){
                current = (Integer)elements[front];
                if(max() == null || max() <= current){
                    maxValuesQueue.addR(current);
                }
            }
        }
    }
    public Integer min() {
        return minValuesQueue.elementR();
    }

    public Integer max() {
        return maxValuesQueue.elementR();
    }
    @Override
    public String toString() {
        return super.toString()+"\nMinAndMaxFinderQueue [maxValuesQueue=" + maxValuesQueue
                + ", minValuesQueue=" + minValuesQueue + "]";
    }



}

Test

测试

//Test class 
package com.java.util.collection.advance.datastructure.queue;

import java.util.Random;


public class MinMaxQueueFinderApp {

    public static void main(String[] args) {
        FindMinMaxQueue<Integer> queue =new MinAndMaxFinderQueue(10);
        Random random =new Random();
        for(int i =0; i< 10; i++){
            queue.addR(random.nextInt(100));
            System.out.println(queue);
            System.out.println("MAX :"+queue.max());
            System.out.println("MIN :"+queue.min());
        }
        System.out.println(queue);
        System.out.println("MAX :"+queue.max());
        System.out.println("MIN :"+queue.min());

        queue.removeL();
        System.out.println(queue);
        System.out.println("MAX :"+queue.max());
        System.out.println("MIN :"+queue.min());
        queue.removeL();
        System.out.println(queue);
        System.out.println("MAX :"+queue.max());
        System.out.println("MIN :"+queue.min());
        queue.removeL();
        System.out.println(queue);
        System.out.println("MAX :"+queue.max());
        System.out.println("MIN :"+queue.min());
        queue.removeL();
        System.out.println(queue);
        System.out.println("MAX :"+queue.max());
        System.out.println("MIN :"+queue.min());
        queue.removeL();
        System.out.println(queue);
        System.out.println("MAX :"+queue.max());
        System.out.println("MIN :"+queue.min());


        System.out.println(queue);
        System.out.println("MAX :"+queue.max());
        System.out.println("MIN :"+queue.min());
    }
}

#7

I suspect you are trying to implement what a PriorityQueue does. This is a sorted queue which O(log N) to get the lowest value. I not sure why you would want to largest value as a queue only has one end.

我怀疑您正在尝试实现PriorityQueue做的事情。这是一个O(log N)取最小值的排序队列。我不知道为什么您希望最大的值作为一个队列只有一个端点。