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  
Definition of a Heap
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 