Week 9

Chapter 9: Heaps & Priority Queues

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.

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

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

A binary heap is a complete binary tree stored as an array. The heap property ensures that the root always holds the extreme value --- the minimum in a min-heap or the maximum in a max-heap. Because the tree is complete, we can map parent-child relationships to array indices without using pointers.

Python's heapq module provides a min-heap implementation built on top of a regular list. Understanding how heaps work internally --- heapify up on insertion, heapify down on extraction --- is essential for solving priority queue problems efficiently. The $O(\log n)$ push and pop operations make heaps dramatically faster than sorting after every insertion.

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.

Blogs

Binary Heap — GeeksforGeeks Heap (Priority Queue) — NeetCode

Advanced Graphs

Dynamic Programming Basics

Chapter 9: Heaps & Priority Queues

Chapter Overview

Chapter Roadmap

Heap Fundamentals

K Closest Points

Merge K Sorted Lists

Kth Largest Element

Reorganize String

Median from Stream

Heap Fundamentals

In this topic

Min-Heap and Max-Heap Structure

Heapify and Python heapq

K Closest Points to Origin

Merge K Sorted Lists

Kth Largest Element

Reorganize String

Find Median from Data Stream