DSA

Part 10 — Heaps

A practical Python guide to heaps and priority queues for coding interviews, covering heap fundamentals, top-k problems, merging sorted streams, almost-sorted data, running medians, and heap-based algorithmic patterns.

Deepak Mishra20 min read

Heaps are one of the most useful data structures in coding interviews.

They are especially powerful when a problem repeatedly asks:

  • What is the smallest element?
  • What is the largest element?
  • What are the top k elements?
  • What is the next item with the highest priority?
  • How can I process a stream without storing everything?
  • How can I merge multiple sorted streams efficiently?

A heap is not a fully sorted data structure.

Instead, it maintains just enough ordering to make the minimum or maximum immediately available.

That limited ordering is precisely what makes heaps efficient.

1. What Part 10 Is Really Teaching

Don’t approach heaps as:

“I need to memorize several heap problems.”

Instead, learn the patterns:

                         HEAPS
                           |
          +----------------+----------------+
          |                |                |
          v                v                v
      Priority         Top-K           Streaming
      processing       problems         data
          |                |                |
          v                v                v
       min/max        k largest        median
       extraction     k smallest       online
          |
          v
     Merge sorted
        streams

The central idea is:

Use a heap when you repeatedly need access to the smallest or largest candidate while the rest of the ordering is not important.

The source material’s heap section covers merging sorted files, increasing-decreasing sequences, almost-sorted data, closest stars, online medians, extracting the largest elements from a heap, and implementing a stack using a heap. citeturn0search0turn0search1

2. Heap Fundamentals

A heap is a specialized complete binary tree.

There are two common forms.

Min-Heap

The smallest element is at the root.

          1
        /   \
       3     5
      / \   / \
     7   8 9  12

The heap property is:

parent <= children

Max-Heap

The largest element is at the root.

          12
        /    \
       9      10
      / \    /  \
     4   7  3    8

The heap property is:

parent >= children

A heap only guarantees the parent-child ordering.

It does not guarantee that the entire array is sorted.

3. Heap as an Array

One of the beautiful properties of a complete binary tree is that it can be represented compactly as an array.

For a node at index i:

left child  = 2*i + 1
right child = 2*i + 2
parent      = (i - 1) // 2

For example:

              10
            /    \
           7      9
          / \    / \
         4   6  2   8

can be represented as:

[10, 7, 9, 4, 6, 2, 8]

This is why heaps don’t require explicit tree-node objects in most implementations.

4. Core Heap Operations

For a heap containing n elements:

Operation Complexity
Peek min/max O(1)
Insert O(log n)
Remove min/max O(log n)
Build heap O(n)
Search arbitrary value O(n)

The last point is important.

A heap is not a general-purpose search structure.

If you need fast lookup of arbitrary values, a hash table or balanced search tree may be more appropriate.

5. Python’s heapq

Python provides a highly optimized heap implementation through:

import heapq

Python’s heapq is a min-heap.

Insert

heapq.heappush(heap, value)

Remove minimum

value = heapq.heappop(heap)

Inspect minimum

smallest = heap[0]

Example:

import heapq

heap = []

heapq.heappush(heap, 5)
heapq.heappush(heap, 2)
heapq.heappush(heap, 8)
heapq.heappush(heap, 1)

print(heap[0])          # 1
print(heapq.heappop(heap))  # 1

6. Simulating a Max-Heap in Python

Python’s heapq is a min-heap.

For numbers, a common technique is to store negative values:

import heapq

max_heap = []

heapq.heappush(max_heap, -10)
heapq.heappush(max_heap, -5)
heapq.heappush(max_heap, -20)

largest = -heapq.heappop(max_heap)

The stored values are:

[-20, -10, -5]

but the logical values are:

[20, 10, 5]

For custom objects, another option is to store tuples whose first field represents the desired priority.

7. The Most Important Heap Pattern: Top K

Suppose you have millions of numbers and only need the:

k largest

elements.

A naive solution:

sorted(values, reverse=True)[:k]

costs:

O(n log n)

But what if:

n = 10,000,000
k = 10

Sorting all ten million values is unnecessary.

We only need to remember the best ten candidates.

That leads to the top-k heap pattern.

8. Top K Largest Using a Min-Heap

To keep the k largest elements:

  1. Maintain a min-heap of size at most k.
  2. Insert each candidate.
  3. If the heap grows beyond k, remove the smallest.
  4. At the end, the heap contains the k largest elements.
import heapq

def k_largest(values, k):
    if k <= 0:
        return []

    heap = []

    for value in values:
        heapq.heappush(heap, value)

        if len(heap) > k:
            heapq.heappop(heap)

    return heap

Complexity

Time:  O(n log k)
Space: O(k)

Compare this with:

Full sorting:
O(n log n)

When:

k << n

the heap approach can be dramatically cheaper.

9. Why a Min-Heap for the K Largest?

This is one of the most common interview questions.

It may initially feel backward.

If we want the largest values, why use a min-heap?

Because we need to efficiently remove the weakest candidate.

Imagine:

k = 3

Current candidates:
100
90
80

If 95 arrives:

100
95
90

The value we want to evict is:

80

That is the minimum.

Therefore:

k largest → min-heap

Similarly:

k smallest → max-heap

This is a pattern worth memorizing.

10. Streaming Top K

The top-k technique becomes even more useful when the data is a stream.

Suppose values arrive one at a time:

x1, x2, x3, ...

You cannot store the entire input.

Maintain only:

k candidates

This changes the memory requirement from:

O(n)

to:

O(k)

The pattern is:

Incoming value
      |
      v
Compare with current candidates
      |
      v
Possibly insert
      |
      v
Evict weakest candidate

This is an important connection between heap algorithms and real streaming systems.

11. Staff-Level Optimization

Even the O(n log k) solution can sometimes be improved in practice.

Before inserting a new value, inspect the smallest candidate:

if len(heap) < k or value > heap[0]:
    heapq.heappush(heap, value)

    if len(heap) > k:
        heapq.heappop(heap)

If:

value <= heap[0]

the new value cannot enter the top k.

So we avoid unnecessary heap operations.

The asymptotic worst-case complexity remains:

O(n log k)

but the constant factors can improve substantially.

12. Problem Pattern — Merge K Sorted Streams

Suppose you have:

File A: 1, 5, 9
File B: 2, 4, 10
File C: 3, 6, 8

and want:

1, 2, 3, 4, 5, 6, 8, 9, 10

A naive approach concatenates everything and sorts:

O(n log n)

But the input already contains valuable structure:

Each individual stream is sorted.

We should exploit that.

13. K-Way Merge With a Heap

Maintain one candidate from each sorted stream.

Initially:

heap:
1 from A
2 from B
3 from C

The smallest is:

1

Output it.

Then take the next element from stream A:

5

Heap becomes:

2
3
5

Output:

2

Then add the next item from B:

4

Continue.

The heap contains at most k elements.

14. Python Implementation

import heapq

def merge_sorted_lists(lists):
    heap = []

    for list_index, values in enumerate(lists):
        if values:
            heapq.heappush(
                heap,
                (values[0], list_index, 0)
            )

    result = []

    while heap:
        value, list_index, element_index = heapq.heappop(heap)

        result.append(value)

        next_index = element_index + 1

        if next_index < len(lists[list_index]):
            next_value = lists[list_index][next_index]

            heapq.heappush(
                heap,
                (next_value, list_index, next_index)
            )

    return result

If there are n total elements across k lists:

Time:  O(n log k)
Space: O(k)

The crucial insight is:

Never keep more candidates in the heap than are necessary to determine the next output.

15. Why K-Way Merge Matters

This pattern appears in:

  • external sorting
  • log processing
  • distributed data systems
  • merge pipelines
  • time-series processing
  • search infrastructure
  • multi-source event streams

The interview problem is really testing whether you can recognize:

Multiple sorted sources
        ↓
One next-best candidate per source
        ↓
Heap
        ↓
Global sorted stream

This is a highly reusable Staff-level pattern.

16. Increasing-Decreasing Arrays

Suppose an array repeatedly alternates between increasing and decreasing runs:

1, 4, 7, 9, 6, 3, 5, 8, 10, 7

Instead of ignoring the structure and sorting everything, we can:

  1. split the array into monotonic runs
  2. reverse decreasing runs
  3. treat every run as sorted
  4. merge them with a heap

The overall pattern becomes:

Structured input
      ↓
Decompose
      ↓
Convert to sorted sequences
      ↓
K-way merge

If there are k sorted runs and n total elements:

Time: O(n log k)

This is another example of:

Exploit structure before applying a general-purpose algorithm.

17. Almost-Sorted Data

Consider:

3, -1, 2, 6, 4, 5, 8

Suppose every element is at most k positions away from its correct sorted position.

This is called an almost-sorted or nearly sorted sequence.

A full sort is unnecessary.

18. Why a Heap Works

Suppose:

k = 2

After reading the first:

k + 1 = 3

elements, the smallest one must be the next element in the final sorted output.

Therefore maintain a min-heap containing roughly:

k + 1

candidates.

Algorithm:

Read first k+1 values
        ↓
Build min-heap
        ↓
Read next value
        ↓
Push it
        ↓
Pop minimum
        ↓
Output minimum

Continue until the stream ends.

Complexity:

Time:  O(n log k)
Space: O(k)

This is especially useful for large streams where storing the complete input is undesirable.

19. Heap Pattern: Sliding Candidate Window

The almost-sorted problem demonstrates a more general concept:

When you know the answer must lie within a bounded candidate window, a heap can maintain that window efficiently.

This idea appears in:

  • delayed event ordering
  • streaming timestamps
  • approximate sorting
  • network packets arriving slightly out of order
  • distributed event processing

20. K Closest Points or Stars

Suppose you have millions of points and need the:

k closest

to the origin.

The distance of:

(x, y, z)

can be compared using squared distance:

distance_squared = x*x + y*y + z*z

There is no need to compute the square root because:

a < b

implies:

sqrt(a) < sqrt(b)

So we can compare squared distances directly.

21. K Closest Using a Max-Heap

We want to retain the k smallest distances.

Therefore we need to efficiently remove the largest candidate.

So use a max-heap.

Conceptually:

k smallest → max-heap
import heapq

def k_closest(points, k):
    heap = []

    for x, y in points:
        distance = x*x + y*y

        heapq.heappush(
            heap,
            (-distance, x, y)
        )

        if len(heap) > k:
            heapq.heappop(heap)

    return [
        (x, y)
        for _, x, y in heap
    ]

Complexity:

Time:  O(n log k)
Space: O(k)

Again, the heap contains only the candidates that still matter.

22. Running Median of a Data Stream

Now we encounter one of the most important heap patterns.

Suppose numbers arrive online:

5
2
10
3
8

After every insertion, we want the median.

Sorting the entire sequence after every insertion would be expensive.

We can instead maintain two heaps:

             DATA
              |
       +------+------+
       |             |
   max-heap        min-heap
   lower half      upper half

The max-heap stores the smaller half.

The min-heap stores the larger half.

23. The Two-Heap Invariant

Maintain:

size(lower) == size(upper)

or:

size(lower) = size(upper) + 1

Also maintain:

max(lower) <= min(upper)

Then:

Odd number of elements

The median is:

max(lower)

Even number of elements

The median is:

(max(lower) + min(upper)) / 2

This gives efficient online median calculation.

24. Python Implementation

import heapq

class RunningMedian:
    def __init__(self):
        self.lower = []  # max-heap using negative values
        self.upper = []  # min-heap

    def add(self, value):
        if not self.lower or value <= -self.lower[0]:
            heapq.heappush(self.lower, -value)
        else:
            heapq.heappush(self.upper, value)

        if len(self.lower) > len(self.upper) + 1:
            value = -heapq.heappop(self.lower)
            heapq.heappush(self.upper, value)

        elif len(self.upper) > len(self.lower):
            value = heapq.heappop(self.upper)
            heapq.heappush(self.lower, -value)

    def median(self):
        if len(self.lower) > len(self.upper):
            return float(-self.lower[0])

        return (
            -self.lower[0] + self.upper[0]
        ) / 2.0

For n inserted elements:

Insertion: O(log n)
Median:    O(1)
Total:     O(n log n)

Space:

O(n)

25. Why Two Heaps Work

Imagine:

1 2 3 4 5 6

Split them:

lower: 1 2 3
upper: 4 5 6

The median lies exactly between:

3 and 4

The heaps give us direct access to:

max(lower) = 3
min(upper) = 4

Therefore:

median = (3 + 4) / 2

This is a beautiful example of using two complementary priority structures to maintain a global statistic.

26. K Largest Elements in a Max-Heap

Suppose the input is already a max-heap.

You want the k largest values without destroying the original heap.

A naive approach performs repeated extraction.

But that modifies the heap.

A better approach exploits the heap’s structural property:

A child’s value can never exceed its parent’s value.

Therefore, when considering candidates, we only need to explore nodes whose values could still belong to the top k.

Maintain a secondary max-heap of candidate nodes.

Start with:

root

Extract the largest candidate.

Then insert its children.

Repeat k times.

This gives a complexity related to:

O(k log k)

rather than scanning the entire heap.

The exact implementation depends on the heap representation and whether the original structure must remain untouched.

27. Why Heap Structure Is Only Partial Ordering

A common misconception is:

“A heap is almost sorted.”

Not really.

A heap only guarantees:

parent <= children

for a min-heap.

It does not tell us how two nodes in different branches compare.

For example:

          1
        /   \
       4     2
      / \   / \
     9   7 5   8

The heap property holds.

But:

4

and:

2

have no direct ordering relationship beyond their relationship with the root.

This limited ordering is exactly why:

peek min/max → O(1)

while:

arbitrary search → O(n)

28. Heap vs Sorted Array

A useful interview comparison:

Requirement Heap Sorted Array
Get min/max O(1) O(1)
Insert O(log n) O(n)
Remove min/max O(log n) O(n) if preserving array
Arbitrary search O(n) O(log n)
Maintain dynamic priority order Excellent Poor

Use a heap when the workload is dominated by:

insert
+
extract best

Use a sorted structure when you need broader ordering or search capabilities.

29. Heap vs Stack vs Queue

The three structures answer different questions.

Stack

Who arrived last?
LIFO

Queue

Who arrived first?
FIFO

Heap

Who currently has the highest priority?
Priority-based ordering

This is the conceptual progression:

STACK
  ↓
arrival order, reversed

QUEUE
  ↓
arrival order

HEAP
  ↓
priority order

Recognizing this distinction is more important than memorizing implementation details.

30. The Most Important Heap Patterns

Pattern 1 — Top K

k largest
    ↓
min-heap of size k
k smallest
    ↓
max-heap of size k

Complexity:

O(n log k)

Pattern 2 — K-Way Merge

Multiple sorted sources
        ↓
One candidate per source
        ↓
Heap
        ↓
Next smallest

Complexity:

O(n log k)

Pattern 3 — Almost-Sorted Data

Maximum displacement = k
        ↓
Maintain k+1 candidates
        ↓
Min-heap

Complexity:

O(n log k)

Pattern 4 — Running Median

Lower half → max-heap
Upper half → min-heap

Invariant:

max(lower) <= min(upper)

and sizes differ by at most one.

Pattern 5 — Candidate Pruning

When only the best k candidates matter:

new candidate
      ↓
could it enter top k?
      ↓
NO → discard
YES → heap

This is the essence of memory-efficient streaming algorithms.

31. Heap Complexity Cheat Sheet

Problem Pattern Time Extra Space
Top k largest Min-heap O(n log k) O(k)
Top k smallest Max-heap O(n log k) O(k)
Merge k sorted streams Min-heap O(n log k) O(k)
Almost-sorted sequence Min-heap O(n log k) O(k)
k closest points Max-heap O(n log k) O(k)
Running median Two heaps O(log n) per item O(n)
Heap insertion Heap O(log n) O(1) auxiliary
Heap extraction Heap O(log n) O(1) auxiliary
Peek Heap O(1) O(1)

32. Common Heap Interview Mistakes

Mistake 1 — Choosing the Wrong Heap

Remember:

K largest → min-heap
K smallest → max-heap

because the heap should expose the candidate you need to evict.

Mistake 2 — Sorting Everything

If:

k << n

ask:

Do I really need to sort all n elements?

Often:

O(n log n)

can become:

O(n log k)

Mistake 3 — Forgetting the Streaming Constraint

If the problem says:

“The sequence is presented as a stream.”

Don’t automatically load the entire dataset.

Ask:

What is the minimum state required?

A heap often reduces memory from:

O(n)

to:

O(k)

Mistake 4 — Assuming Heap Means Sorted

A heap is partially ordered.

Don’t use it when you need arbitrary ordered traversal or binary-search-style lookup.

Mistake 5 — Ignoring Tuple Ordering in Python

Python’s heapq compares tuples lexicographically.

For example:

heapq.heappush(heap, (priority, item_id, item))

means:

  1. compare priority
  2. if tied, compare item_id
  3. then compare item

This is extremely useful when heap entries contain multiple pieces of state.

33. Heap as a Streaming Architecture Pattern

One of the strongest lessons from this part is the connection between heaps and streaming systems.

Imagine:

                 EVENTS
                    |
          +---------+---------+
          |         |         |
        source1   source2   source3
          |         |         |
          +---------+---------+
                    |
                 HEAP
                    |
             next best event
                    |
                    v
                OUTPUT

The heap acts as a small stateful frontier.

It stores only the candidates necessary to determine the next output.

This pattern is useful in:

  • distributed log processing
  • event-time ordering
  • external sorting
  • multi-source ingestion
  • search ranking
  • task scheduling

34. Staff-Level Mental Model

A junior engineer may see:

“Find the 10 largest values.”

and immediately think:

sort()

A Staff engineer should ask:

n = ?
k = ?
Do I need all values sorted?
Is the data streaming?
Can I discard candidates?
What is the memory constraint?

If:

n = 10 million
k = 10

then:

full sort
O(n log n)

is probably unnecessary.

Instead:

min-heap of size 10

gives:

O(n log 10)

and:

O(10)

additional storage.

The deeper lesson is:

Don’t compute information that the problem never asks for.

35. The Heap Decision Tree

When you encounter a new problem:

Do I repeatedly need the smallest/largest item?
             |
            YES
             |
             v
           HEAP
             |
      +------+------+
      |             |
      v             v
   One best       Top K
      |             |
      v             v
  min/max       bounded heap

If multiple sources are already sorted:

K sorted streams
       ↓
   K-way merge
       ↓
      HEAP

If the data is streaming:

Streaming
    ↓
Can I retain only candidates?
    ↓
Top K / median / priority
    ↓
Heap

36. What to Practice Until It Becomes Automatic

You should be able to implement and explain:

✓ Min-heap operations
✓ Max-heap simulation in Python
✓ Top K largest
✓ Top K smallest
✓ K-way merge
✓ Merge sorted streams
✓ Sort almost-sorted data
✓ K closest points
✓ Running median
✓ K largest elements from a heap

But more importantly, you should recognize the pattern behind each one.

37. Final Interview Cheat Sheet

Need the smallest item repeatedly?

MIN-HEAP

Need the largest item repeatedly?

MAX-HEAP

Need K largest?

MIN-HEAP of size K

Need K smallest?

MAX-HEAP of size K

Need K closest?

MAX-HEAP of size K

Have K sorted streams?

MIN-HEAP

Data is almost sorted by at most K positions?

MIN-HEAP of size K+1

Need online median?

MAX-HEAP for lower half
+
MIN-HEAP for upper half

Need priority-based processing?

HEAP / PRIORITY QUEUE

38. The Bigger Lesson From Part 10

Heaps teach a powerful algorithmic principle:

Maintain only the information necessary to make the next decision.

A full sort maintains:

complete ordering

A heap maintains:

just enough ordering

A top-k heap maintains:

only the best k candidates

A k-way merge heap maintains:

one frontier candidate per source

A two-heap median structure maintains:

the boundary between two halves

That is why heaps are so powerful.

They deliberately throw away ordering information you don’t need.

Final Takeaway

When you see a coding problem involving:

minimum
maximum
priority
top K
streaming
multiple sorted sequences
almost-sorted data
running median

pause before reaching for sort().

Ask:

Can I maintain a small set of candidates in a heap and avoid computing the full ordering?

If the answer is yes, you may have just transformed:

O(n log n)

into:

O(n log k)

or reduced memory from:

O(n)

to:

O(k)

That is the core skill Part 10 is designed to build.

Don’t sort everything.
Don’t store everything.
Maintain only what the next decision requires.

Part 10 in the Series

Part 7 — Linked Lists
↓
Part 8 — Stacks & Queues
↓
Part 9 — Binary Trees
↓
Part 10 — Heaps
↓
Part 11 — Searching

The progression is deliberate:

Linked Lists
     ↓
Pointer manipulation

Stacks & Queues
     ↓
Ordering and controlled state

Binary Trees
     ↓
Hierarchy and recursive structure

Heaps
     ↓
Priority and candidate selection

Searching
     ↓
Efficient retrieval from ordered structure

The goal is not to memorize isolated solutions.

The goal is to recognize the data structure that eliminates the work.