PIXELBANKv8.2.1
Menu
Sign In
Back to DSA Study Plan
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)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)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

1
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

2
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
3
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
4
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
5
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
6
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)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 ii: ⌊(i−1)/2⌋\lfloor (i - 1) / 2 \rfloor
  • Left child: 2i+12i + 1
  • Right child: 2i+22i + 2

Push (insert): Add to the end, then sift up by swapping with the parent until the heap property is restored --- O(log⁡n)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)O(\log n). Peek: Return the root --- O(1)O(1).

Mathematical Intuition

A binary heap is a complete binary tree where every parent satisfies the heap property: in a min-heap, parent≤children\text{parent} \leq \text{children}; in a max-heap, parent≥children\text{parent} \geq \text{children}. Stored as an array, the children of index ii are at 2i+12i+1 and 2i+22i+2, and the parent is at ⌊(i−1)/2⌋\lfloor (i-1)/2 \rfloor. Completeness means height is O(log⁡n)O(\log n), so insert (bubble up) and extract-root (sift down) are both O(log⁡n)O(\log n). Peek at the root is O(1)O(1). A heap of nn elements uses exactly O(n)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)O(n) time --- faster than inserting elements one by one (O(nlog⁡n)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)O(\log n)
  • heapq.heappop(heap) --- pop the smallest, O(log⁡n)O(\log n)
  • heapq.heapify(lst) --- convert list to heap in-place, O(n)O(n)
  • heapq.heappushpop(heap, val) --- push then pop, optimized to O(log⁡n)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)O(n) — not O(nlog⁡n)O(n \log n) — by sifting down from the last non-leaf upward; the proof uses a telescoping sum ∑h=0log⁡n(n/2h+1)⋅h=O(n)\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)O(\log n); heapq.nlargest(k, arr) uses a size-kk heap for O(nlog⁡k)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 — GeeksforGeeksHeap (Priority Queue) — NeetCode
Previous
Advanced Graphs
Next
Dynamic Programming Basics