P-4.6 Heaps and Priority Ordering

Work through these

• The heap property: each parent is smaller than its children

  Ordering is enforced only between a parent and its own children, never across a level. That much weaker promise is enough to know where the smallest item is and cheap enough to maintain.

  Algorithms, 4th Edition — companion site · Reference

• A complete tree stored in an array, with children found by arithmetic

  Filling every level left to right means position and structure agree, so a child sits at twice the index and a parent at half. No links are stored at all.

• Sifting up on insert and sifting down on removal

  A new item is placed at the end and moved up while it is out of order; removing the top moves the last item to the front and sinks it. Both walk one path of the tree.

• Priority ordering as a use of a heap, not a structure of its own

  Serving the most urgent item rather than the earliest is the pattern behind schedulers, event simulation and several graph algorithms. A heap is the usual implementation.

• Heapsort, and why building a heap is faster than it looks

  Repeatedly removing the top gives a sorted sequence in place with no extra memory. Building the heap in the first place costs linear time rather than the obvious bound, which is a result worth working through.