IN C++ CODING In this assignment, you are given several classes in the cpp file
ID: 3710507 • Letter: I
Question
IN C++ CODING
In this assignment, you are given several classes in the cpp file "Heap.cpp". Your task is to complete the implementation of the classes specified as below. You need to submit a single cpp file that contains everything. 1 Your Task You are given a class "TNode" that contains one integer value, and three pointers one to the parent, one to the left child, and one to the right child. You need to complete the class "minHeap" and other functions specified in the cpp file. Task 1: Implement the constructors (default and copy) of Heap. You need to make sure that the copy constructor makes a separate copy of the heap. Task 2: Implement in, removemin, getmin. Note: .getmin returns the pointer to the min element, but do not modify the heap. On the other hand, removemin just deletes the min element from the heap. . In this homework, I request that the in function takes input "const TNode t", which means you cannot modify the input node t. You should create a new node (different from the input node t) and then add into the heap . It is highly recommended to write helper functions, such as bubble-up and bubble-down. If you don't know what they are, you should review heap. Task 3: Implement Heapify that takes input a binary tree, and makes a heap from the binary tree. Here your binary tree is in the array form. You cannot modify the array Task 4: Implement Heapsort that takes input an array of size n, and returns a sorted array. Task 5: Design a test function of your own design. Test everything!Explanation / Answer
Heapsort in c++
///////////////////////////////////////////////////////////////////////////////////////////////
// C++ program for implementation of Heap Sort
#include <iostream>
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 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);
}
}
// 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 << " ";
}
// Driver program
int main()
{
int arr[] = {12, 11, 13, 5, 6, 7};
int n = sizeof(arr)/sizeof(arr[0]);
heapSort(arr, n);
cout << "Sorted array is ";
printArray(arr, n);
}
/////////////////////////////////////////////////////////////////////