Java priority queues and heaps
A priority queue gives quick access to the item with the highest priority. Java's PriorityQueue is a binary min-heap: poll removes the smallest element in O(log n), and offer adds one in O(log n). Peeking at the smallest element is O(1). A heap is stored in an array, where the children of position i are at 2i + 1 and 2i + 2.
Java
import java.util.*;
class Main {
public static void main(String[] args) {
PriorityQueue<Integer> minHeap = new PriorityQueue<>();
for (int v : new int[] {5, 1, 8, 3, 9, 2}) {
minHeap.offer(v);
}
StringBuilder order = new StringBuilder();
while (!minHeap.isEmpty()) {
order.append(minHeap.poll()).append(' ');
}
System.out.println(order.toString().trim());
PriorityQueue<Integer> maxHeap = new PriorityQueue<>(Comparator.reverseOrder());
maxHeap.addAll(List.of(5, 1, 8, 3));
System.out.println("largest " + maxHeap.peek());
int k = 3;
PriorityQueue<Integer> top = new PriorityQueue<>();
for (int v : new int[] {7, 12, 3, 19, 5, 11, 2, 15}) {
top.offer(v);
if (top.size() > k) {
top.poll();
}
}
List<Integer> result = new ArrayList<>(top);
Collections.sort(result, Collections.reverseOrder());
System.out.println("top " + k + ": " + result);
}
}