An Algorithm a Day: Build a max heap with input array

The bottom up tree growth from a seed is interesting!! But note that we start with the root. But a computer tree, has leaves at the bottom and roots at the top!! This never matches with a normal forest tree!!.. Bad design :D

   But the methodology in which a computer tree is constructed follows the same historical ways: bottom up, top down. For a heap, we need to construct a tree bottom up like how a natural forest tree grows. But you might shout out like leaves should be at the bottom!! where would you fit the leaves?

   We treat all the leaves as root in any bottom up traversal approach in computer algorithms. Since we grow from the bottom, we should get the leaves of a computer tree as input!!.. Since we only know the leaves, we should treat them as initial root obviously. The next input that we get might be assumed as the root of some of these leaves and the algorithm goes until you are left with only one root to process.

   This is the approach the build max heap algorithm follows. For understanding this fully, you should understand how a normal tree is converted to a max heap tree. [http://analgorithmaday.blogspot.com/2011/01/make-partial-max-heap-perfect-max-heap.html]

    The basic input to the max heapify algorithm is: the root of a tree. The tree can be already following or not following the max heap principle (parent > children). But max heapify traverses the full tree until it reaches a small tree in which parent > children. This basic principle can be used to build the heap.

    The interesting point in a heap is, its leaves will be always [n/2]+1, [n/2]+2,..n. For example, if size of the heap is n=10, then 6,7,8,9,10 are the leaves. If these indices are leaves, the next level indices which will all be roots which means [n/2]…1 are the remaining nodes which roots.

Read full article from An Algorithm a Day: Build a max heap with input array