Heap Data Structure
Min binary heap definition: a binary tree such that for every node x, the children of x have greater (or equal) keys than the key of x
Principal property for min heap: the root node has the least key in the heap
Supporting operations
- Swim -- starting at right-most leaf node, swap node upwards as long as parent is greater than current node
- Sink -- starting a root node, swap node downward if child node is less than current node; if both nodes are less than current node, swap with least child
A heap is used as an efficient implementation of a priority queue