Question

Design and analyze asymptotically a transform-conquer algorithm for the following problem:

• input: an array A[lo..hi] of n double numbers;
• output: an array representing the min-heap whose elements are elements of A.

Answer 1

A heap is typically represented as an array:

Below table shows indexes of other nodes for the i_th node, i.e., Arr[0]:

The algorithm for building a heap from an array:

while not end of array, 
        if heap is empty, 
                place item at root; 
        else, 
                place item at bottom of heap; 
                while (child > parent) 
                        swap(parent, child); 
        go to next array element; 
end

The number of operations required depends only on the number of levels the new element must rise to satisfy the heap property, thus the insertion operation has a worst-case time complexity of O(log n) but an average-case complexity of O(1).