Skip to content

Volume ITechnology

4.17.0 — Heap & Priority Queue: The Pattern ​

Recognition cue. The problem says top k, k-th largest or smallest, median of a stream, merge k sorted things, or a loop repeatedly needs "the current largest or smallest" from a changing collection.

The move. A heap gives the extreme element in O(1) and inserts or removes in O(\log n). It does not keep everything sorted — it only guarantees the root, and that weaker promise is what makes it cheap.

The rule that decides min or max ​

People get this backwards constantly, so hold on to one sentence:

The root must be the item you are about to throw away.

  • k largest → min-heap of size k. The root is the weakest keeper, the one a better arrival replaces.
  • k smallest → max-heap of size k. The root is the worst keeper.

The three shapes ​

python
# 1. SIZE-K HEAP — top k, and the only version that works on a stream
heap = []  # (1)
for x in items:
    heapq.heappush(heap, x)          # (2) min-heap → keeps the k LARGEST
    if len(heap) > k:  # (3)
        heapq.heappop(heap)
# (4) heap[0] is the k-th largest

# 2. K-WAY MERGE — one candidate per source
for i, src in enumerate(sources):
    heapq.heappush(heap, (src[0], i, 0))  # (5)
while heap:
    val, i, j = heapq.heappop(heap)  # (6)
    ...
    if j + 1 < len(sources[i]):  # (7)
        heapq.heappush(heap, (sources[i][j+1], i, j+1))

# 3. TWO HEAPS — the middle of a stream
small = []   # (8) max-heap (negated), lower half
large = []   # (9) min-heap, upper half

The templates, line by line.

(1) Shape 1 keeps only k items. (2) Push each new item. Python's heap keeps the smallest at the front. (3) If there are now more than k, remove the smallest. It cannot be among the k largest. (4) The front of the heap is the smallest of the k largest, which is the k-th largest.

(5) Shape 2 starts with the first item of every sorted source. Each entry also carries which source it came from and its position there. The source number also breaks ties, so Python never has to compare the items themselves. (6) Take the smallest item across all sources. (7) If that source has more items, its next one becomes its new candidate.

(8) Shape 3 keeps the lower half of a stream in a heap that hands out its largest, using negated numbers. (9) The upper half sits in an ordinary heap that hands out its smallest. The two fronts are the two middle values, as worked in full in 4.17.7.

Python specifics worth knowing ​

heapq is min-only. For a max-heap, negate on the way in and on the way out. Forgetting one of the two is the standard bug.

heapify is O(n), not O(n \log n). Building in place by sifting down from the middle beats n separate pushes.

Push tuples for tie-breaking. (priority, index, item) — without a comparable second field, Python compares the third element, and objects without < raise TypeError. This bites in 4.9.10 Merge K Sorted Lists.

heapq.nlargest(k, xs) and nsmallest use a size-k heap internally. Know them, and know what they are doing.

JavaScript has no built-in heap. Write one, or use pairwise merging instead (4.9.10).

The seven problems ​

#ProblemThe one insight
4.17.1Kth Largest in a StreamKeep only k; the rest can never return
4.17.2Last Stone WeightThe collection changes, so sorting will not do
4.17.3K Closest Points to OriginCompare squared distances; max-heap for the k smallest
4.17.4Kth Largest in an ArrayQuickselect is O(n) because it recurses into one side
4.17.5Task SchedulerRun the most frequent task; or use the skeleton formula
4.17.6Design TwitterA k-way merge with an early stop at 10
4.17.7Find Median from Data Stream ★Two heaps facing each other

★ marks the Blind 75 subset.

When not to use a heap ​

When the values are bounded small integers — bucket or count instead, and get O(n). That is the linear solution to 4.4.5 and the follow-up to 4.17.7.

When you need the k-th element once, from an array you may reorder — quickselect is O(n) average.

When k is close to n — the heap's advantage disappears; just sort.

When you need to delete an arbitrary element — heaps cannot do it efficiently. Use lazy deletion with a "to remove" map, or a balanced tree.

What the interviewer will push on ​

"Min-heap or max-heap?" The root is the item you evict. Say it that way.

"Why not sort?" Sorting is O(n \log n) and needs the whole collection; a size-k heap is O(n \log k) and works on a stream.

"Can you beat O(n \log k)?" Quickselect for a one-off selection, O(n) average.

"Why is heapify O(n)?" Most nodes are near the bottom and barely sift.

"What if the data does not fit in memory?" The size-k heap holds only k items. For approximate percentiles at scale, name t-digest or Count-Min sketch.

One thing to volunteer: say the discard rule out loud — "anything outside the top k now can never re-enter it" — before writing the loop. That sentence is what justifies throwing data away, and it is the whole design.

Recall

  • A heap gives the extreme in O(1) and inserts or removes in O(\log n). It does not sort.
  • The root is the item you evict. k largest → min-heap; k smallest → max-heap.
  • Three shapes: size-k heap (top k, streams), k-way merge (one candidate per source), two heaps (the middle of a stream).
  • Python's heapq is min-only — negate for a max-heap, on the way in and out. heapify is O(n). Push tuples with a tiebreaker.
  • Quickselect beats a heap for a one-off k-th element: O(n) average, because it recurses into one side and the sizes halve.
  • Bounded small values beat a heap entirely — count into buckets for O(n).
  • Heaps cannot delete an arbitrary element; use lazy deletion or a balanced tree.

Next: 4.17.1 Kth Largest Element in a Stream — the size-k heap in its simplest form.

Combine chapters into one PDF

Pick the chapters you want. They print in the order you pick them.

Volume I — Technology
Part 0 — Retention & Notation
Part 1 — Foundations of Computation
Part 2 — Operating Systems
2.1 The Kernel
2.2 Processes
2.3 Threads & Scheduling
2.4 Concurrency Under the Hood
2.5 Memory Management
2.6 File Systems
2.7 Input/Output
2.8 Linux for Engineers
2.9 Windows & macOS in Practice
Part 3 — Languages, Compilers & Runtimes
3.6 JavaScript & V8
3.7 TypeScript
3.8 Node.js Internals
3.13 Python & CPython
3.14 FastAPI & Production Python
Part 4 — Data Structures & Algorithms
4.0 Classic Problems — Before NeetCode
4.4 Arrays & Hashing — Problems
4.5 Two Pointers
4.6 Sliding Window
4.8 Stack — Problems
4.9 Linked List — Problems
4.11 Binary Search — Problems
4.13 Trees
4.14 Tree — Problems
4.15 Trie — Problems
4.17 Heap — Problems
4.18 Backtracking — Problems
4.19 Graphs
4.20 Graph — Problems
4.21 Advanced Graph — Problems
4.23 1-D DP — Problems
4.24 2-D DP — Problems
4.26 Greedy — Problems
4.27 Interval — Problems
4.28 Math & Geometry — Problems
4.30 Bit Manipulation — Problems
Part 5 — Networking & the Web
5.3 IP
5.4 Transport
5.6 HTTP
Part 6 — Frontend Engineering
6.1 Browser Internals
6.2 HTML & CSS Mastery
6.3 JavaScript in the Browser
6.4 React, from First Component to Full Shop
6.5 Frameworks & Rendering
6.8 UI Engineering & Patterns
Part 7 — Databases & Storage
7.2 SQL Mastery
7.3 Storage Engine Internals
7.4 Transactions
7.5 NoSQL Taxonomy
7.8 Analytics & Big Data
Part 8 — Security, Identity & Cryptography
8.2 Cryptography
8.3 Protocols of Trust
8.4 Identity: AuthN & AuthZ
8.5 Application Security
8.6 Infrastructure Security
Part 9 — Software Design (LLD)
9.2 OOP Foundations
9.3 Design Principles
9.4 Design Patterns
9.5 Concurrency
9.6 API Design
9.7 LLD Interview Machines
9.9 Node/Express Production Playbook
Part 10 — Distributed Systems & HLD
10.7 Consistency & Consensus
10.8 Messaging & Microservices
10.14 Caching
Building blocks from the design seat
Part 11 — System Design Case Studies
Part 12 — AI & ML Engineering
12.1 What AI Engineering Is
12.2 The Math You Need
12.3 Classical Machine Learning
12.4 Data for ML
12.5 Deep Learning
12.6 Embeddings & Vector Search
12.7 Transformers & LLMs
12.8 Building with LLMs
12.9 Retrieval-Augmented Generation
12.10 Agents
12.11 Adapting Models
12.12 Production AI
12.13 Multimodal AI
12.14 AI Security & Governance
12.15 Case Studies & Capstone
Part 13 — Cloud, DevOps & Infrastructure
13.11 Git, from First Commit to Team Workflow
Part 14 — Containers: Docker & Kubernetes
14.1 Foundations
14.2 Docker
14.3 Kubernetes
14.4 Kubernetes on Azure
Part 15 — The Craft & Career
Nothing picked yet