Chapter 9: Heaps & Priority Queues

Week 9

Master heap data structures and priority queues for efficient element retrieval. Learn heap operations, Python's heapq module, and solve classic interview problems including k closest points, merging sorted lists, kth largest element, string reorganization, and running median.

Topics: 6
Demos: 6
Min read: 25

Chapter Overview

A heap is a specialized tree-based data structure that satisfies the heap property: in a min-heap, every parent is smaller than or equal to its children; in a max-heap, every parent is larger than or equal to its children. This guarantees the minimum (or maximum) element is always at the root, accessible in $O(1)$ time.

Heaps power priority queues --- abstract data structures where the highest-priority element is always served first, regardless of insertion order. Operations like push and pop run in $O(\log n)$ time, making heaps ideal for problems that repeatedly ask for the smallest or largest element from a dynamic collection.

This chapter covers:

Heap Fundamentals: How heaps work internally, heapify, and Python's heapq
K Closest Points: Using a heap to find the k nearest points to the origin
Merge K Sorted Lists: Efficiently merging multiple sorted sequences with a heap
Kth Largest Element: Maintaining a min-heap of size k for streaming data
Reorganize String: Greedy character placement using a max-heap
Find Median from Data Stream: The elegant two-heap technique for running median

Chapter Roadmap

Click any topic to jump in

Interactive demo

Heap Fundamentals

Complete binary tree with the heap property — $O(\log n)$ push/pop via sift-up and sift-down.

Min-Heap and Max-Heap StructureHeapify and Python heapq

Top-k and k-way problems

Bounded-size heaps

K Closest Points

Find the $k$ nearest neighbors to the origin — max-heap of size $k$ keeps it $O(n \log k)$.

Min-Heap ApproachMax-Heap of Size K

Merge K Sorted Lists

K-way merge with a min-heap — always pop the smallest next element across all lists.

K-Way Merge with Min-HeapHandling Ties and Custom Comparisons

Running statistics

Kth Largest Element

Maintain a running min-heap of size $k$ — the root is always the answer.

Min-Heap of Size KStreaming Kth Largest (KthLargest Class)

Greedy scheduling with heaps

Reorganize String

Greedy max-heap on character counts — interleave the most frequent letters to avoid adjacency.

Greedy with Max-HeapTwo-Character Alternation Pattern

Two-heap architectures

Median from Stream

Two heaps split the data in half — $O(\log n)$ insert, $O(1)$ median query.

Two-Heap ArchitectureRebalancing Strategy

Topics

6 topics in this chapter

An emergency room does not treat patients in arrival order. It treats the most urgent case first, and new patients keep arriving while others are being seen. An operating system scheduler, a router's packet queue, and an event-driven simulation all make the same demand: insert items at any time, and repeatedly remove the one with the highest priority. A sorted array makes removal cheap but costs $O(n)$ shifts per insertion; an unsorted list makes insertion cheap but every removal scans all $n$ items.

The previous chapter, Advanced Graphs, already relied on this structure: Dijkstra's and Prim's algorithms pulled the closest unsettled vertex from a min-heap without looking inside it. A binary heap balances the two costs. It keeps only a partial order, every parent no larger than its children, which is enough to put the minimum at the root while making both insertion and removal $O(\log n)$ . Because the tree is complete, it fits in a plain array with index arithmetic instead of pointers.

We first build the array layout and the sift-up and sift-down operations. Then we see why heapify runs in linear time and how Python's heapq module exposes all of it.

Definition

A binary heap is a complete binary tree stored in an array, where the node at index $i$ has children at $2i+1$ and $2i+2$ . In a min-heap every parent is less than or equal to its children, so the minimum sits at index 0. Push and pop take $O(\log n)$ time, peek takes $O(1)$ , and heapify builds a heap from $n$ items in $O(n)$ .

In this topic

1Min-Heap and Max-Heap Structure
2Heapify and Python heapq

1 of 2

Min-Heap and Max-Heap Structure

A min-heap ensures that every parent node is less than or equal to its children. The smallest element sits at the root (index 0). A max-heap is the reverse --- every parent is greater than or equal to its children, so the largest element is at the root.

Since a heap is a complete binary tree stored as an array, the parent-child relationships follow simple index formulas:

Parent of node at index $i$ : $\lfloor (i - 1) / 2 \rfloor$
Left child: $2i + 1$
Right child: $2i + 2$

Push (insert): Add to the end, then sift up by swapping with the parent until the heap property is restored --- $O(\log n)$ . Pop (extract min/max): Swap root with the last element, remove it, then sift down by swapping with the smaller (min-heap) or larger (max-heap) child --- $O(\log n)$ . Peek: Return the root --- $O(1)$ .

Mathematical Intuition

A binary heap is a complete binary tree where every parent satisfies the heap property: in a min-heap, $\text{parent} \leq \text{children}$ ; in a max-heap, $\text{parent} \geq \text{children}$ . Stored as an array, the children of index $i$ are at $2i+1$ and $2i+2$ , and the parent is at $\lfloor (i-1)/2 \rfloor$ . Completeness means height is $O(\log n)$ , so insert (bubble up) and extract-root (sift down) are both $O(\log n)$ . Peek at the root is $O(1)$ . A heap of $n$ elements uses exactly $O(n)$ space with no pointers.

Example:

Insert elements [5, 3, 8, 1, 4] into a min-heap one by one. Show the heap state after each insertion.

2 of 2

Heapify and Python heapq

Heapify converts an arbitrary list into a valid heap in $O(n)$ time --- faster than inserting elements one by one ( $O(n \log n)$ ). The algorithm starts from the last non-leaf node and sifts down each node. Because most nodes are near the bottom (where sift-down is cheap), the total work is linear.

Python's heapq module provides a min-heap API:

heapq.heappush(heap, val) --- push a value, $O(\log n)$
heapq.heappop(heap) --- pop the smallest, $O(\log n)$
heapq.heapify(lst) --- convert list to heap in-place, $O(n)$
heapq.heappushpop(heap, val) --- push then pop, optimized to $O(\log n)$
heapq.nsmallest(k, iterable) and heapq.nlargest(k, iterable) --- find k extreme values

For a max-heap in Python, negate values before pushing and negate again after popping.

Mathematical Intuition

Python's heapq module implements a min-heap on a regular list. heapq.heapify(arr) converts an arbitrary list into a heap in $O(n)$ — not $O(n \log n)$ — by sifting down from the last non-leaf upward; the proof uses a telescoping sum $\sum_{h=0}^{\log n} (n / 2^{h+1}) \cdot h = O(n)$ . For a max-heap, negate values (heappush(heap, -x)). heappush and heappop are $O(\log n)$ ; heapq.nlargest(k, arr) uses a size- $k$ heap for $O(n \log k)$ total.

Example:

Given the list [9, 4, 7, 1, 3, 6], show the result of heapify and demonstrate push/pop.

Papers

Williams, J. W. J. — Algorithm 232: Heapsort (1964, Communications of the ACM)Floyd, R. W. — Algorithm 245: Treesort 3 (1964, Communications of the ACM)

Blogs

Binary Heap — GeeksforGeeks Heap (Priority Queue) — NeetCode

Definition

K Closest Points to Origin asks for the $k$ points of a list with the smallest distance $\sqrt{x^2 + y^2}$ to the origin, returned in any order. Ranking by the squared distance $x^2 + y^2$ gives the same result. Heapify-and-pop runs in $O(n + k \log n)$ time; a size- $k$ max-heap runs in $O(n \log k)$ time and $O(k)$ space.

In this topic

1Min-Heap Approach
2Max-Heap of Size K

1 of 2

Min-Heap Approach

The straightforward approach pushes all $n$ points into a min-heap keyed by squared distance, then pops $k$ times to get the $k$ closest.

Time complexity: $O(n \log n)$ for $n$ pushes, plus $O(k \log n)$ for $k$ pops. Space complexity: $O(n)$ for the heap.

Alternatively, heapify the list in $O(n)$ , then pop $k$ times for $O(n + k \log n)$ . When $k$ is small relative to $n$ , this is nearly linear.

Mathematical Intuition

The straightforward solution puts all $n$ points in a min-heap keyed by squared distance from origin, then pops $k$ times. Building the heap is $O(n)$ via heapify, and popping $k$ times costs $O(k \log n)$ . Total time: $O(n + k \log n)$ . This is wasteful when $k \ll n$ because we're maintaining full state for points we will never return. Still optimal when $k = \Theta(n)$ .

Example:

Find the 2 closest points to the origin from: [(3,3), (1,1), (-2,2), (5,1)]. Use squared distances.

2 of 2

Max-Heap of Size K

A more space-efficient approach maintains a max-heap of size $k$ . The max-heap tracks the $k$ closest points seen so far, with the farthest of the $k$ at the root.

For each new point:

If the heap has fewer than $k$ elements, push it.
If the new point is closer than the root (farthest of the current $k$ ), pop the root and push the new point.

Time complexity: $O(n \log k)$ --- each of $n$ elements does at most one push/pop on a heap of size $k$ . Space complexity: $O(k)$ .

Since Python's heapq is a min-heap, simulate a max-heap by negating distances.

Mathematical Intuition

A smarter approach maintains a max-heap of size exactly $k$ containing the $k$ closest points seen so far. For each new point, if it is closer than the max (the root), replace the root with the new point ( $O(\log k)$ ). Total time: $O(n \log k)$ , which beats $O(n + k \log n)$ when $k$ is small. Space is $O(k)$ instead of $O(n)$ . In Python, negate distances to simulate a max-heap with heapq. This pattern generalizes to all 'top-k' problems.

Example:

Use a max-heap of size 2 to find the 2 closest points from [(3,3), (1,1), (-2,2), (5,1)].

Papers

Bentley, J. L. — Multidimensional Binary Search Trees Used for Associative Searching (1975, Communications of the ACM)Hoare, C. A. R. — Algorithm 65: Find (1961, Communications of the ACM)

Blogs

K Closest Points to Origin — LeetCode Editorial K Closest Points to Origin — NeetCode

Definition

Merge K Sorted Lists combines $k$ individually sorted sequences with $N$ elements in total into one sorted sequence. A k-way merge keeps a min-heap holding the current head of each non-empty list; each step pops the smallest head, outputs it, and pushes the next element of that list. It runs in $O(N \log k)$ time with $O(k)$ extra space.

In this topic

1K-Way Merge with Min-Heap
2Handling Ties and Custom Comparisons

1 of 2

K-Way Merge with Min-Heap

The algorithm maintains a min-heap of size $k$ , where each entry contains the current smallest element from one of the $k$ lists along with an identifier for which list it came from.

Steps:

Push the first element from each of the $k$ lists into the heap (with list index and element index).
Pop the minimum element from the heap and add it to the result.
If that list has more elements, push the next element from the same list.
Repeat until the heap is empty.

Time: $O(N \log k)$ where $N$ is the total element count across all lists. Space: $O(k)$ for the heap (ignoring the output).

Mathematical Intuition

To merge $k$ sorted lists with $n$ total elements, use a min-heap of size $\leq k$ containing the current head of each list. Initialize with the first element from each list ( $O(k)$ heapify). Repeatedly pop the minimum, append to output, and push the next element from the same list ( $O(\log k)$ per element). Total time: $O(n \log k)$ , space: $O(k)$ . Compare to merging lists pairwise (merging list $i$ into the accumulator), which is $O(nk)$ — strictly worse for $k > \log k$ .

Example:

Merge three sorted lists: [1, 4, 7], [2, 5, 8], [3, 6, 9] using a min-heap.

2 of 2

Handling Ties and Custom Comparisons

When two elements from different lists have the same value, Python's heapq will try to compare the next item in the tuple. If the next item is not comparable (e.g., a list node), this raises a TypeError.

Solution: Include a unique tiebreaker (like a counter or list index) as the second element of the tuple:

(value, tiebreaker_index, list_id)

This guarantees a total ordering. The tiebreaker does not affect correctness --- it only ensures the heap can resolve equal values without comparing incomparable objects.

This pattern is essential in Python because heapq does not support custom comparator functions like Java's PriorityQueue.

Mathematical Intuition

Python's heapq orders by the full tuple comparison, so when two keys tie, it falls through to the next element. If that element is a list node (not comparable), you get a TypeError. The standard fix is to include a unique tie-breaker: push tuples (key, counter, node) where counter is a monotonically increasing integer. This guarantees the tuple comparison never reaches the uncomparable node. Tie-breaking does not affect asymptotic complexity — only a small constant per push.

Example:

Merge [[1, 3, 3], [1, 2, 4]] using a heap. Show how to handle the duplicate value 1.

Papers

Vitter, J. S. — External Memory Algorithms and Data Structures: Dealing with Massive Data (2001, ACM Computing Surveys)

Blogs

Merge K Sorted Lists — LeetCode Editorial Merge K Sorted Arrays — GeeksforGeeks

Definition

The $k$ th largest element of a collection of $n$ values is the value at position $k$ when the collection is sorted in descending order, counting duplicates. A min-heap holding the $k$ largest values seen so far keeps it at the root, giving $O(n \log k)$ time and $O(k)$ space, with $O(\log k)$ per update on a stream.

In this topic

1Min-Heap of Size K
2Streaming Kth Largest (KthLargest Class)

1 of 2

Min-Heap of Size K

To find the $k$ th largest element, maintain a min-heap of exactly $k$ elements. After processing all elements, the root of the heap is the $k$ th largest.

Algorithm:

Push the first $k$ elements into a min-heap.
For each remaining element: if it is larger than the heap root, replace the root (pop + push, or use heapreplace).
After all elements are processed, the root is the $k$ th largest.

Why min-heap, not max-heap? The min-heap lets us efficiently check and remove the smallest of our top- $k$ candidates. If we used a max-heap, we would need to track the minimum of the $k$ elements, which is $O(k)$ .

Time: $O(n \log k)$ . Space: $O(k)$ .

Mathematical Intuition

To find the $k$ -th largest in an array, maintain a min-heap of size $k$ containing the $k$ largest values seen so far. For each new value: if heap size $< k$ , push; else if the value exceeds the root, replace the root. The root is always the $k$ -th largest. Total time: $O(n \log k)$ , space: $O(k)$ . Quickselect achieves $O(n)$ average but $O(n^2)$ worst case; the heap approach offers a guaranteed $O(n \log k)$ worst case, which is preferred when latency matters.

Example:

Find the 3rd largest element in [7, 2, 9, 1, 5, 8, 3] using a min-heap of size 3.

2 of 2

Streaming Kth Largest (KthLargest Class)

The heap-of-size- $k$ approach naturally extends to a streaming scenario where elements arrive continuously. The LeetCode problem "Kth Largest Element in a Stream" asks you to design a class that:

Initializes with $k$ and an initial set of numbers.
Has an add(val) method that returns the $k$ th largest after adding val.

The class maintains a min-heap of size $k$ . On each add:

If the heap has fewer than $k$ elements, push val.
Else if val > root, replace the root.
Return the root (the $k$ th largest).

Each add call is $O(\log k)$ , making this highly efficient for long streams.

Mathematical Intuition

For an online setting where elements arrive one at a time, maintain a min-heap of size exactly $k$ . Each add(val) pushes $\text{val}$ and, if size exceeds $k$ , pops the minimum — $O(\log k)$ amortized. The current $k$ -th largest is always the root, retrievable in $O(1)$ . For $n$ adds, total time is $O(n \log k)$ . The heap only ever stores the top- $k$ candidates, using $O(k)$ space regardless of how many elements have streamed through.

Example:

Design a KthLargest stream with k=3, initial = [4, 5, 8, 2]. Then add: 3, 5, 10, 9, 4.

Papers

Hoare, C. A. R. — Algorithm 65: Find (1961, Communications of the ACM)Blum, M., Floyd, R. W., Pratt, V., Rivest, R. L. & Tarjan, R. E. — Time Bounds for Selection (1973, Journal of Computer and System Sciences)

Blogs

Kth Largest Element in an Array — LeetCode Editorial Kth Largest Element in a Stream — NeetCode

Definition

Reorganize String asks for a permutation of a string $s$ of length $n$ in which no two adjacent characters are equal, or an empty string if none exists. A valid arrangement exists if and only if no character occurs more than $\lceil n/2 \rceil$ times. The max-heap greedy builds one in $O(n \log A)$ time for an alphabet of size $A$ .

In this topic

1Greedy with Max-Heap
2Two-Character Alternation Pattern

1 of 2

Greedy with Max-Heap

The algorithm uses a max-heap (priority queue) sorted by character frequency:

Count character frequencies.
Push all characters with their (negated) counts into a max-heap.
At each step, pop the most frequent character, add it to the result.
Before pushing it back (with decremented count), pop and place the next most frequent. Then push the first character back.

Alternatively, at each step pop the top, append it, hold it aside, pop the next top, append, push back the held character, and so on.

Impossibility check: If any character appears more than $\lceil n/2 \rceil$ times, rearrangement is impossible. With $n$ slots, the most any character can occupy without adjacency conflicts is every other slot.

Time: $O(n \log A)$ where $A$ is the alphabet size (at most 26). Space: $O(A)$ for the heap.

Mathematical Intuition

To reorganize a string so no two adjacent characters are equal, greedily place the most-frequent unused character each step. Use a max-heap keyed by count. This fails iff some character's count exceeds $\lceil n/2 \rceil$ , because it cannot be separated by other characters. Each step pops the heap, appends the character, decrements its count, and temporarily holds it until the next step (to prevent repeating). Total time: $O(n \log |\Sigma|)$ where $|\Sigma|$ is the alphabet size (26 for lowercase letters, so effectively $O(n)$ ).

Example:

Reorganize the string "aaabbc" so no two adjacent characters are the same.

2 of 2

Two-Character Alternation Pattern

A simpler approach that avoids a heap works specifically for the "reorganize string" problem:

Sort characters by frequency (descending).
Fill even indices (0, 2, 4, ...) first with the most frequent characters.
Then fill odd indices (1, 3, 5, ...) with the remaining characters.

This works because placing the most frequent character at even positions guarantees no two adjacent characters are the same --- adjacent characters come from different index groups.

Time: $O(n)$ (using counting sort since we have at most 26 characters). Space: $O(n)$ for the result array.

Both approaches are valid. The heap approach generalizes better --- for instance, to problems where the gap between same characters must be $k$ instead of 1.

Mathematical Intuition

After the greedy placement, the resulting string has adjacent characters alternating. The mathematical condition for feasibility is $\max_c \text{count}(c) \leq \lceil n/2 \rceil$ : if any character appears more than half the time, the pigeonhole principle forces two copies into adjacent slots. A variation uses a buffer slot to hold the previously used character until it can be re-pushed — guaranteeing the second-most-frequent is used between consecutive uses of the most-frequent.

Example:

Reorganize "aabbcc" using the index-fill approach.

Blogs

Reorganize String — LeetCode Editorial Rearrange Characters So No Two Adjacent Are Same — GeeksforGeeks

A monitoring dashboard shows the median response time of a service, updated with every request, because the median resists the few extreme outliers that distort an average. The numbers arrive one at a time without end, and the current median must be available after each arrival. Re-sorting on every query costs $O(n \log n)$ , and even inserting into a sorted array costs $O(n)$ per arrival for the shifting.

The previous topic, Reorganize String, used a single max-heap to drive a greedy choice. Find Median from Data Stream needs two heaps working together. The median depends only on the one or two values in the middle, so the data can be split into a lower half and an upper half. A max-heap holds the lower half and exposes its largest value; a min-heap holds the upper half and exposes its smallest. If every lower value is at most every upper value and the sizes differ by at most one, the median sits at the heap roots. Each insertion costs $O(\log n)$ and each query $O(1)$ .

We first set up the two-heap architecture and its invariants. Then we derive a fixed rebalancing protocol that keeps both invariants true after every insertion.

Definition

Find Median from Data Stream maintains a growing multiset of numbers under two operations: addNum inserts a value, and findMedian returns the middle value, or the mean of the two middle values when the count is even. A max-heap for the lower half and a min-heap for the upper half, with sizes differing by at most one, give $O(\log n)$ inserts and $O(1)$ queries.

In this topic

1Two-Heap Architecture
2Rebalancing Strategy

1 of 2

Two-Heap Architecture

Split the data into two halves:

max_heap (left half): stores the smaller half of numbers. The largest of the small half is at the root.
min_heap (right half): stores the larger half of numbers. The smallest of the large half is at the root.

Invariants:

Every element in max_heap $\leq$ every element in min_heap.
The heaps are balanced: their sizes differ by at most 1.

Adding a number:

Push to max_heap (negate for Python).
Move max_heap's root to min_heap (ensures invariant 1).
If min_heap is larger, move its root back to max_heap (ensures invariant 2).

Finding the median:

If heaps are equal size: average of both roots.
If max_heap is larger: max_heap root.

Time: $O(\log n)$ per add, $O(1)$ per findMedian. Space: $O(n)$ total.

Mathematical Intuition

Maintain a max-heap lo for the lower half and a min-heap hi for the upper half, with the invariant $|\text{lo}| \in \{|\text{hi}|, |\text{hi}| + 1\}$ . On insert, push to lo then move lo's max to hi; if $|\text{hi}| > |\text{lo}|$ , move hi's min back to lo. The median is lo.top() (odd $n$ ) or $(\text{lo.top()} + \text{hi.top()}) / 2$ (even $n$ ). Insert is $O(\log n)$ , median query is $O(1)$ . Space is $O(n)$ .

Example:

Add numbers 5, 2, 8, 1, 9 one at a time. Show the median after each addition.

2 of 2

Rebalancing Strategy

The rebalancing after each insertion follows a fixed 3-step protocol that guarantees both invariants:

def addNum(num):
    heappush(max_heap, -num)           # Step 1: add to left half
    heappush(min_heap, -heappop(max_heap))  # Step 2: move max of left to right
    if len(min_heap) > len(max_heap):       # Step 3: rebalance sizes
        heappush(max_heap, -heappop(min_heap))

Why this works:

Step 2 ensures the largest element in the left half moves right, maintaining the ordering invariant.
Step 3 ensures the left half is never smaller than the right, so the median is always accessible.

This protocol handles all edge cases: first element, equal values, negative numbers, already-sorted input, reverse-sorted input. Each step is a single heap operation, so the total is exactly 3 or 5 heap operations per insertion.

Mathematical Intuition

The two heaps must maintain balance after every insert. The cleanest invariant is: always push to lo first, then pop-and-move to hi; if hi becomes larger than lo, pop-and-move back to lo. This guarantees $|\text{lo}| - |\text{hi}| \in \{0, 1\}$ at all times. Each rebalance is $O(\log n)$ — at most 2 pushes and 2 pops per insert. The constant factor is small, but rebalancing every step is the price of $O(1)$ median queries. Approximate online medians (e.g., Greenwald-Khanna quantile sketches) can be faster but give only $\varepsilon$ -approximations.

Example:

Trace the heap states when adding [3, 1, 4, 1, 5] and show the median after each step.

Papers

Munro, J. I. & Paterson, M. S. — Selection and Sorting with Limited Storage (1980, Theoretical Computer Science)Greenwald, M. & Khanna, S. — Space-Efficient Online Computation of Quantile Summaries (2001, ACM SIGMOD)

Blogs

Find Median From Data Stream — LeetCode Editorial Median in a Stream of Integers — GeeksforGeeks

Heap Fundamentals

K Closest Points

Merge K Sorted Lists

Kth Largest Element

Reorganize String

Median from Stream

6 topics in this chapter

Heap Fundamentals

Definition

In this topic

Min-Heap and Max-Heap Structure

Heapify and Python heapq

Related Problems on PixelBank

K Closest Points to Origin

Definition

In this topic

Min-Heap Approach

Max-Heap of Size K

Related Problems on PixelBank

Merge K Sorted Lists

Definition

In this topic

K-Way Merge with Min-Heap

Handling Ties and Custom Comparisons

Related Problems on PixelBank

Kth Largest Element

Definition

In this topic

Min-Heap of Size K

Streaming Kth Largest (KthLargest Class)

Related Problems on PixelBank

Reorganize String

Definition

In this topic

Greedy with Max-Heap

Two-Character Alternation Pattern

Find Median from Data Stream

Definition

In this topic

Two-Heap Architecture

Rebalancing Strategy

Related Problems on PixelBank