DataslopeHeaps and Priority Queues
Learn binary heaps, heapify, heap sort, priority_queue, and heap-based problem patterns in C++
A binary heap is a complete binary tree stored in an array. A max-heap keeps every parent greater than or equal to its children. A min-heap keeps every parent less than or equal to its children.
Conceptual tree and array storage
For index i, children are 2*i + 1 and 2*i + 2. The parent is (i - 1) / 2.
Push: sift up
Insert at the end to preserve completeness, then swap upward until the heap property is restored.
Pop: sift down
Remove the root by moving the last value to index 0, then swapping down with the larger child.
push and pop take O(log n), because they move along the height of the tree. top is O(1), because the best value is at index 0.
Bottom-up heapify
Building a heap by repeatedly pushing is O(n log n). Bottom-up heapify runs sift-down from the last internal node to the root and takes O(n).
for i from parent(last_index) down to 0:
siftDown(i)Heap sort
Heap sort builds a max-heap, then repeatedly swaps the root with the end and shrinks the heap.
std::priority_queue
The standard priority queue is a max-heap by default. Use std::greater<int> to make a min-heap.
Applications
Heaps appear whenever you need the next best item quickly.
- Top-k elements: keep a min-heap of size k.
- Streaming median: use a max-heap for the lower half and a min-heap for the upper half.
- Dijkstra preview: repeatedly extract the unvisited node with smallest tentative distance.
Heap is not a sorted array
A heap only guarantees that the top element has highest priority. Siblings and cousins are not globally sorted.
Practice: Kth largest element
Implement int kthLargest(std::vector<int> nums, int k) using a min-heap of size k.
Practice: Merge K sorted lists
Merge K sorted vectors into one sorted vector. The driver prints one merged value per line.
Practice: Last stone weight
Repeatedly take the two largest stones. If they differ, push their difference back. Return the final stone weight or 0.
Check your understanding
What is the time complexity of pushing into a binary heap?
O(1) always
O(log n)
O(n)
O(n log n)
When might a heap be preferred over a BST?
When you only need repeated access to the minimum or maximum item.
When you need sorted iteration over all keys at all times.
When you need fast search for any arbitrary value.
When duplicate values are impossible.
What is the default behavior of std::priority_queue<int>?
It is a min-heap.
It is a max-heap.
It keeps all values sorted in ascending iteration.
It removes elements in insertion order.