If you say priority queue in an interview, I'll hire you

This is sort of a joke, but also not.

The Heap DataStructure

The simplest way to put it is a binary tree where every child and grand child is smaller (MaxHeap), or larger (MinHeap) than the current node.

  • Whenever a node is added, we must adjust the tree
  • Whenever a node is deleted, we must adjust the tree
  • There is no traversing the tree


Some cool characteristics

  • It is self balancing
  • It can be used for priority
  • Funnest data structure to implement, but easy to get wrong!

If there is time

Lets implement it!

Careful about garbage.

the previous values in the array remain unless you nil them out...