Heaps (Priority Queues)
Heaps & Priority Queues
A Heap is a specialized tree-based data structure that satisfies the heap property. It is a powerful tool for efficiently retrieving the minimum or maximum element from a collection. For this reason, it's the classic way to implement a Priority Queue.
Heap Property
A heap is a complete binary tree, which means all levels are filled except possibly the last one, which is filled from left to right. The key property depends on its type:
- Max-Heap: The value of any node is greater than or equal to the values of its children. This means the root is the largest element.
- Min-Heap: The value of any node is less than or equal to the values of its children. This means the root is the smallest element.
Array-Based Representation
Although a heap is a tree, it's typically implemented using an array or vector. Because it's a complete binary tree, there are no "gaps" in the array. This allows for easy calculation of parent and child indices for a node at index i (0-indexed):
- Parent:
floor((i-1)/2) - Left Child:
2*i + 1 - Right Child:
2*i + 2
Core Operations
Operations rely on restoring the heap property via "bubbling" or "sifting".
1. Insertion (push):
Add the new element to the end of the array. Then, "bubble up" by repeatedly comparing it with its parent and swapping if the heap property is violated, until the root is reached or the property is satisfied.
- Complexity: O(log n)
2. Deletion (pop):
The element to be removed is always the root. Replace the root with the last element in the array and shorten the array. Then, "bubble down" the new root by repeatedly comparing it with its children and swapping with the appropriate child (smaller for min-heap, larger for max-heap) until the heap property is restored.
- Complexity: O(log n)
3. Peek (top):
Simply return the root element without modifying the heap.
- Complexity: O(1)
Applications
In competitive programming, you'll almost always use the standard library's priority queue (which is implemented with a heap).
- Dijkstra's Algorithm: A priority queue efficiently stores vertices to visit next.
- Heapsort: A fast and efficient sorting algorithm with O(n log n) time complexity.
- Finding the Kth largest/smallest element: A min-heap of size K can find the Kth largest element in a stream of numbers in O(n log k) time.
Interactive Min-Heap
Visualize heap operations like insertion (bubble-up) and extraction (bubble-down).
Heap is empty. Insert an element to start.
Click a button to start.