Heap

Merge K Sorted Lists (H)

Min heap:

1. Push head of each non-empty list into heap

2. Pop smallest node, attach to result

3. Push popped node’s next into heap

   Repeat until heap empty

   Always extract current minimum

   O(N log k)

K Closest Points to Origin

Use heap on distance:

1. Compute distance x^2 + y^2

2. Keep min heap of all points, or size-k max heap

3. Extract k closest

   For size-k heap:

• Push point

• If heap size > k, pop farthest

  O(n log k)

Top K Frequent Elements

Count + heap:

1. Build frequency map

2. Push (freq, num) into heap

3. Keep size k min heap

4. Remaining elements are top k frequent

   Alternative: bucket sort

Find Median from Data Stream

Two heaps:

1. Max heap for smaller half

2. Min heap for larger half

3. Balance sizes so difference ≤ 1

4. Median:

   • odd: top of larger heap

   • even: average of both tops

     Keeps halves ordered

Kth Largest Element in a Stream

Min heap of size k:

1. Push each new number

2. If heap size > k, pop smallest

3. Heap top is kth largest

   Keeps only top k largest seen so far