The Structure That Only Ever Knows Its Smallest Item

Subtitle: One weak rule. One cheap answer.

• Left column - What the one rule buys:
• Parent smaller than both children
• The root IS the minimum
• Peek the minimum in O(1)
• Insert or extract in O(log n)
• A value walks one root-to-leaf path

• Right column - What that rule costs:
• Siblings have no defined order
• Second smallest needs real work
• No range scan at all
• Cannot iterate in sorted order
• Find any given value is O(n)

• Where it breaks:
• The trap: the word priority appears
• Weak order gives nothing to search by
• Need find, delete or ranges? Wrong tool
• Use a balanced tree or a skip list
• Static data? Sort once, then look up
• Test: ask it for the second smallest

• Heapify is linear, not n log n:
• Building from an array is O(n)
• n inserts would cost O(n log n)
• So making a heap beats sorting
• True when you want only the top few

• Lives in a flat array, no pointers:
• Children of i sit at 2i+1 and 2i+2
• Parent of i sits at (i-1)/2
• Neighbours share cache lines
• Heapsort needs no extra memory

• Use it when:
• You need the extreme again and again
• You never need the order
• A scheduler picking the next task
• Dijkstra picking the nearest node
• Top-k over a stream, evict the root

Taped rule strip: Not a cheap sorted thing. An unsorted thing with one correct end.