Last Minute Notes
  • Github
  • Docs
  • Learn
    @sayanstwt
Lessons
0/15 done
  • Tree BFS
  • Tree DFS
  • Two Heaps
  • Top K Elements
  • K-way Merge
  • Trie
Learn/Data Structures & Algorithms/Trees & Heaps

Two Heaps

8 min Advanced 8 steps

Keep a running median with a max-heap and a min-heap.

Added
5
Shifted
0sorted insert is O(n)
median
5
5new
current visited done
In this lessonStep 1 of 8
  1. The problem
  2. Two halves
  3. Add 5
  4. Add 15
  5. Add 1, 3
  6. IPO
  7. Pitfalls
  8. Recap
Step 1 / 8problem

Median of a growing stream

Numbers arrive one at a time: 5, 15, 1, 3. After each one, report the median.

Keeping everything sorted works, but each insert shifts elements, and we only ever look at the middle.

Key idea

Median or middle value from a stream, or two competing priorities: think two heaps.

←→ step·R replay·Space pause

You'll learn

  • Split a stream into a max-heap half and a min-heap half
  • Keep both invariants on every addNum
  • Read the median from the tops in O(1)
  • Use two heaps for two competing priorities (IPO)
Read the full notesTrees, Graphs and Search, 4