## 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.
- 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.

Continue: Analysis of Heap Creation Algorithm