Priority Queue Basics
A priority queue is a queue where each element has a priority. Elements are dequeued based on their priority (highest priority first) rather than FIFO order. In Java, `PriorityQueue` implements a min-heap by default.
Priority queues are used in Dijkstra's algorithm, Huffman coding, and task scheduling.
Java PriorityQueue example
// Min-heap (smallest element has highest priority)
PriorityQueue pq = new PriorityQueue<>();
pq.offer(5);
pq.offer(1);
pq.offer(3);
System.out.println(pq.poll()); // 1 (smallest)
System.out.println(pq.poll()); // 3
// Max-heap using custom comparator
PriorityQueue maxHeap = new PriorityQueue<>((a,b) -> b - a);
maxHeap.offer(5);
maxHeap.offer(1);
maxHeap.offer(3);
System.out.println(maxHeap.poll()); // 5 (largest)
For custom objects, implement `Comparable` or provide a `Comparator`.
Two Minute Drill
- Priority queue serves elements based on priority (min/max heap).
- Java's `PriorityQueue` is a min-heap (smallest element has highest priority).
- Use comparator for max-heap or custom ordering.
- Core operations: offer() (add), poll() (remove head), peek().
- O(log n) time for insertion and removal.
Need more clarification?
Drop us an email at career@quipoinfotech.com