Page 262 - DCAP407_DATA_STRUCTURE

Unit 14: Heaps

Step 1: Exchange the root’s key with the last key K of the heaps as shown in the figure 14.10.
Figure 14.10: Exchanging the Root Key with the Last
Key

Step 2: Decrease the heap’s size by 1 (Refer figure 14.11).
Figure 14.11: Delete the Key Having the Original Root
Key

Step 3: “Heapify” the smaller tree by shifting K down the tree as we did in the bottom-up heap
construction algorithm. That is, verify the parental dominance for K and if it holds, we complete the
process (Refer figure 14.12). If not, swap K with the largest of its children and repeat this operation until
the parental dominance condition holds for K in its new position.

Figure 14.12: Heapified Tree

We can determine the efficiency of deletion by the number of key comparisons required to “heapify”
the tree after the swap is done, and the size of the tree is decreased by 1. Since it does not need more key
comparisons than twice the heap’s height, the time efficiency of deletion is in O(log n).

Name some applications of heap.

14.4 Heap Sort

A heap is used to implement heapsort. Heapsort uses the data structure max-heap which is a complete
binary tree where the element at any node is greater than its children. Heapsort is a comparison-based

LOVELY PROFESSIONAL UNIVERSITY 255