Write a priority queue data structure. The supported methods are isEmpty(), add(E e), delMax(), size(). Call add to add elements, call delMax() to get the largest value and delete it from the priority queue.
Solution:
In the following class, the time complexity of isEmpty, size is O(1), the time complexity for add and delMax is O(NlogN). The space complexity is O(N).
public class MyPriorityQueue<Item extends Comparable<Item>> {
private Item[] pq;
private int N = 0;
public MyPriorityQueue(int maxN) {
pq = (Item[])new Comparable[maxN + 1];
}
public boolean isEmpty() {
return N == 0;
}
public int size() {
return N;
}
public void add(Item item) {
pq[++N] = item;
swim(N);
}
public Item delMax() {
Item max = pq[1];
exch(N--, 1);
pq[N + 1] = null;
sink(1);
return max;
}
private void sink(int k) {
while(2*k <= N) {
int j = k*2;
if(j < N && less(pq[j], pq[j+1])) j++;
if(!less(pq[k], pq[j])) break;
exch(j, k);
k = j;
}
}
private void swim(int k) {
while(k > 1 && less(pq[k/2], pq[k])) {
exch(k, k/2);
k = k/2;
}
}
private boolean less(Item a, Item b) {
return (a.compareTo(b)) < 0;
}
private void exch(int i, int j) {
Item temp = pq[i];
pq[i] = pq[j];
pq[j] = temp;
}
public static void main(String...args) {
MyPriorityQueue<Integer> pque = new MyPriorityQueue<>(5);
pque.add(30);
pque.add(2);
pque.add(10);
System.out.println("size: " + pque.size());
while(!pque.isEmpty()) {
System.out.println(pque.delMax());
}
}
}
