 The average case is more complex to analyze, but it can be shown to asymptotically approach comparisons.The Build-Max-Heap function that follows, converts an array "A" which stores a complete
binary tree with "n" nodes to a max-heap by repeatedly using Max-Heapify in a bottom up manner.It is based on the observation that the array elements indexed by
, , ..., "n"
are all leaves for the tree (assuming that indices start at 1), thus each is a one-element heap.