A heap is a specialized tree-based data structure that is:
- almost complete
- satisfies the heap property
The heap property – if P is a parent node of C, then the key (the value) of P is either greater than or equal to (in a max heap) or less than or equal to (in a min heap) the key of C.
The heap is an implementation of a priority queue.
Useful structure when needing to repeatedly remove the object with the highest or lowest priority.
Since a heap is an almost perfect tree, it extends itself nicely to be implemented with an array.
Nodes are always inserted in the next available most right spot. Top to bottom, left to right. After an element is inserted we need to bubble it up to the correct location to insure the heap property is maintained.
To remove the top element, we insert the last leaf node as the root. Than we need to bubble that value down until the heap property is restored.
Navigating the Tree as an array
With the heap implemented as an array, we can navigate around pretty easily if we remember a few formulas.
Parent = (index – 2) / 2
Left = index * 2 + 1
Right = index * 2 + 2