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
(whiteboard)
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...