In heap sort, another new term called Heapify is used. Heapify is a method of converting the binary tree to a Max/Min heap.
How can we do heapify? What are the steps?
Assumption: Array of integers are passed to do heapify. This array of integers are representing a binary tree where node ith children are placed at 2*i and 2*i + 1 positions.
Node 0’th key = 11, its children node 1 (22) and node 2 (23)
Node 1’th key = 22, its children node 3 (8) and node 4(12)
Node 2’th key = 23, its children node 5 (19) and node 6(4)
Node 3’th key = 8, its child node 7 (14).
Basically, the child with the min value of the key is swapped with the node key value. This is repeated for all the nodes.
We have to follow the bottom-up approach as the key values of children are compared with the nodes’ (or parents’ ) key values. If there is a change in a node, repeat the heapify procedure for its subtrees.
Let’s build the min-heap using heapify to the above binary tree:
- Step 1: Total number of elements = 8, 8/2 = 4,
- Step 2: Start the heapify procedure from index (4–1) index 3.
- Step 3: 8 < 14, no change required.
- Step 4: heapify at index 2: 23 > min(19, 4) → swap node 2 with node 6.
- Step 5: Node 6 not having children, so proceed.
- Step 6: node 1 key 22 > min (8, 12) → swap the node 1 with node 3:
- Step 7: node 3 having children, repeat the procedure with a subtree of node 3.
- Step 8: node 0 key 11 > min (8,4) → swap node 0 with node 2:
- Step 9: Repeat the heapify procedure for node 2.
Basically, applying heapify procedure for each node with children in bottom-up procedure:
Get the bottom parent index (p) (total number of nodes/2 -1)
For ii = p to 0
Begin
Heapify (array, ii)
End
Heapify procedure with a given index n:
Checking the node n key value with its min (children nodes 2*n and 2*n+1)
Min node = min (children nodes 2*n and 2*n+1) key values
If Min node key value < node n key value
Begin
Swap (node n, min node)
Heapify(array, min node)
End
