Command Palette

Search for a command to run...

Hectal

Module 18

Heaps and Priority Queues

Always know the smallest or largest: how a heap works inside an array, Java's PriorityQueue, top-K, two heaps and K-way merge.

Intermediate 5 lessons 9 problems ~60 min of lessons
Top K with a HeapTwo HeapsK-Way Merge

A heap answers one question fast: what is the smallest (or largest) item right now? Adding an item and removing the top both cost O(log n), and peeking at the top is O(1). It does this with a complete binary tree stored inside a plain array.

This module opens the heap up (sift-up and sift-down drawn step by step), then teaches the three heap patterns that cover most interview problems: keep a heap of size K for top-K questions, balance two heaps for running medians, and merge K sorted sources by always taking the smallest head.

Best after: Binary Trees

Part 1

Learn the ideas

  1. 18.1How a Heap Works Inside an ArrayA min-heap is a complete binary tree where every parent is ≤ its children, stored in an array: the children of index i are 2i + 1 and 2i + 2.15 min
  2. 18.2PriorityQueue in JavaJava's PriorityQueue is a min-heap by default; pass a Comparator for a max-heap or to order arrays and objects.10 min
  3. 18.3Top-K: Keep a Heap of Size KTo keep the K largest items, use a min-heap of size K: the top is the weakest of the winners, and anything smaller is thrown out.12 min
  4. 18.4Two Heaps for a Running MedianA max-heap holds the smaller half and a min-heap the larger half; their tops are the middle values.12 min
  5. 18.5K-Way MergeMerge K sorted sources by keeping one candidate from each in a min-heap: always take the smallest, then refill from the same source.10 min

Part 2

Solve the problems

In order of difficulty. Each one shows the pattern it teaches.

  1. 18.1Last Stone WeightEasyTop K with a Heap

    A max-heap as a simulation tool: repeatedly take the two largest.

  2. 18.2K Closest Points to OriginMediumTop K with a Heap

    K smallest by a computed key: a max-heap of size K keyed on squared distance.

  3. 18.3Kth Largest Element in a StreamEasyTop K with a Heap

    Top-K as a long-lived data structure: the min-heap's top is always the k-th largest.

  4. 18.4Task SchedulerMediumTop K with a Heap

    Greedy with a heap: always run the task with the most copies left; then see the counting formula behind it.

  5. 18.5Find Median from Data StreamHardTwo Heaps

    The two-heaps pattern as a class.

  6. 18.6IPOHardTwo Heaps

    Unlock options over time: sorted by requirement, and a max-heap of the options you can currently afford.

  7. 18.7Kth Smallest Element in a Sorted MatrixMediumK-Way Merge

    Rows as sorted lists: K-way merge, or binary search on the value with a staircase count.

  8. 18.8Smallest Range Covering Elements from K ListsHardK-Way Merge

    K-way merge with a window: the heap holds one element per list; the range is heap minimum to the running maximum.

  9. 18.9Furthest Building You Can ReachMediumTop K with a Heap

    Deciding in hindsight: give ladders to the largest climbs so far by keeping them in a min-heap, and pay bricks for the smallest.