Java Reference
In-Depth Information
required to traverse the tree are extremely simple and likely to be very fast on
most computers. The heap entity consists of an array of objects and an integer
representing the current heap size.
In this chapter, heaps are drawn as trees to make the algorithms easier to
visualize. In the implementation of these trees we use an array. We do not use
the implicit representation for all search trees. Some of the problems with
doing so are covered in Exercise 21.8.
21.1.2 heap-order property
The property that allows operations to be performed quickly is the heap-order
property. We want to be able to find the minimum quickly, so it makes sense
that the smallest element should be at the root. If we consider that any subtree
should also (recursively) be a heap, any node should be smaller than all of its
descendants. Applying this logic, we arrive at the heap-order property.
The heap-order
property states that,
in a heap, the item
in the parent is
never larger than
the item in a node.
heap-order property
In a heap, for every node X with parent P , the key in P is smaller than or equal to
the key in X .
The root's parent
can be stored in
position 0 and
given a value of
negative infinity.
The heap-order property is illustrated in Figure 21.2. In Figure 21.3(a),
the tree is a heap, but in Figure 21.3(b), the tree is not (the dashed line
figure 21.2
Heap-order property
P
P - X
X
figure 21.3
Two complete trees:
(a) a heap; (b) not a
heap
13
13
21
16
21
16
24
31
19
68
6
31
19
68
65
26
32
65
26
32
(a)
(b)
 
Search WWH ::




Custom Search