Question

In: Computer Science

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

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.

Solutions

Expert Solution

// 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)


Related Solutions

(C++)Heapsort: Write C++ codes for heapsort. The input array is a random permutation of A={1, 2,...
(C++)Heapsort: Write C++ codes for heapsort. The input array is a random permutation of A={1, 2, 3, …, 99, 100}. You should write codes to generate and print the random permutation first.
Java : Modify the selection sort algorithm to sort an array of integers in descending order....
Java : Modify the selection sort algorithm to sort an array of integers in descending order. describe how the skills you have gained could be applied in the field. Please don't use an already answered solution from chegg. I've unfortunately had that happen at many occasion ....... ........ sec01/SelectionSortDemo.java import java.util.Arrays; /** This program demonstrates the selection sort algorithm by sorting an array that is filled with random numbers. */ public class SelectionSortDemo { public static void main(String[] args) {...
Sorting (merge) Sort the array (as in Part 2) using merge sort. Write the array content...
Sorting (merge) Sort the array (as in Part 2) using merge sort. Write the array content after each pass (i.e., from pass 1 to pass 9). Each pass is defined as the completion of one merge operation. Suppose an array contains the following integers: -1, 20, 10, -5, 0, -7, 100, -7, 30, -10. Sort the array using the following algorithms: selection sort, bubble sort, and insertion sort. For each algorithm, write the array content after each pass (i.e., from...
USING JAVA Almost sort the array using Merge Sort. Perform Merge Sort as usual except that...
USING JAVA Almost sort the array using Merge Sort. Perform Merge Sort as usual except that during the final merge, it is not necessary to merge all n elements, but only the elements in positions 1 to k.
Java language 1. Sort any 10 keys using Min Heap. 2. Sort any 10 keys using...
Java language 1. Sort any 10 keys using Min Heap. 2. Sort any 10 keys using Max Heap.
Java language 1. Sort any 10 keys using Min Heap. 2. Sort any 10 keys using...
Java language 1. Sort any 10 keys using Min Heap. 2. Sort any 10 keys using Max Heap.
Given an integer array sorted in non-decreasing order, there is exactly one integer in the array...
Given an integer array sorted in non-decreasing order, there is exactly one integer in the array that occurs more than 25% of the time. Return that integer. Input: arr = [1,2,2,6,6,6,6,7,10] Output:
Write a program in Java to sort the given array using merge sort, quick sort, insertion...
Write a program in Java to sort the given array using merge sort, quick sort, insertion sort, selection sort and bubble sort based on the input from the user which sorting technique they wanted to use. Get the array size, array elements from the user, and also display the sorted array along with the name of the sorting technique used.
java 2. Write a program to implement heapsort. Sort the following elements using your program. 6,...
java 2. Write a program to implement heapsort. Sort the following elements using your program. 6, 12, 34, 29, 28, 11, 23, 7, 0, 33, 30, 45
Write a program to sort the following using HeapSort. Use any language you want. A=[10, 8,...
Write a program to sort the following using HeapSort. Use any language you want. A=[10, 8, 7, 9,16, 14, 3, 2, 4, 1]
ADVERTISEMENT
ADVERTISEMENT
ADVERTISEMENT