Java Reference
In-Depth Information
FIGURE 26-1
(a) A complete binary tree with its nodes numbered in level order;
(b) its representation as an array
(a)
(b)
90
90
80
60
70
30
20
50
10
40
1
0
1
2
3
4
5
6
78910
11
12
80
60
2
3
30
20
70
50
4
5
6
7
10
40
8
9
The complete binary tree in Figure 26-1 is actually a maxheap. We will now use the previous
array representation of a complete tree in our implementation of a maxheap.
Question 1
If an array contains the entries of a heap in level order beginning at index 0,
what array entries represent a node's parent, left child, and right child?
26.4
Beginning the class
MaxHeap
.
As Listing 26-1 shows, our class begins with the following data
fields: an array of
Comparable
heap entries, the index of the last entry in the array, and a constant
for the default initial capacity of the heap. If
lastIndex
is less than 1, the heap is empty, since we
begin the heap at index 1. Two simple constructors are similar to constructors we have seen
before in array-based implementations. We allocate one extra array location, since we will not
use the first one. The methods
getMax
,
isEmpty
,
getSize
, and
clear
have simple implementations
that are shown in this listing. We consider the methods
add
and
removeMax
next.
LISTING 26-1
The class
MaxHeap
, partially completed
import
java.util.Arrays;
public class
MaxHeap<T
extends
Comparable<?
super
T>>
implements
MaxHeapInterface<T>
{
private
T[] heap;
// array of heap entries
private int
lastIndex;
// index of last entry
private static final int
DEFAULT_INITIAL_CAPACITY = 25;
public
MaxHeap()
{
this
(DEFAULT_INITIAL_CAPACITY);
// call next constructor
}
// end default constructor
