java - 从队列中获取 O(1) 时间内的最小值/最大值？

Question

如何以 0(1) 的时间复杂度随时从队列中检索最大和最小元素？早些时候我使用 Collections.max 和 min 来查找元素，但那将是 0(n)。

Answer 1

存在这样一种结构，其行为类似于队列，但允许您在恒定时间内检索最小/最大值，实际上不是严格恒定的，它是摊销的恒定时间（您可以猜到命名为最小/最大队列）。有两种实现方式 - 使用两个堆栈或使用队列和双端队列。

双端队列的实现看起来不像这样（语言不可知）：

所以我们有一个最大元素的双端队列，前面的那个是所需的最大值，还有一个标准队列。

推送操作

1. 如果队列为空，只需将元素推送到队列和双端队列。
2. 如果队列不为空，则推入队列中的元素，从双端队列的后面删除所有严格小于我们现在推入的元素（它们肯定不是最大值，因为推入的元素更大并且将在队列中持续更长时间）并将当前元素推到双端队列的后面

删除操作

1. 如果双端队列的前端等于队列的前端，则两者都弹出（从前端的双端队列）
2. 如果双端队列的前端不等于队列的前端，则仅弹出队列，弹出的元素肯定不是最大的元素。

获得最大值

1. 它只是双端队列的第一个元素。

（应该添加很多论据以明确其工作原理，但下面介绍的第二个版本可能是这种必要性的答案）

Stack 的实现非常相似，我认为实现可能会更长一些，但可能更容易掌握。首先要注意的是，将最大元素存储在堆栈中很容易 - 容易练习（对于懒惰的人 -堆栈与 find-min/find-max 比 O(n) 更有效？）。第二部分，如果第一次看到可能有点棘手，是使用两个堆栈实现队列非常容易，可以在这里找到 -如何使用两个堆栈实现队列？. 基本上就是这样 - 如果我们可以获得两个堆栈的最大元素，我们可以获得整个队列的最大元素（如果你想要一个更正式的论点，取最大值是关联的或类似的东西，但我打赌你不't，这真的很明显）。

最小版本是类比完成的。

一切也可以在 O(nlogn) 时间内使用一个集合（或类似的东西）来完成，但这毫无意义，因为 O(n) 中的常数非常小，它应该更快，但易于实现。

第一个版本中不感兴趣的部分：

希望我能有所帮助。并希望这没有说错什么。如果需要，可以在 C++/C 中给出一个简单的实现。非常感谢您对表格的任何反馈，因为这是我在任何地方的第一篇此类帖子:)（而且英语不是我的母语）。对正确性的一些确认也会很棒。

编辑：由于这个答案让我得到了一些分数，我觉得有必要对其进行一些清理，同时也对其进行一些扩展。

Answer 2

对于最小/最大操作，您只有 2 种方法可以获得 O(1)：

• 如果结构已排序并且您知道最大值/最小值的位置
• 如果结构未排序且仅允许插入：您可以在每次插入项目时重新计算最小值/最大值并单独存储该值
• 如果结构未排序并允许插入和删除：我认为你不能比 O(n) 做得更好，除非你使用多个集合（但该解决方案不支持删除任何元素，只支持头/尾元素，队列应该是这种情况）。

Answer 3

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

Answer 4

我怀疑您正在尝试实现 PriorityQueue 的功能。这是一个排序队列，O(log N) 得到最低值。我不知道为什么你会想要最大值，因为队列只有一端。

Answer 5

这不是真正的队列，但您可以实现 Min-Max Heap。

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

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

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

Answer 6

我在这里发布了完整的代码，以便在恒定时间内在队列中找到 MIN 和 MAX。如果您有任何疑问，请随时与我联系。

队列

// 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();
}

双端队列

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();

}

查找最小最大队列

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


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

    public Integer min();

    public Integer max();
}

我的队列

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;
    }

}

MinAndMaxFinder 队列

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 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());
    }
}

Answer 7

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

当新元素添加到队列中时，检查两件事：

1. 该元素小于minIndex位置的当前最小元素；如果是这样，则在插入后更新minIndex的值。
2. 该元素大于maxIndex位置的当前最大元素，并相应地更新引用。

这将为您提供当前最小值和最大值的 O(1) 渐近线。