Heap / Priority Queue

A heap is a complete binary tree that satisfies the heap property:

Min-Heap: Parent is always smaller than or equal to children. Root is the minimum.

Max-Heap: Parent is always larger than or equal to children. Root is the maximum.

Heaps are typically stored as arrays:

• •Parent of node at index i: (i-1)/2
• •Left child: 2i + 1
• •Right child: 2i + 2

Key operations:

• •Insert (push): O(log n) - add at end, bubble up
• •Extract min/max (pop): O(log n) - remove root, bubble down
• •Peek: O(1) - just return root

In Java, PriorityQueue is a min-heap by default. For max-heap, use Collections.reverseOrder() or negate values.

To find the K largest elements, use a MIN-heap of size K. This seems backwards, but here's why it works:

1. •Keep a min-heap with at most K elements
2. •For each new number:
   • If heap has less than K elements, add it
   • Else if number > heap's minimum, remove min and add number
3. •The heap always contains the K largest seen so far
4. •The root (minimum of heap) is the Kth largest overall

Why min-heap? Because we want to efficiently remove the smallest of the K candidates. The smallest of the K largest is the Kth largest.

Similarly, for K smallest elements, use a MAX-heap of size K.

A common variation: find the K most frequent elements. This combines frequency counting with the Top K pattern.

Approach 1: Heap (O(n log k))

1. •Count frequencies with a HashMap
2. •Use a min-heap of size K, ordered by frequency
3. •The heap contains the K most frequent elements

Approach 2: Bucket Sort (O(n))

1. •Count frequencies
2. •Create buckets where bucket[i] contains elements appearing i times
3. •Scan buckets from highest to lowest, collect K elements

Bucket sort is theoretically faster but uses more space. In interviews, both approaches are valid.

The median is the middle value when data is sorted. For a stream of numbers, we need to find the median efficiently after each insertion.

The key insight: split numbers into two halves using two heaps:

small (max-heap): Contains the smaller half. Root is the largest of the small numbers. large (min-heap): Contains the larger half. Root is the smallest of the large numbers.

Invariants:

• •All elements in small <= all elements in large
• •Size difference is at most 1
• •small.size >= large.size (small has the extra element if odd count)

Finding median:

• •If sizes equal: median = (small.root + large.root) / 2
• •If small has more: median = small.root

Adding a number:

1. •Add to small (max-heap)
2. •Move largest of small to large (rebalance)
3. •If large has more elements, move smallest of large back to small

Given K sorted linked lists, merge them into one sorted list. This is a classic heap problem.

Naive approach: Merge two at a time. O(Nk) where N is total elements.

Heap approach: O(N log k)

1. •Create a min-heap with the first node from each list
2. •Pop the smallest node, add it to result
3. •If that node has a next, push it to the heap
4. •Repeat until heap is empty

The heap always has at most K elements (one from each list), so operations are O(log k).

This pattern applies to any 'merge K sorted sequences' problem:

• •Merge K sorted arrays
• •Find smallest range covering elements from K lists
• •External sorting (merge sorted file chunks)

Given tasks with cooldown period n (same task must have n intervals between executions), find minimum time to complete all tasks.

This is a heap + greedy problem:

1. •Count frequency of each task
2. •Use a max-heap to always execute the most frequent available task
3. •Track tasks in cooldown in a queue with their ready time
4. •Each cycle: pop from heap, execute, add to cooldown queue if count > 0
5. •When cooldown expires, move task back to heap

Greedy insight: Always execute the most frequent task that's available. This minimizes idle time because frequent tasks are the bottleneck.

Alternative formula: If maxFreq is the highest frequency and maxCount is how many tasks have that frequency: result = max(tasks.length, (maxFreq - 1) * (n + 1) + maxCount)

Problem: Find K points closest to origin (0,0).

Approach: Use a MAX-heap of size K to keep the K smallest distances.

Why max-heap? Same logic as K largest, but inverted:

• •We want K smallest, so use max-heap
• •If new distance < heap's max, replace it
• •Root is the Kth smallest (furthest of the K closest)

Key insight: Don't need sqrt for distance comparison. Compare squared distances directly.

Example: points = [[1,3],[-2,2]], K = 1

Problem: Given meeting times, find minimum number of meeting rooms required.

Key Insight: A room becomes free when a meeting ends. Track end times in a min-heap.

Algorithm:

1. •Sort meetings by start time
2. •Min-heap stores end times of ongoing meetings
3. •For each meeting:
   • If it starts after earliest ending meeting, reuse that room (pop)
   • Add current meeting's end time to heap
4. •Heap size = number of concurrent meetings = rooms needed

Example: [[0,30],[5,10],[15,20]]

Problem: Rearrange string so no two adjacent characters are the same. Return "" if impossible.

Greedy + Heap: Always place the most frequent character that's different from the last placed.

Algorithm:

1. •Count frequencies
2. •Max-heap ordered by frequency
3. •Each step: pop most frequent, append to result, hold it for next iteration
4. •Re-add previous character (if count > 0) to heap
5. •If heap empty but we have a held char with count > 0, impossible

Example: "aab"

Impossible check: If maxFreq > (n+1)/2, impossible (pigeonhole principle).

Problem: Start with capital W, complete at most k projects. Each project needs capital to start and gives profit. Maximize final capital.

Greedy: Always pick the project with maximum profit among affordable ones.

Two Heaps Solution:

1. •Min-heap: projects sorted by required capital (to find affordable ones)
2. •Max-heap: affordable projects sorted by profit (to pick best)

Algorithm:

1. •Add all projects to min-heap by capital
2. •For k iterations:
   • Move all affordable projects (capital <= W) to max-heap
   • Pick project with max profit, add profit to W
   • If no affordable project exists, stop

Example: k=2, W=0, profits=[1,2,3], capital=[0,1,1]

Problem: Find median for each sliding window of size k.

Challenge: Two Heaps work for streaming, but we also need to REMOVE elements as window slides.

Approach: Two heaps with lazy deletion.

Lazy Deletion:

1. •When element should be removed, mark it (add to hash map of "to delete")
2. •Before popping from heap, check if top should be deleted
3. •If yes, pop and decrement "to delete" count, repeat
4. •Only balance heaps after cleaning tops

Why lazy? Removing from middle of heap is O(n). Lazy deletion keeps it O(log n) per operation.

Balance Rule: After each operation, ensure |small.size - large.size| <= 1.

Edge Cases to Handle:

1. Empty Heap Operations

2. K larger than array size

3. Single element

4. All elements same

5. Negative numbers

Common Mistakes:

Quick reference for heap problems:

Decision Framework:

Heap Operation Complexity:

Problem-Specific Complexity:

Why O(n log k) is Better Than O(n log n):

JavaScript Caveat: Using array.sort() for heap operations is O(n log n) per operation, not O(log n). For interviews, explain you'd use a proper heap implementation in production.

Top K Template:

Two Heaps Median Template:

Merge K Sorted Template:

Interview Tips:

• •State heap type explicitly (min vs max)
• •For K problems, explain the counter-intuitive choice
• •Draw the heap structure when debugging
• •In JS, acknowledge sort() inefficiency
• •Handle empty heap cases