Binary heap¶
A binary heap is a special kind of binary tree. It maintains two invariants:
- (Shape property) A binary heap is a complete binary tree. Furthermore, leaf nodes are filled left-to-right.
- (Heap property) All nodes compare less than or equal to their children, if any.
As stated, these properties apply to a min-heap; there is also a max-heap where the second property becomes
- (Heap property) All nodes compare greater than or equal to their children, if any.
A min-heap is used to represent a minimum priority queue, while a max-heap is used to represent a maximum priority queue.
Operations¶
The two primary operations that can be performed on a binary heap
(henceforth, heap) are insert and extract. insert adds a
new value to the heap, while extract removes the minimum element
from the heap (if a max-heap, the maximum element).
insert¶
To insert an element, we insert the value as a leaf node. To maintain the shape property, this leaf node must either be inserted in the current lowest level (if the tree is currently not perfect) or on a new level (if the tree is currently perfect). Additionally, since we fill the bottom row from left-to-right there is exactly one candidate position for the new element.
We must now ensure that the heap property is maintained. Recursively, we swap the new element with its parent if it compares greater than the parent. This continues until the parent compares less than or equal to the new node. Note that after this operation the heap property is maintained.
This operation takes \(O(\log n)\) time.
extract¶
By the heap property, the root of the tree contains the minimum element, so it is easy to extract. However, removing it violates the shape property (since there are now two disconnected trees). Thus we replace the root node with the final element of the final row in the heap. The shape property is now maintained. However, we must verify the heap property is maintained. If the root element compares greater than one of its children, swap it with the lesser of the two children. Recursively apply this procedure to the node until the heap property is maintained.
This operation takes \(O(\log n)\) time.