Neo & Byte · #5 · Min-heap

Find Box 7

Four-panel comic. Byte has stacked boxes as a min-heap, box 1 on top. A customer orders box 7, and Byte throws box after box aside until he finds it in the very last spot.

Transcript

  1. Panel 1. Byte: “Smallest on top. Always. Instant!”
  2. Panel 2. Neo: “Nice. A customer just ordered box 7.”
  3. Panel 3. Byte: “1? No. 3? No. 6? No. 4? No…”
  4. Panel 4. Byte: “Found it! Only had to check… all of them.”

Actually…

A min-heap keeps the smallest value on top, so reading it takes O(1), and inserting a value or taking out the smallest one takes O(log n). Each value is only smaller than its own children, so nothing tells you where any other value is: finding it means checking the values one by one, O(n). Here box 7 sat in the very last spot.

See it step by step

In the VisiGrab app, build a min-heap yourself: insert, take the minimum, and watch every swap. App Store · Google Play