Write a C++ program called heap.cpp to conduct heap operations. When the program
ID: 3859904 • Letter: W
Question
Write a C++ program called heap.cpp to conduct heap operations. When the program starts, it should read a set of numbers from a user. After that, your program should display if it’s a heap or not. If it’s not a heap, your program should construct a heap with the numbers. Then, your program should conduct heap operation(s). For the program, your heap should be implemented using a dynamic array.
The following presents a sample run of the program.
Input size: 5
Enter numbers: 20 7 8 1 3
This is a heap.
Select an operation
1: Insert a number
2. Delete the max
3. Heapsort & Quit
1
Enter a number: 5
Updated heap: 20 7 8 1 3 5
Select an operation
1: Insert a number
2. Delete the max
3. Heapsort & Quit
2
Updated heap: 8 7 5 1 3
Select an operation
1: Insert a number
2. Delete the max
3. Heapsort & Quit
2
Updated heap: 7 3 5 1
Select an operation
1: Insert a number
2. Delete the max
3. Heapsort & Quit
3
Heapsort: 7 5 3 1
Bye!
This is another sample run:
Input size: 3
Enter numbers: 1 3 7
This is NOT a heap.
Heap constructed: 7 3 1
Select an operation
1: Insert a number
2. Delete the max
3. Heapsort & Quit
1
Enter a number: 100
Updated heap: 100 7 1 3
Select an operation
1: Insert a number
2. Delete the max
3. Heapsort & Quit
3
Heapsort: 100 7 3 1
Bye!
Explanation / Answer
#include<iostream>
using namespace std;
int change=0,u=0;
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])
{
change=1;
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);
}
if(change==0,u==0)
cout<<"This is a Heap";
else if(change==1,u==0)
{
cout<<"This is NOT a Heap"<<endl;
cout<<"Heap constructed:";
for(i=0;i<=n;i++)
{
cout<<a[i];
}
}
else
{
cout<<"Updated Heap is:";
for(i=0;i<=n;i++)
{
cout<<a[i];
}
}
}
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<<"Enter element "<<i<<": ";
cin>>arr[i];
}
// Building max heap.
Build_MaxHeap(arr,n-1);
HeapSort(arr,n-1);
while(1)
{
int ch;
cout<<"select an option";
cout<<"1.Insert a number"<<endl;
cout<<"2.Delete the max"<<endl;
cout<<"3.Heapsort & Quit"<<endl;
cin>>ch;
if(ch==1)
{
cout<<"enter number";
cin>>arr[n];
n++;
u=1;
Build_MaxHeap(arr,n-1);
}
else if(ch==2)
{
arr[0]=arr[n-1];
n--;
u=1;
Build_MaxHeap(arr,n-1);
}
else
{
cout<<" Sorted Data ";
for (i=1;i<n;i++)
cout<<arr[i];
exit(1);
}
}
return 0;
}
Related Questions
drjack9650@gmail.com
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.