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.

Representing a Heap in an Array

Now that we've looked at the structure of a heap and the three processes used to build and modify one, we are closer to being able to implement a heap in C#. Before we begin, we need to consider how the heap data will be held. We could create a binary tree class that contained nodes, where each node was an object with properties linking it to its parent and its left and right children. However, this would introduce unnecessary overheads.

A simpler way to store the contents of a heap is in an array. All we need to do is hold the root node's value in the first element of the array, at index zero. The next level of the tree uses indexes one and two, the third level indexes three, four, five and six and so on. This means that each time we add a new node it is added as the next unused element in the array.

The figure below shows the mapping between a three-level heap and an array.

Holding a binary heap in an array

Using an array removes the need to hold the links between nodes. When we need to traverse the tree to add, remove or swap nodes we can use basic arithmetic instead. The rules are as follows:

  • New nodes are always added in the first unused array index.
  • The root node is always at index zero.
  • The index of the left child of a node is found by multiplying the parent index by two and adding one.
    Left Child Node Index Equation
  • The index of the right child of a node is found by multiplying the parent index by two and adding two.
    Right Child Node Index Equation
  • The parent of any node except the root, which has no parent, is found by subtracting 1 from the node's index then dividing by two and rounding down to the nearest integer.
    Parent Node Index Equation
  • The final, non-leaf node in a tree is the parent of the last leaf node.

Implementing a Heap

In the remainder of this article we'll use the information above to create a heap class in C#. The heap will be simplistic, allowing you to generate a min heap of integers. It would be trivial to change this into a max heap, or to alter the data type.

Start by creating a new console application project and adding a class named, "IntegerHeap".

public class IntegerHeap
{
}

We need to hold the contents of the heap in an array and maintain a pointer to tell us where the next item in the heap should be placed within the array. We'll use two private fields for this information. We can initialise them in the constructor as shown below. Note that the array is configured to allow up to seven items, which is enough for a three-level heap. When we add an eighth item we'll automatically increase the available space in the array to allow for another level.

int[] _contents;
int _nextItemIndex;

public IntegerHeap()
{
    _contents = new int[7];
    _nextItemIndex = 0;
}

Count Property

Although not strictly necessary, it will be useful to include a Count property that tells us how many items are currently stored on the heap. This value coincides with the value of the next index pointer.

public int Count
{
    get { return _nextItemIndex; }
}
3 February 2013