🚀 Phases 1–5 are live — Days 1–17 cover the foundations and the algorithmic patterns. See the roadmap →
Day 7 - Heaps and Priority QueuesOverview

Day 7 — Heaps and Priority Queues

Heaps are the data structure that answers a deceptively simple question: “Give me the smallest (or largest) thing right now.” Not the sorted list. Not all of them. Just the one extreme element — fast.

That’s it. That’s the entire job. And once you have an answer to that question in O(log n), an enormous family of problems suddenly has clean solutions.

What you’ll learn today

  • Binary heaps — a tree where the parent is always smaller (min-heap) or larger (max-heap) than its children, stored cleverly in a flat array
  • The four core operations — push, pop, peek, heapify — and why the array layout makes parent / child lookup arithmetic
  • The surprising O(n) build-heap that lets you turn an arbitrary array into a heap faster than sorting it
  • Priority queues — the abstract API that languages all expose, backed by a heap underneath
  • The two-heap pattern — a max-heap glued to a min-heap that maintains the median of a stream in O(log n)
  • Where heaps power real systems — Dijkstra, Huffman coding, A*, event-driven simulation, schedulers
  • Ten classic interview problems covering every heap pattern: Kth Largest, Top K Frequent, Merge K Sorted Lists, Median of a Stream, Reorganize String, Task Scheduler, and more

You’ve already met heaps twice. Day 4’s queue variants page introduced priority queues. Day 12’s Heap Sort used a max-heap to sort in place. Today we open the hood and look at what’s actually inside.

Roadmap

  1. Introduction — what a heap is, the heap property, min vs max, why we store a tree in an array.
  2. Heap Operations — push, pop, peek, sift-up, sift-down, and the O(n) build-heap.
  3. Priority Queues — the standard API, plus the stdlib heap in C++, Python, and Java.
  4. Applications — where heaps actually earn their keep: Dijkstra, Huffman, top-K maintenance, event simulation, scheduling.
  5. The Two-Heap Pattern — the max-min sandwich that gives you the running median in O(log n).
  6. Basic Questions — warm-up exercises: verify heap property, trace operations, build heaps by hand.
  7. Practice Questions — ten interview classics where a heap collapses an O(n log n) problem into something cleaner.

The mental model to keep: a heap is a sorted enough structure — sorted enough to give you the extreme in O(1) and maintain that property in O(log n), but not fully sorted in the middle. That partial-order is where all the speed comes from.

Sorted Array to BSTIntroduction