Java Reference
In-Depth Information
741
Figure 17
A Heap
A heap is superficially similar to a binary search tree, but there are two important
differences.
1. The shape of a heap is very regular. Binary search trees can have arbitrary
shapes.
2. In a heap, the left and right subtrees both store elements that are larger than the
root element. In contrast, in a binary search tree, smaller elements are stored in
the left subtree and larger elements are stored in the right subtree.
Suppose we have a heap and want to insert a new element. Afterwards, the heap
property should again be fulfilled. The following algorithm carries out the insertion
(see
Figure 18
).
1. First, add a vacant slot to the end of the tree.
