Java Reference
In-Depth Information
array empty. Then the child nodes of the node with index i have index 2 i and 2 i +
1, and the parent node of the node with index i has index i/2. For example, as you can
see in
Figure 20
, the children of node 4 are nodes 8 and 9, and the parent is node 2.
Storing the heap values in an array may not be intuitive, but it is very efficient. There
is no need to allocate individual nodes or to store the links to the child nodes. Instead,
child and parent positions can be determined by very simple computations.
Figure 20
Storing a Heap in an Array
745
746
The program at the end of this section contains an implementation of a heap. For
greater clarity, the computation of the parent and child index positions is carried out
in methods
getParentIndex
,
getLeftChildIndex
, and
getRightChildIndex
. For greater efficiency, the method calls could be avoided
by using expressions index
/ 2
,
2 * index
, and
2 * index + 1
directly.
In this section, we have organized our heaps such that the smallest element is stored
in the root. It is also possible to store the largest element in the root, simply by
