# Building Heaps from an array of keys

## Dry Run for Building a heap

• The size of the heap N = 11
• The number of leaves start from index N/2 + 1 = 6
• Hence we can consider all elements from index 6 to 11 each to be a max heap with just one node, hence the max heap property is intact.
• Let us start our loop from i = 5 to 1
• Children of index i(5) are indices 2i (10) and 2i+1 (11)
• if A[i] > A[2i] ( 3 > 10 or 3 > 5)
• No – hence there is a need to heapify A[5]. Doing that we will interchange it with either index 10 or 11,
• The heapify algorithm in the previous post swaps it with the key 10. (3 and 10 swap their places).
• This restores the max heap property till index 5 and the array looks as below:

• Now decrease the loop counter to i = 4 and repeat the same steps.
• Children of index i (4) are indices 2i (8) and 2i+1 (9)
• if A[i] > A[2i] ( 14 > 4 or 14 > 8 )
• Yes – hence this is already satisfying the max heap property and we need not do anything. Hence, the array doesn’t change.
• Now decrease the loop counter to i = 3 and repeat the same steps.
• Children of index i (3) are indices 2i (6) and 2i+1 (7)
• if A[i] > A[2i] ( 7 > 12 or 7 > 9 )
• No – hence there is a need to heapify A[3]. Doing that we will interchange it with either index 6 or 7.
• The heapify algorithm swaps it with the key 12. (12 and 7 swap their places).
• This restore the max heap property till index 3 and the array looks like below:
• This seems to restore the max heap property at index 3 and below.
• Now decrease the loop counter to i = 2 and repeat the same steps
• Children of index i (2) are indices 2i (4) and 2i+1 (5)
• if A[i] > A[2i] (2 > 14 or 2 > 10)
• No – hence there is a need to heapify A[2]. Doing that we will interchange it with either index 4 or 5.
• The heapify algorithm swaps it with the key 14. (14 and 2 swap their places)
• This restores the max heap property till index 2 and the array looks like below:
• Incidentally, the index 4 is now disturbed and it doesn’t satisfy the max heap property.
• Now we, need to run the heapify at A[4] and that will swap index 4 with index 9 (2 and 8 swap their positions)
• That restores the max heap property at index 4 and the array looks as below:
• Now decrease the loop counter to i = 1 and repeat the same steps
• Children of index i (1) are indices 2i (2) and 2i+1 (3)
• if A[i] > A[2i] (6 > 14 or 6 > 12)
• No – hence there is a need to heapify A[1]. Doing that we will interchange it with either index 2 or 3.
• The heapify algorithm swaps it with the key 14. (14 and 6 swap their places)
• This restores the max heap property till index 1 and the array looks like below:
• But now the index 2 doesn’t seem to satisfy the max heap property because the key stored at its children (indices 4 and 5) are bigger than the key at index 2 i.e. 6.
• Heapifying at index 2 will result in swapping 6 and 10 and the array will change to the below form:
• This now is completely satisfying the max heap property and the index of loop counter is 1, so the algorithm ends here.