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

The final method adds the more efficient process for building a heap from an existing array of items. It starts by replacing the heap's contents with the unordered array that it is provided to its parameter. It then loops through all non-leaf nodes from the bottom-right of the tree to the root, performing the trickle down process for each.

public void BuildHeap(int[] data)
{
    _contents = data;
    _nextItemIndex = data.Length;
    for (int parent = LastNonLeafNodeIndex; parent >= 0; parent--)
    {
        TrickleDown(parent);
    }
}

Testing the Heap with a Heapsort

We can now test the heap by using it to perform a heapsort. This is a sort operation that works by building a heap and repeatedly extracting its root value until exhaustion. Add the code shown below to the Main method and run it to see the results. It generates 50 random numbers and combines them in a heap. The while loop extracts the root value repeatedly until the heap is empty, outputting each value to the console. You should see that the values are sorted by the process.

const int count = 50;

Random random = new Random();
IntegerHeap heap = new IntegerHeap();
int[] initial = new int[count];

for (int i = 0; i < count; i++)
{
    initial[i] = random.Next(1000);
}

heap.BuildHeap(initial);

while (heap.Count > 0)
{
    Console.WriteLine(heap.ExtractRootItem());
}
3 February 2013