Page 258 - DCAP407_DATA_STRUCTURE

Unit 14: Heaps

1. Heap data structure can be an n-ary tree.
2. Heap is not essentially sorted.

Draw a max heap and a min heap for the sequence (20, 13, 16, 8, 15, 4, 9, 3, 12, 18)

Architectural Approach of Heaps and Algorithms
The two principal ways to construct a heap are:
1. Bottom-up heap construction algorithm
2. Top-down heap construction algorithm
Let us now discuss the bottom-up heap construction.
Bottom-up Heap Construction
Bottom-up heap construction initializes the complete binary tree with n nodes by placing keys in the
given order and then “heapifies” the tree as follows. Starting with the last parental node and ending
with the root, the algorithm checks whether the parental dominance holds over the key at this node. If
the parental dominance condition is not met, the algorithm exchanges the node’s key with the larger
key of its children and checks for parental dominance of the key in its new position. This process
continues until the parental dominance for the key is satisfied. After the “heapification” of the sub-tree
rooted at the current parental node, the algorithm proceeds to do the same for the node’s immediate
predecessor.
If parental dominance does not hold over the key at a node, the algorithm exchanges the node’s key K
with the larger key of its children and checks whether the parental dominance holds for K in its new
position (Refer figures 14.4 and 14.5). In figure 14.4, the node with value 7 is lesser than its child node
that has the value 8. Hence these two nodes are interchanged.
Figure 14.4: Checking for Parental Dominance

LOVELY PROFESSIONAL UNIVERSITY 251