Question

We consider Heapsort to sort an array in decreasing order by using min-heaps.

1. State the min-heap property. Then, using the same notation as in the textbook, write pseudocode for the following functions (where A is the min-heap)

Then, using the same notation as in the textbook, write pseudocode for the following functions (where A is the min-heap):

2. Min-Heapify(A, i), which assumes that the binary trees rooted at Left(i) and Right(i) are min-heaps, but that A[i] may be larger than its children. Min-Heapify lets the value of A[i] float down so that the subtree rooted at i obeys the min-heap property.

3. Build-Min-Heap(A), which builds a min-heap on the input array A(overwriting it).

4. Heapsort(A), which sorts the array A in decreasing order, based on Min-Heapify and Build-Min-Heap.

5. State a loop invariant for Heapsort and use it to prove its correctness. Assume Min-Heapify and Build-Min-Heap are correct.

6. Give the runtime for Min-Heapify, Build-Min-Heap and Heapsort as a function of the array size n. Explain your answers.

Answer 1

// C++ program for implementation of Heap Sort

#include <bits/stdc++.h>

using namespace std;

// 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 smallest = i; // Initialize smalles as root

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

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

    // If left child is smaller than root

    if (l < n && arr[l] < arr[smallest])

        smallest = l;

    // If right child is smaller than smallest so far

    if (r < n && arr[r] < arr[smallest])

        smallest = r;

    // If smallest is not root

    if (smallest != i) {

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

        // Recursively heapify the affected sub-tree

        heapify(arr, n, smallest);

    }

}

// main function to do heap sort

void heapSort(int arr[], int n)

{

    // Build heap (rearrange array)

    for (int i = n / 2 - 1; i >= 0; i--)

        heapify(arr, n, i);

    // One by one extract an element from heap

    for (int i = n - 1; i >= 0; i--) {

        // Move current root to end

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

        // call max heapify on the reduced heap

        heapify(arr, i, 0);

    }

}

/* A utility function to print array of size n */

void printArray(int arr[], int n)

{

    for (int i = 0; i < n; ++i)

        cout << arr[i] << " ";

    cout << "\n";

}

// Driver program

int main()

{

    int a[] = { 4, 6, 3, 2, 9 };

    int n = sizeof(a) / sizeof(arr[0]);

    heapSort(a, n);

    cout << "Sorted array is \n";

    printArray(a, n);

}

Time complexity:It takes O(logn) for heapify and O(n) for constructing a heap. Hence, the overall time complexity of heap sort using min heap or max heap is O(nlogn)