Implementing the Binary Heap

The priority queue chapter worked with the binary heap by hand. In this chapter, you will implement it twice: first from linked nodes, then in an array.

After reading this chapter, you should be able to:

  • Find the path from the root to any position in a complete tree by writing the position’s number in binary, in
  • Implement add and remove on a linked heap, with a recursive add that uses the call stack in place of parent references to swim the new value up
  • Trace a recursive add on a linked heap as a call stack
  • Store a binary heap in an array in level order, and move between a node and its parent or children by index arithmetic
  • Implement an array heap, with swim and sink as loops
  • Explain why the array is the usual way to store a binary heap, comparing the two heaps by cost and memory

You can download the accompanying code for this chapter: starter and solution.

Sections

  1. A Heap Built from Nodes
  2. Finding the Next Open Slot
  3. The Path in Binary
  4. Reaching the Parent
  5. add, Recursively
  6. remove in Code
  7. Tracing a Recursive add
  8. A Heap in an Array
  9. Tracing the Array
  10. The ArrayHeap Class and Its Helpers
  11. swim and sink in an Array
  12. Implementing peek, add, and remove
  13. Two Heaps, Side by Side