Binary Heap
A binary heap can be used as a priority queue, as the highest (or lowest) value node is always at the root of the tree.
Types of Heaps
max-heap
The value of each node is greater than all of its descendants
min-heap
The value of each node is less than all of its descendants
Heap Rules
Follow its heap condition (either max-heap or min-heap)
The tree must be complete
It must not have any empty node positions. Although the bottom row can have empty positions. But there cannot be any nodes to the right of those empty nodes.
Example of incomplete heap (the 36 does not have a left child)
Heap properties
Heaps are weakly ordered.
It's not ordered like a binary search tree where values less than a node are on the left branch, and values greater than the node are on the right branch.
We only know that the descendant nodes are smaller than a given node in a max-heap. And vice versa for a min-heap.
In a max-heap, the greatest value will always be at the root node. In a min-heap the smallest value will be at the root node.
Implementation
Heaps are usually implemented as an array. This makes it easy to keep track of the root node and the last node in the 'tree'. The root node is the first element of the array. The last node is the last element of the array.
The first two diagrams above show how the heap is represented in the array.
To find the left child of a node:
(index * 2) + 1
To find the right child of a node:
(index * 2) + 2
To find the parent of a node:
(index - 1) / 2
Note: the above does integer division, so the remainder is thrown away
Primary Operations
Insertion
These steps are for a max-heap. Min-heap follows the same steps except a min comparison is done instead.
A new node is inserted into the last node
The new node is compared to its parent node
If the new node is greater than its parent, swap the nodes
repeat steps 2 - 3 until it has a parent that has a greater value than it.
Deletion
These steps are for a max-heap. Min-heap follows the same steps except a min comparison is done instead.
Important: We only ever delete the root node.
Replace the root node with the last node
Trickle the root node down to its proper place
Check both children of the trickle down node to see which one is bigger
If the trickle node is smaller than the larger of the two child nodes, then swap the trickle node with the larger child
repeat above two steps until the trickle node has no descendants that have a greater value than it
By repeatedly popping the root element, we get the list in sorted order (descending). It will be in ascending order for a min-heap.
Last updated
