Java Reference
In-Depth Information
figure 21.8
The remaining two
steps required to
insert 14 in the
original heap shown in
Figure 21.7
14
14
13
13
16
14
16
24
21
19
68
24
21
19
68
65
26
32
31
65
26
32
31
(a)
(b)
1
/**
2
* Adds an item to this PriorityQueue.
3
* @param x any object.
4
* @return true.
5
*/
6
public boolean add( AnyType x )
7
{
8
if( currentSize + 1 == array.length )
9
doubleArray( );
10
11
// Percolate up
12
int hole = ++currentSize;
13
array[ 0 ] = x;
14
15
for( ; compare( x, array[ hole / 2 ] ) < 0; hole /= 2 )
16
array[ hole ] = array[ hole / 2 ];
17
array[ hole ] = x;
18
19
return true;
20
}
figure 21.9
The
add
method
Line 16 moves the item in the parent down into the hole, and then the third
expression in the
for
loop moves the hole up to the parent. When the loop ter-
minates, line 17 places
x
in the hole.
The time required to do the insertion could be as much as
O
(log
N
) if the
element to be inserted is the new minimum. The reason is that it will be perco-
lated up all the way to the root. On average the percolation terminates early: It
has been shown that 2.6 comparisons are required on average to perform the
add
, so the average
add
moves an element up 1.6 levels.
Insertion takes con-
stant time on aver-
age but logarithmic
time in the worst
case.
Search WWH ::
Custom Search