Java Reference
In-Depth Information
90
60
50
10
85
70
20
40
30
80
90
0
1
2
3
4
5
6
7
8
9
10
11
12
60
85
100 > 85, so move 85
100
70
20
50
10
40
30
80
90
60
70
85
20
50
10
40
30
80
90
0
1
2
345
6
7
8
9
10
11
12
100
60
100 > 90, so move 90
70
85
20
50
10
40
30
80
90
60
100
70
85
20
50
10
40
30
80
100
0
1
2
3
4
5
7
8
9
11
6
10
12
60
90
Insert 100
85
70
20
50
10
40
30
80
4.
private void
ensureCapacity()
{
if
(lastIndex >= heap.length)
heap = Arrays.copyOf(heap, 2 * heap.length);
}
// end ensureCapacity
5.
public
void
add(T newEntry)
{
lastIndex++;
ensureCapacity();
heap[0] = newEntry;
// sentinel
int
newIndex = lastIndex;
int
parentIndex = newIndex / 2;
while
(newEntry.compareTo(heap[parentIndex]) > 0)
{
heap[newIndex] = heap[parentIndex];
newIndex = parentIndex;
parentIndex = newIndex / 2;
}
// end while
heap[newIndex] = newEntry;
}
// end add