Page 261 - DCAP407_DATA_STRUCTURE

Data Structure

14.2 Inserting into Heaps

To insert a new key into a heap, add a new node with key K after the last leaf of the existing heap. Then,
shift K up to its suitable place in the new heap. Consider inserting value 8 into the heap shown in the
figure 14.7.

Figure 14.7: Inserting 8 into Heap

Compare 8 with its parent key. Stop if the parent key is greater than or equal to 8. Else, swap these two
keys and compare 8 with its new parent (Refer to figure 14.8). This swapping continues until 8 is not
greater than its last parent or it reaches the root. In this algorithm too, we can shift up an empty node
until it reaches its proper position, where it acquires the value 8.
Figure 14.8: Check for Parental Dominance until Tree
is Balanced

This insertion operation does not require more key comparisons than the heap’s height. Since the height
of a heap with n nodes is about log2n, the time efficiency of insertion is in O(log n).
14.3 Deleting the Root of a Heap
The following steps show the method to delete the root key from a heap in the figure 14.9.

Figure 14.9: Sample Heap

254 LOVELY PROFESSIONAL UNIVERSITY