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.

Trickle Down

Trickling down is a little more complicated than bubbling up. First we check if the node being examined is a leaf node using a call to HasLeftChild. If it is, the trickling down is complete. If not, we call LowerChildIndex, which returns the left child's index if it is the lower value of two children or if the node has only one child. If the right child exists and has a lower value that the left, its index is returned by LowerChildIndex.

Once we know the index of the child that has the lowest value we compare it with the current node. If the two are in the right order the trickling down process is finished. If not, the values are swapped and the TrickleDown method is called again for the selected child node.

void TrickleDown(int index)
{
    if (HasLeftChild(index))
    {
        int lowerChildIndex = LowerChildIndex(index);

        if (_contents[index] > _contents[lowerChildIndex])
        {
            SwapWithParent(lowerChildIndex);
            TrickleDown(lowerChildIndex);
        }
    }
}

private int LowerChildIndex(int index)
{
    if (HasRightChild(index))
    {
        int leftChildIndex = LeftChildIndex(index);
        int rightChildIndex = RightChildIndex(index);

        int lowerChildIndex = _contents[leftChildIndex] < _contents[rightChildIndex]
            ? leftChildIndex : rightChildIndex;
        return lowerChildIndex;
    }
    else
    {
        return LeftChildIndex(index);
    }
}

Array Expansion

We now need a couple of small members before we can implement the methods that add items, remove items and build a heap. These will control the automatic expansion of the array. The ExpansionRequired property returns true if the array is currently full. The ExpandArrayIfRequired method checks this property and, if expansion is required, increases the array's size in readiness for another full level of nodes. It does this by creating a new, larger array and copying the existing elements into it.

NB: The method that initialises a heap from an existing array breaks this functionality slightly as the heap's initial array is not necessarily sized exactly for a perfect binary tree. This could be rectified but has no real impact upon the heap.

bool ExpansionRequired
{
    get { return _nextItemIndex == _contents.Length; }
}

private void ExpandArrayIfRequired()
{
    if (ExpansionRequired)
    {
        int[] newValues = new int[_contents.Length * 2 + 1];
        _contents.CopyTo(newValues, 0);
        _contents = newValues;
    }
}

Adding to the Heap

We can now write the method that adds a new item to the heap. The preparation that we've already done makes this really easy. All we need to do is add the new value at the end of the heap's array, move the next item pointer accordingly and bubble up. During adding we'll also expand the array if necessary.

public void AddItem(int value)
{
    AddItemAtEnd(value);
    BubbleUp(LastLeafNodeIndex);
}

private void AddItemAtEnd(int value)
{
    ExpandArrayIfRequired();
    _nextItemIndex++;
    _contents[LastLeafNodeIndex] = value;
}

Extracting the Root Value

Next we'll add the method that extracts the value from the root of the heap, which is the smallest value. First we check if the heap is empty and throw an exception if it is. If items are present we take the value from the top of the heap and replace it with the last item from the heap, reducing the value of the next item pointer as we do so. Finally, the new root value is trickled down into its correct position.

public int ExtractRootItem()
{
    if (_nextItemIndex == 0)
    {
        throw new InvalidOperationException("The heap is empty");
    }

    int rootValue = _contents[RootIndex];
    MoveLastItemToRoot();
    TrickleDown(RootIndex);
    return rootValue;
}

void MoveLastItemToRoot()
{
    _contents[RootIndex] = _contents[LastLeafNodeIndex];
    _nextItemIndex--;
}
3 February 2013