The C++Course provides a general introduction to programming in C++. It is based on A.B. Downey's book, How to Think Like a Computer Scientist. Click here for details.

Home Heap Definition of a Heap
 
del.icio.us Reddit Facebook StumbleUpon MySpace Twitter

Definition of a Heap

A heap is a special kind of tree. It has two properties that are not generally true for other trees:

completeness
The tree is complete, which means that nodes are added from top to bottom, left to right, without leaving any spaces.
heapness
The item in the tree with the highest priority is at the top of the tree, and the same is true for every subtree.

Both of these properties bear a little explaining. This figure shows a number of trees that are considered complete or not complete:

An empty tree is also considered complete. We can define completeness more rigorously by comparing the height of the subtrees. Recall that the height of a tree is the number of levels.

Starting at the root, if the tree is complete, then the height of the left subtree and the height of the right subtree should be equal, or the left subtree may be taller by one. In any other case, the tree cannot be complete.

Furthermore, if the tree is complete, then the height relationship between the subtrees has to be true for every node in the tree.

It is natural to write these rules as a recursive method:

    int height(Tree* head)
    {
      if(head==null) return 0;
      int right = height(head->right), left = height(head->left);
      if(right > left) return right + 1;
      return left + 1;
    }

    bool isComplete (Tree *tree) {
        // the null tree is complete
        if (tree == null) return true;

        int leftHeight = height (tree->left);
        int rightHeight = height (tree->right);
        int diff = leftHeight - rightHeight

        // check the root node
        if (diff < 0 || diff > 1) return false;

        // check the children
        if (!isComplete (tree->left)) return false;
        return isComplete (tree->right);
    }

For this example I used the linked implementation of a tree. As an exercise, write the same method for the array implementation. Also as an exercise, write the height method. The height of a null tree is 0 and the height of a leaf node is 1.

The heap property is similarly recursive. In order for a tree to be a heap, the largest value in the tree has to be at the root, and the same has to be true for each subtree. As another exercise, write a method that checks whether a tree has the heap property.
Home Heap Definition of a Heap

Last Update: 2005-12-05