CODEWITHSUNDEEP
javadata-structures
Kaihua Hou
Kaihua Hou

Reputation: 368

Finding the min/max element of a priority queue using ranked array

If I would like to implement a data structure that can allow me to efficiently identify the min/max of a PriorityQueue, will it work if I implement the PriorityQueue using a circular ranked array representation so that the min and max elements are at the opposite ends of the array? Why or why not? Thanks in advance!

Upvotes: 1

Views: 1169

Answers (1)

the Hutt
the Hutt

Reputation: 18398

You can extend PriorityQueue and update max value in add, offer, and poll methods.
Something like below code. Improve/fix the code as per your needs.

public class Test {

    public static void main(String[] args) {
        MyPQ<Integer> pq = new MyPQ<>();
        pq.offer(3);
        pq.offer(44);
        pq.offer(1);
        pq.offer(10);
        System.out.println("Max:" + pq.getMax() + " Min:" + pq.getMin());
        System.out.println(pq.poll());
        System.out.println(pq.poll());
        System.out.println(pq.poll());
        System.out.println(pq.poll());
        System.out.println("Max:" + pq.getMax() + " Min:" + pq.getMin());
    }
}

class MyPQ<E extends Comparable<E>> extends PriorityQueue<E>{
    private E max;
    private void setMax(E e) {
        if(max == null)
            max = e;
        else if(e.compareTo(max) > 0) {
            max = e;
        }
    }
    public E getMax() {
        return max;
    }
    
    public E getMin() {
        return super.peek();
    }
    @Override
    public boolean offer(E e) {
        setMax(e);
        return super.offer(e);
    }
    
    @Override
    public boolean add(E e) {
        setMax(e);
        return super.add(e);
    }
    @Override
    public E poll() {
        E min = super.poll();
        if(min.equals(max))
            max=null;
        return min;
    }
}

Output:

Max:44 Min:1
1
3
10
44
Max:null Min:null

Upvotes: 1

Related Questions