TRT
Sign in

Core · Module 11 · Lesson 4 of 4

Top-k and merging streams

A heap of just k items finds the k largest of a billion in one pass. A heap of k stream heads merges k sorted streams. Two heaps keep a running median. These three patterns cover most heap problems.

Pro — members onlyAbout 15 minutes

By the end you can

  • Find the k largest items of a stream with a size-k min-heap, in O(n log k) time and O(k) memory
  • Merge k sorted lists or streams with a heap of their current heads
  • Maintain a running median with two heaps

Builds on Heapify and heap sort.

01 · A question first

A server has logged a billion requests, and you want the 10 slowest. Sorting all of them needs O(n log n) time and every request in memory at once. A heap holding just 10 items does it in one pass. Why does it have to be a min-heap, when you want the largest?

Make a guess before you read on.

02 · The idea

Members only

Unlock the full lesson

This lesson is part of the membership. Join to read it in full, along with every other premium deep dive.

What's inside

  • Top k with a small heap
  • The alternatives
  • Merging k sorted streams
  • Two heaps for a running median
  • Heaps inside real systems
  • Pseudocode & Multi-Language Implementations (C++, Java, Python)
  • Complexity Derivation, Edge Cases & Common Mistakes
See plansAlready a member? Sign in

03 · Practice

Practice · medium · LeetCodeKth largest element in an arrayFind the kth largest value in an unsorted array with a size-k heap or with quickselect, without fully sorting it.Practice · medium · LeetCodeTop k frequent elementsReturn the k most frequent values, by counting with a hash map and keeping a size-k heap of counts.Practice · medium · LeetCodeK closest points to originReturn the k points nearest the origin with a max-heap of size k keyed by squared distance.Practice · hard · LeetCodeMerge k sorted listsMerge k sorted linked lists into one, in O(N log k), with a min-heap of the current list heads.Practice · hard · LeetCodeFind median from data streamMaintain the median of a growing stream with a max-heap for the lower half and a min-heap for the upper half.Practice · medium · LeetCodeTask schedulerFind the minimum time to run tasks when equal tasks need n idle intervals between them, by always running the most frequent remaining task.

Asked in interviews

Something wrong with this lesson? Report a problem