Heap is a binary tree where the max element is always at the root. Heap is usually implemented by using an array where:
- Root is at element index 0.
- A node’s two children is at indices and .
- A node’s parent is at index .
Insert a new element can be done by appending it to the end of the array then do a “SIFT UP” operation to restore the heap. To remove the largest element can be done by removing the element at index 0, move the last element of the array to the index 0, then do a “SIFT DOWN” operation.
Heap is useful in many situations, for example:
- Top N elements from an array.
- K-way merging
The power of heap comes from the point where it finds max element avoid doing the comparison with all other elements again, instead, the heap structure keeps some comparison result so the new element’s position can be decided in less time.