Java Reference
In-Depth Information
26.1
A heap is a complete binary tree whose nodes contain
Comparable
objects. In a maxheap, the object
in each node is greater than or equal to the objects in the node's descendants. Segment 23.32 pro-
vided the following interface for the maxheap:
public interface
MaxHeapInterface<T
extends
Comparable<?
super
T>>
{
public void
add(T newEntry);
public
T removeMax();
public
T getMax();
public boolean
isEmpty();
public int
getSize();
public void
clear();
}
// end MaxHeapInterface
We will use this interface in our implementation of a maxheap.
Note:
You may also have heard the word “heap” used to refer to the collection of memory
cells that are available for allocation to your program when the
new
operator executes. But
that heap is not an instance of the ADT heap that we will discuss in this chapter. It would be
considered, however, in a book about programming languages.
26.2
Representing a complete binary tree.
We begin by using an array to represent a complete binary
tree. A complete tree is full to its next-to-last level, and its leaves on the last level are filled in from
left to right. Thus, until we get to the last leaf, a complete tree has no holes.
Suppose that we number the nodes in a complete binary tree in the order in which a level-order
traversal would visit them, beginning with 1. Figure 26-1a shows such a tree numbered in this way.
Now suppose that we place the result of this tree's level-order traversal into consecutive array loca-
tions beginning at index 1, as Figure 26-1b shows. This representation of the data in the tree enables
us to implement any needed tree operations. By beginning at index 1 instead of 0, we can simplify the
implementation somewhat, as you will see.
VideoNote
Implementing the ADT heap
26.3
Since the tree is complete, we can locate either the children or the parent of any node by performing
a simple computation on the node's number. This number is the same as the node's corresponding
array index. Thus, the children of the node
i
—if they exist—are stored in the array at indices 2
i
and
2
i
+
1. The parent of this node is at array index
i
/
2, unless of course the node is the root. In that
case,
i
/
2 is 0, since the root is at index 1. To detect the root, we can watch for either this index or a
special value—called a
sentinel
—that we place at index 0.
Note:
When a binary tree is complete, using an array instead of linked nodes is desirable.
You can use a level-order traversal to store the tree's data into consecutive locations of an
array. This representation enables you to quickly locate the data in a node's parent or chil-
dren. If you begin storing the tree at index 1 of the array—that is, if you skip the array's first
element—the node at array index
i
•
Has a parent at index
i
/
2, unless the node is the root (
i
is 1)
•
Has any children at indices 2
i
and 2
i
+
1
