The Java Course provides a general introduction to programming in Java. 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  
See also: The Heap  
Search the VIAS Library  Index  
Definition of a Heap
A heap is a special kind of tree. It has two properties that are not generally true for other trees:
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: public static boolean 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 