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.

Navigation Members

Next we can create some members that will help us navigate the heap or improve the readability of the code. There are eight such members:

  • The RootIndex constant is purely for readability. Set to zero, it gives the index of the root node within the array.
  • The ParentIndex method calculates the index of the parent of any given node. We could include a check to make sure that we never look for the parent of the root node. However, I've omitted this check, as the method is private and should never be called in this manner.
  • LeftChildIndex and RightChildIndex find the indices of the two child nodes of a non-leaf node. Again, no validity checks are included because the methods are private.
  • To determine whether a node has children, the HasLeftChild and HasRightChild return Boolean values. HasLeftChild could have been named, "HasChildren", as the heap constraints mean that a node should never have a right child without a left child. Both methods work by calculating the index that would be used for a child and checking whether or not that index is in use by comparing the calculated node index with the next item pointer.
  • The last two navigation methods allow us to find the index of the final leaf node and the last non-leaf node in the tree. They are properties named LastLeafNodeIndex and LastNonLeafNodeIndex respectively. The former returns a value calculated by subtracting one from the next item index pointer. The latter is the index of the parent node of the former.
const int RootIndex = 0;

int ParentIndex(int index)
{
    return (index - 1) / 2;
}

int LeftChildIndex(int index)
{
    return (index * 2) + 1;
}

int RightChildIndex(int index)
{
    return (index * 2) + 2;
}

bool HasLeftChild(int index)
{
    return LeftChildIndex(index) < _nextItemIndex;
}

bool HasRightChild(int index)
{
    return RightChildIndex(index) < _nextItemIndex;
}

int LastNonLeafNodeIndex
{
    get { return ParentIndex(LastLeafNodeIndex); }
}

int LastLeafNodeIndex
{
    get { return _nextItemIndex - 1; }
}

SwapWithParent Method

For both bubbling up and trickling down we need to swap a node's value with that of its parent. As we'll be using this process repeatedly it makes sense to put it into a method. The SwapWithParent method performs the swap using a temporary variable. It could also be achieved with an XOR swap but this would make it trickier to change the data type of the heap to a non-integer type.

void SwapWithParent(int childIndex)
{
    int parentIndex = ParentIndex(childIndex);
    int temp = _contents[childIndex];
    _contents[childIndex] = _contents[parentIndex];
    _contents[parentIndex] = temp;
}

Bubble Up

With the navigation and swap members in place, the recursive bubbling up process is trivial. The BubbleUp method starts by checking if we are trying to bubble up from the root node. If we are, the process is finished. If not, we compare the current node's value with that of its parent. If the nodes are incorrectly ordered we switch their values and perform a recursive call to continue the bubbling up.

void BubbleUp(int index)
{
    if (index != RootIndex)
    {
        int parentIndex = ParentIndex(index);

        if (_contents[index] < _contents[parentIndex])
        {
            SwapWithParent(index);
            BubbleUp(parentIndex);
        }
    }
}
3 February 2013