Java Reference
In-Depth Information
8.3.3 Removing the topmost element
We have previously seen that the maximal element is at the root of the heap.
Let us explain now how to remove and update the heap. When we remove the
maximal element located at the root (index 0 of the array), we choose the last
inserted node and put this node at the the root position. We now similarly
have to again ensure the heap property by eventually performing swapping
operations: If the value of the current root node is below the value of its right
child (the right subtree has less or exactly as many children as the left tree by
construction), then we swap that node with the selected child, and reiterate
until we reach the heap property. Figure 8.4 depicts these swapping operations
when removing the topmost element.
37
17
25
25
31
31
25
31
22
16
22
2 3
16
2 3
22
16
2 3
17
17
9
9
17
17
12
6
12
9
6
12
6
31
31
17
25
23
25
16
22
2 3
16
22
2
17
12
12
9
6
9
12
12
6
The heap property is now satisfied!
Figure 8.4
Removing the maximal element of the heap: First, replace the
root by the last leaf node, and then potentially swap this node with its current
children until the heap property is recovered
The portion of code performing this removal operation in the array encoding
the heap is as follows:
Program 8.5
Removing the topmost element from the heap
static int
removeHeap(
int
element , Heap h)
h.
label
[0]=h.
label
[h. size
−
1];
h. size
−−
;
int
i=0,j ,k,tmp;
Search WWH ::
Custom Search