algorithm - Build Heap Procedure.

Question

An array of integers of size n can be converted into a heap by adjusting the heaps rooted at each internal node of the complete binary tree starting at the node ?(n?1)/2? and doing this adjustment up to the root node (root node is at index 0) in the order ?(n?1)/2, ?(n?3)/2?, ....., 0.

==========================================================================

I know, it's a Build Heap procedure and takes O(n) time, but can someone please make me visualise by taking a array with small value of n to show how things are working?

Answer 1

Let's do an example with the array [7, 3, 9, 1, 2, 4, 8, 5, 6, 0]. The tree structure is:

         7
    3         9
  1   2     4   8
 5 6 0

There are 10 items in the heap. So, starting at index (n/2)-1 (the first non-leaf node), we see that the value 2 is greater than its one child. We swap, giving:

         7
    3         9
  1   0     4   8
 5 6 2

Next, 1 is smaller than its children, so we leave it alone.

9 is larger than both of its children. The rule is that you swap it with its smallest child, giving:

         7
     3       4
   1   0   9   8
  5 6 2

3 is larger than both of its children, so swap it with 0. It's also larger than 2, so we do another swap. The result is:

         7
     0       4
   1   2   9   8
  5 6 3

Finally, 7 is larger than 0, so we swap it, placing 0 at the root. 7 is also larger than its two children, so we swap it with 1. And 7 is larger than 5 and 6, so we swap it to the leaf level. The result is:

         0
     1       4
   5   2   9   8
  7 6 3

Which is a valid min-heap.