Get Min/Max in O(1) time from a Queue?

Question

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).

Answer 1

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.

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

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

Push operation

1. If the queue is empty, just push the element on both, the queue and the deque.
2. 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

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. 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.

Get max

1. It is just the first element of the 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).

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.

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.

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

Answer 2

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

• 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).

Answer 3

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

Answer 4

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.

Answer 5

This isn't really a queue, but you can implement 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.

Answer 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

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


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

    public Integer min();

    public Integer max();
}

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

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

Answer 7

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

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. The element is greater than the current maximum element at the maxIndex position and update the reference accordingly.

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