DSA: Heaps and Priority Queues

Learn heap properties, array representation, heap sort, and classic heap algorithms like median in a stream and merging K sorted arrays.

Heap Property

A heap is a complete binary tree stored as an array. In a max-heap every parent is greater than or equal to its children; in a min-heap every parent is less than or equal to its children. The root always holds the extreme value.

`Min-Heap vs Max-Heap`

The heap property applies at every node, not just the root. This guarantees O(1) access to the minimum (min-heap) or maximum (max-heap).

Max-heap: parent >= children, root is the maximum element
Min-heap: parent <= children, root is the minimum element
A heap is always a complete binary tree (all levels full except possibly the last, filled left to right)
Siblings have no ordering relationship with each other

Operation	Time Complexity
peek (get min/max)	O(1)
insert	O(log n)
extract min/max	O(log n)
build heap from array	O(n)
heap sort	O(n log n)
delete arbitrary element	O(log n)

Heap Representation (Array-Based)

A heap does not need explicit pointers. Given a node at index i (0-indexed), its left child is at 2i+1, right child at 2i+2, and parent at (i-1)/2.

`Index Arithmetic`

The complete binary tree property ensures that all nodes fill the array contiguously with no gaps, making pointer-free storage possible.

Parent of i: (i - 1) / 2
Left child of i: 2*i + 1
Right child of i: 2*i + 2
Leaves occupy indices n/2 to n-1 (they have no children)

Min-Heap Insert with Sift-Up

C++

After appending to the array, sift the new element up by swapping with its parent until the heap property is restored.

Heapify and Building a Heap

Heapify (sift-down) fixes the heap property at a given node by pushing it down until it is smaller than its children. Building a heap from an unsorted array runs heapify on all non-leaf nodes bottom-up in O(n).

`Build Heap in O(n)`

Start heapify from the last non-leaf node (index n/2 - 1) down to the root. This is more efficient than inserting n elements one by one at O(n log n).

Last non-leaf is at index n/2 - 1 (0-indexed)
Run heapify on indices from n/2-1 down to 0
Each heapify call sifts the node down until the subtree satisfies the heap property
Total work across all heapify calls sums to O(n) due to shorter sift paths near the leaves

Build Max-Heap in O(n)

C++

Heapify runs bottom-up on all n/2 non-leaf nodes. Deeper nodes do less work, which gives the O(n) total.

Heap Sort

Heap sort builds a max-heap in O(n), then repeatedly extracts the maximum by swapping the root with the last element and heapifying the reduced heap. The result is a sorted array in-place.

`Heap Sort Algorithm`

Phase 1: build max-heap in O(n). Phase 2: extract max n times, each taking O(log n), giving O(n log n) total.

Step 1: buildHeap, O(n)
Step 2: swap arr[0] with arr[n-1], then heapify the first n-1 elements
Repeat step 2 shrinking the heap by 1 each time
In-place, O(1) extra space. Not stable (equal elements may swap relative order).

Heap Sort

C++

After building the max-heap, each swap places the current maximum at the end. Heapify on the shrinking heap restores order.

Priority Queue Using Heap

C++ provides std::priority_queue as a max-heap by default. A min-heap is created with greater<int> as the comparator.

`std::priority_queue`

priority_queue wraps a heap with push, pop, and top in O(log n), O(log n), and O(1) respectively.

Max-heap (default): priority_queue<int> pq
Min-heap: priority_queue<int, vector<int>, greater<int>> pq
top() returns the current max (or min) in O(1)
push() and pop() both take O(log n)

Max-Heap and Min-Heap with std::priority_queue

C++

Extracting all elements from a min-heap in order gives sorted output, which is conceptually heap sort.

K Largest and K Smallest Elements

To find K largest elements, maintain a min-heap of size K. If a new element is larger than the heap top, replace the top and heapify. At the end the heap contains the K largest. For K smallest, use a max-heap symmetrically.

`Fixed-Size Heap Trick`

A min-heap of size K is the smallest maximum seen so far. Any element larger than the top displaces it, keeping only the K largest.

Push first K elements into the min-heap
For each remaining element: if element > top, pop top and push element
After full traversal, the heap holds exactly the K largest elements
Time: O(n log K), Space: O(K)

K Largest Elements with Min-Heap

C++

Keeping the heap at size K ensures only the K largest survive. Any newcomer larger than the current minimum evicts it.

Merge K Sorted Arrays

Merge K sorted arrays into one sorted array by using a min-heap that tracks the current front element of each array. Always extract the global minimum, then push the next element from the same array.

`K-Way Merge with Min-Heap`

The heap stores tuples of (value, array index, element index). At each step, the heap top is the globally smallest remaining element.

Initialize: push the first element of each array as (val, arrayIdx, elemIdx)
Extract the minimum (heap top), append to result
Push the next element from the same array (if any) to replace it
Time: O(n log K) where n is the total number of elements across all arrays

Merge K Sorted Arrays in O(n log K)

C++

The heap always holds exactly one element per array, so its size never exceeds K. Each extraction and insertion is O(log K).

Median in a Running Stream

Maintain two heaps: a max-heap for the lower half of numbers and a min-heap for the upper half. The median is the top of the larger heap, or the average of both tops when sizes are equal.

`Two-Heap Median Strategy`

Keep both heaps balanced so their size difference is at most 1. The median is always available in O(1) from the heap tops.

lowerHalf: max-heap, holds the smaller half of seen numbers
upperHalf: min-heap, holds the larger half of seen numbers
After each insert, rebalance: transfer one element if sizes differ by more than 1
Median: if sizes equal, average of both tops; otherwise top of the larger heap

Running Median with Two Heaps

C++

lower (max-heap) and upper (min-heap) stay balanced within 1 element. Median is O(1) from their tops.

Top K Frequent Elements

Count element frequencies with a hash map, then use a min-heap of size K to track the K highest frequencies. The heap evicts the least frequent element whenever it grows beyond K.

`Frequency Map + Min-Heap`

A min-heap ordered by frequency keeps only the K most frequent elements. Time: O(n log K), far better than sorting all frequencies at O(n log n).

Step 1: build frequency map in O(n)
Step 2: push (freq, element) pairs into a min-heap ordered by frequency
Evict when heap size exceeds K, evicted element has the lowest frequency so far
Heap top is the least frequent among the top K at all times

Top K Frequent Elements

C++

Frequency map counts occurrences. Min-heap of size K retains only the K highest-frequency elements across all unique values.

Kth Largest Element in a Stream

Maintain a min-heap of exactly K elements. The top of the heap is always the Kth largest element seen so far. Each new element either has no effect (if smaller than the top) or displaces the current Kth largest.

`Min-Heap of Size K for Kth Largest`

The heap top is the smallest of the K largest elements, which by definition is the Kth largest. Each add operation is O(log K).

If heap size is less than K, push the element directly
Otherwise: if element > top, pop top and push element
If element <= top, it is smaller than all K current leaders, ignore it
top() always returns the Kth largest in O(1)

Kth Largest in Streaming Data

C++

The min-heap top is the weakest of the K leaders. Any stronger newcomer evicts it and claims a spot.

Knowledge Check

1. In a max-heap stored as an array, the children of node at index i are at:

2. Building a heap from an unsorted array using heapify takes:

3. What is the time complexity of extracting the minimum from a min-heap of n elements?

4. To find the median of a running stream efficiently, you maintain:

5. Merging K sorted arrays using a min-heap takes:

6. Heap sort is not stable because:

7. The Kth largest element in a stream can be maintained using:

8. In a 0-indexed array representation of a heap, the parent of node i is at:

Previous Next