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:img22

 

  • 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.img33
  • 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:img444
    • 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:img5
    • 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:img6
  • 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:img77
    • 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:img8
    • This now is completely satisfying the max heap property and the index of loop counter is 1, so the algorithm ends here.