BlackWaspTM

This web site uses cookies. By using the site you accept the cookie policy.This message is for compliance with the UK ICO law.

Algorithms and Data Structures
.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.

Building a binary heap

The process to reorder the heap starts by finding the last non-leaf node in the tree, as shown below.

Building a binary heap

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.

Building a binary heap

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.

Building a binary heap

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.

Building a binary heap

The processing of parent nodes continues until the root node is reached. This again must be trickled down if it is incorrectly ordered.

Building a binary heap

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.

Building a binary heap

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.

Building a binary heap

3 February 2013