Modify the following C++ code and make sure it runs EXACTLY like this sample run
ID: 3860303 • Letter: M
Question
Modify the following C++ code and make sure it runs EXACTLY like this sample run:
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!
Code to modify:
#include
using namespace std;
#include
std::vector heap;
bool isHeap()
{
int l=heap.size();
for(int i=l-1;i>=0;i--)
{
if(i%2==0)
{
if(heap[(i/2)-1] return false;
}
else
{
if(heap[i/2] return false;
}
}
return true;
}
void heapify()
{
int l=heap.size()-1;
int i=l;
while(i!=0)
{
if(i%2==0)
{
if(heap[(i/2)-1] {
int t=heap[i];
heap[i]=heap[(i/2)-1];
heap[(i/2)-1]=t;
i=(i/2)-1;
}
else break;
}
else
{
if(heap[i/2] {
int t=heap[i];
heap[i]=heap[(i/2)];
heap[(i/2)]=t;
i=(i/2);
}
else break;
}
}
cout<<"Updated heap : ";
for(i=0;i<=l;i++)
{
cout<
int deleteMax()
{
int l=heap.size();
cout< heap[0]=heap[l-1];
heap.pop_back();
for(int i=0;i {
if(2*i+2 {
if(heap[2*i+1]>heap[2*i+2]&&heap[2*i+1]>heap[i])
{
int t=heap[i];
heap[i]=heap[2*i+1];
heap[2*i+1]=t;
cout<
cout<
else if(2*i+1==l-2)
{
if(heap[2*i+1]>heap[i])
{
int t=heap[i];
heap[i]=heap[2*i+1];
heap[2*i+1]=t;
cout<
}
int main()
{
heap.push_back(20);//you may get this initial sequence scanned form the user
heap.push_back(7);
heap.push_back(8);
heap.push_back(1);
heap.push_back(3);
if(isHeap())cout<<"This is a heap ";
else cout<<"This is NOT a heap ";
int option;
while(1)
{
cout<<" Select an operation 1 Insert number 2 Delete the max 3 Quit ";
cin>>option;
if(option==1)
{
cout<<"Enter a number : ";
int num;
cin>>num;
heap.push_back(num);
heapify();
}
if(option==2)
{
deleteMax();
}
if(option==3)
{
cout <<"Bye";
break;
}
}
return 0;
}
Explanation / Answer
std::vector heap;
bool isHeap()
{
int l=heap.size();
for (int i=0; i<=(l-2)/2; i++)
{
// If left child is greater, return false
if (heap[2*i +1] > heap[i])
return false;
// If right child is greater, return false
if (heap[2*i+2] > heap[i])
return false;
}
return true;
}
void heapify()
{
int l=heap.size()-1;
int i=l;
while(i!=0)
{
if(i%2==0)
{
if(heap[(i/2)-1] {
int t=heap[i];
heap[i]=heap[(i/2)-1];
heap[(i/2)-1]=t;
i=(i/2)-1;
}
else break;
}
else
{
if(heap[i/2] {
int t=heap[i];
heap[i]=heap[(i/2)];
heap[(i/2)]=t;
i=(i/2);
}
else break;
}
}
cout<<"Updated heap : ";
for(i=0;i<=l;i++)
{
cout<<heap[i];
}
}
int deleteMax()
{
if (heap.size() == 0)
{
cout<<"Heap is Empty"<<endl;
return;
}
heap[0] = heap.at(heap.size() - 1);
pop_heap(heap.begin(), heap.end());
heapifydown(0);
cout<<"Element Deleted"<<endl;
}
void HeapSort()
{
int i, temp;
int n=heap.size;
for (i = n; i >= 2; i--)
{
// Storing maximum value at the end.
temp = heap[i];
heap[i] = heap[1];
heap[1] = temp;
// Building max heap of remaining element.
heapify();
}
for(int i=0;i<n;i++)
cout<<heap[i];
}
int main()
{
heap.push_back(20);//you may get this initial sequence scanned form the user
heap.push_back(7);
heap.push_back(8);
heap.push_back(1);
heap.push_back(3);
if(isHeap())cout<<"This is a heap ";
else cout<<"This is NOT a heap ";
int option;
while(1)
{
cout<<" Select an operation 1 Insert number 2 Delete the max 3 Quit ";
cin>>option;
if(option==1)
{
cout<<"Enter a number : ";
int num;
cin>>num;
heap.push_back(num);
heapify();
}
if(option==2)
{
deleteMax();
}
if(option==3)
{
cout <<"Bye";
HeapSort();
break;
}
}
return 0;
}
Related Questions
drjack9650@gmail.com
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.