Question

In C++,

Implement the heapafication operation. Do not re-implement the binary tree class. Simply create a funcntion that takes in a binary tree and heapafies it. Meaning it takes in a pointer to a binary tree and converts it into a heap. (You may choose max or min heap).

Answer 1

// To heapify a subtree rooted with node i which is

// an index in arr[]. n is size of heap

void heapify(int arr[], int n, int i)

{

    int largest = i; // Initialize largest as root

    int l = 2*i + 1; // left = 2*i + 1

    int r = 2*i + 2; // right = 2*i + 2

    // If left child is larger than root

    if (l < n && arr[l] > arr[largest])

        largest = l;

    // If right child is larger than largest so far

    if (r < n && arr[r] > arr[largest])

        largest = r;

    // If largest is not root

    if (largest != i)

    {

        swap(arr[i], arr[largest]);

        // Recursively heapify the affected sub-tree

        heapify(arr, n, largest);

    }

}