Answer to Question #143180 in Algorithms for Michael

Question

What is the MAXimum number of comparisons between heap elements required to construct a max heap of 12 elements using the O(n) BuildHeap(array)?

Answer 1

From the below program of max heap, we can conclude that it can compare maximum n+1 times, here n is 9, so maximum number of comparison will be 10.

#include <iostream>

using namespace std;

void heapify(int arr[], int n, int i)
{
    int largest = i;
    int l = 2 * i + 1;
    int r = 2 * i + 2;
    int x=0;

    // If left child is larger than root
    if (l < n && arr[l] > arr[largest]){
        largest = l;

            x=++x;
        cout << x << " ";

    }
    if (r < n && arr[r] > arr[largest]){
        largest = r;
            x=++x;
        cout << x << " ";

    }

    if (largest != i) {
        
        swap(arr[i], arr[largest]);
    

        heapify(arr, n, largest);
    }
}


void buildHeap(int arr[], int n)
{
    // Index of last non-leaf node
    int startIdx = (n / 2) - 1;

    for (int i = startIdx; i >= 0; i--) {
        heapify(arr, n, i);
    }
}

void printHeap(int arr[], int n)
{
    cout << "Array representation of Heap is:\n";

    for (int i = 0; i < n; ++i)
        cout << arr[i] << " ";
    cout << "\n";
}

// Driver Code
int main()
{
    int arr[] = { 1,2, 3, 4, 5, 6,7,8,9};
    int n = sizeof(arr) / sizeof(arr[0]);
    buildHeap(arr, n);
    printHeap(arr, n);
    return 0;
}