.NET 1.1+Binary Heaps
A binary heap is a data structure, based upon a complete binary tree, that allows the first item in an ordered set to be quickly extracted. Heaps are used in several popular algorithms, including the heapsort method for ordering elements in a collection.
Building a Heap
In some situations you may need to build a heap gradually and can do so by repeatedly using the add process described earlier, where each item is added in the next available node position and bubbled up. However, this is an inefficient way to populate a heap when you already know the set of values that must be included.
A better way to build a heap is to build a complete binary tree from the starting values in an arbitrary order. This may produce a tree similar to the image below, which happens to be a max heap but that we will turn into a min heap.
The process to reorder the heap starts by finding the last non-leaf node in the tree, as shown below.
Once the last parent node is found, the trickle down process is executed against it. In the example tree this means that the 8 and 5 will be swapped. Once the trickle down process is complete, the branch of the tree starting at the original parent node's position will be correctly ordered.
The process is now repeated for the previous non-leaf node, either to the left of the first position or at the right hand side of the tree one level up. In the example this is the 6.
Again we use the trickle down process to ensure that the branch of the tree starting at the parent node becomes correctly ordered. This time the 3 and 6 must change places.
The processing of parent nodes continues until the root node is reached. This again must be trickled down if it is incorrectly ordered.
In the example the first part of the trickle down process swaps the 9 with its smaller child, which is the 3 in the left child node.
The second iteration of the trickle down process swaps the 9 and the 4. This ends the process, as the node has become a leaf node. The binary tree is now a valid heap.
3 February 2013