To insert an element say x, into the heap with n elements, we first
create a hole in position (n+1) and see if the heap property is violated
by putting x into the hole. If the heap property is not violated, then
we have found the correct position for x. Otherwise, we ``push-up'' or
``percolate-up'' x until the heap property is restored. To do this, we
slide the element that is in the hole's parent node into the hole, thus
bubbling the hole up toward the root. We continue this process until x
can be placed in the whole. See Figure 6.2
for an example.
 |
Worstcase complexity of insert is O (h) where h is the height of the heap. Thus insertions are O (log n) where n is the number of elements in the heap.
Deletemin
When the minimum is deleted, a hole is created at the root level. Since
the heap now has one less element and the heap is a complete binary tree,
the element in the least position is to be relocated. This we first do
by placing the last element in the hole created at the root. This will
leave the heap property possibly violated at the root level. We now ``push-down''
or ``percolate-down'' the hole at the root until the violation of heap
property is stopped. While pushing down the hole, it is important to slide
it down to the less of its two children (pushing up the latter). This is
done so as not to create another violation of heap property. See Figure
6.3.
It is easy to see that the worst-case running time of deletemin is O (log
n) where n is the number of elements in the heap.
 |