Page 259 - DCAP407_DATA_STRUCTURE

Data Structure

Figure 14.5 shows how checking for parental dominance continues.
Figure 14.5: Continue Checking for Parental
Dominance

This process continues until the parental dominance requirement for K is satisfied. After completing the
“heapification” of the sub-tree rooted at the current parental node, the algorithm continues to do the
same for the immediate predecessor of the node as shown in figure 14.5. In figure 14.5, the node with
value 9 is greater than its child nodes that have the values 6 and 4 and thereby holds the parental
dominance. Then, this node with value 9 is compared with the root value 2, which is lesser than 9 and
hence these two nodes are interchanged. The node with value 2 is lesser than its child nodes 6 and 4 and
thus, it is interchanged with the node having larger value 6. The algorithm stops after this is done for
the tree’s root to give the final heap in figure 14.6(i). The numbers above the nodes in the tree indicate
their position in the array which is shown in the figure 14.6(ii).

Figure 14.6: Heap and Array Representation

As the value of a node’s key does not change during the process of shifting the node down the tree, it
need not get involved in intermediate swaps. The empty nodes are swapped with the larger keys until a
final position is reached where it accepts the deleted value again.
Let us now study the algorithm for bottom-up heap construction.
Algorithm: Heap Bottom-up (H [1...n])
//Constructs a heap from the elements of a given array

// by the bottom-up algorithm
//Input: An array H[1..n] of orderable items
//Output: A heap H[1..n]

252 LOVELY PROFESSIONAL UNIVERSITY