In C++ Language, and include header file if possible. Create a Heap (min or max,
ID: 3605174 • Letter: I
Question
In C++ Language, and include header file if possible. Create a Heap (min or max, your choice) class containing the standard functionality of insertion and removal. Use a dynamically-allocated array for storage of your heap, allowing the heap to grow as needed (no reduction of size is required In addition, this heap allows the user to "flush" a value from the heap. In other words, the user supplies a value and the heap removes all instances of that value automatically. Because this is a structure with dynamic memory in C++, you must include the memory management methods. In your driver, test the heap by: 1) Inserting more than the default size number of values(to test insertion and resize) Removing the next value and printing it to the screen (to test remove) "Flushing" a given value from the heap, then removing and printing values until it is clear the flushed value has been removed (to test flush) 2) 3) Note that you must know a value is on the heap to know if your flush method removed it. Consequently, you must either insert one (or more) known values on the heap, or track one (or more) of the random values.Explanation / Answer
#include <iostream>
using namespace std;
void MaxHeapify(int a[], int i, int n)
{
int j, temp;
temp = a[i];
j = 2*i;
while (j <= n)
{
if (j < n && a[j+1] > a[j])
j = j+1;
if (temp > a[j])
break;
else if (temp <= a[j])
{
a[j/2] = a[j];
j = 2*j;
}
}
a[j/2] = temp;
return;
}
void HeapSort(int a[], int n)
{
int i, temp;
for (i = n; i >= 2; i--)
{
temp = a[i];
a[i] = a[1];
a[1] = temp;
MaxHeapify(a, 1, i - 1);
}
}
void Build_MaxHeap(int a[], int n)
{
int i;
for(i = n/2; i >= 1; i--)
MaxHeapify(a, i, n);
}
int main()
{
int n, i;
cout<<" Enter the number of data element to be sorted: ";
cin>>n;
n++;
int arr[n];
for(i = 1; i < n; i++)
{
cout<<i<<" "<<flush;
cin>>arr[i];
}
Build_MaxHeap(arr, n-1);
HeapSort(arr, n-1);
cout<<" Sorted Data ";
for (i = 1; i < n; i++)
cout<<"->"<<arr[i];
return 0;
}