Data Structures, Algorithms, & Applications in C++
Chapter 12, Exercise 13
Let y = heap[size].
When the element in heap[i] is removed from the
max heap, the size of the max heap decreases by
1 and we must insert y
back into the heap. Since the position heap[i]
is vacant, we try to put y into
heap[i]. We can put y
into heap[i] iff y <= heap[i/2]
and y >= max{heap[2*i], heap[2*i + 1]}
(assuming i is not the root and has two children).
Notice that at most one of these two conditions can be violated by
y.
When y is greater
than the element in the parent position, we use the strategy used
to insert an element into a max heap and follow the path from
i towards the root until we find the
place to put y.
When
y is smaller than one or both of the children
of i, we use the strategy used by
removeMax and follow a path from
i towards the leaves until we find the
place for y.