Next:6.1.2 Creating HeapUp:6.1 Binary HeapsPrevious:6.1 Binary Heaps

## 6.1.1 Implementation of Insert and Deletemin

Insert

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.

Next:6.1.2 Creating HeapUp:6.1 Binary HeapsPrevious:6.1 Binary Heaps
eEL,CSA_Dept,IISc,Bangalore