Day 81: Heaps & Priority Queues
Today I dove into Heaps, one of the most efficient data structures for priority-based tasks. A heap is a complete binary tree that satisfies the heap property — either max-heap or min-heap.
What is a Heap?
Min-Heap: The value of each node is less than or equal to the values of its children.
Max-Heap: The value of each node is greater than or equal to the values of its children.
Stored typically as an array for space efficiency and ease of access to parent/child nodes.
Applications of Heaps
Priority Queues
Dijkstra’s Algorithm
Median in a Data Stream
Top K Frequent Elements
Heap Sort
Java Implementation Using PriorityQueue (Min-Heap by default)
java
import java.util.*;
public class HeapExample {
public static void main(String[] args) {
// Min-Heap
PriorityQueue<Integer> minHeap = new PriorityQueue<>();
minHeap.add(5);
minHeap.add(1);
minHeap.add(10);
minHeap.add(3);
while (!minHeap.isEmpty()) {
System.out.print(minHeap.poll() + " ");
}
// Output: 1 3 5 10
}
}
Custom Max-Heap Using Comparator
java
PriorityQueue maxHeap = new PriorityQueue<>(Collections.reverseOrder());
maxHeap.add(5);
maxHeap.add(1);
maxHeap.add(10);
maxHeap.add(3);
while (!maxHeap.isEmpty()) {
System.out.print(maxHeap.poll() + " ");
}
// Output: 10 5 3 1
Key Takeaways
PriorityQueue in Java uses a binary heap under the hood.
For max-heap behavior, use a custom comparator or Collections.reverseOrder().
Time complexities:
Insertion: O(log n)
Deletion (poll): O(log n)
Peek (top element): O(1)