The JDK's implementation is java.util.PriorityQueue. It use a heap in the background. The add and poll time cost is O(NlogN), the size and isEmpty time cost is O(1). The space complexity is O(N).
Code:
import java.util.PriorityQueue;
public class test {
public static void main(String...args) {
PriorityQueue<Integer> pq = new PriorityQueue<>(5);
pq.add(1);
pq.add(5);
pq.add(10);
while(!pq.isEmpty()) {
System.out.println(pq.poll());
}
}
}
The most important methods for heap is swim and sink. Here is class that achieves priority queue with swim and sink functions.
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());
}
}
}
