Write a C++ program called heap.cpp to conduct heap operations. When the program

Question

Write a C++ program called heap.cpp to conduct heap operations. When the program starts, it should read a sequence 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 homework, your heap should be implemented using a dynamic array.

The following presents a sample run of the program.

Enter numbers: 20 7 8 1 3

This is a heap.

Select an operation

    1: Insert a number

    2. Delete the max

    3. 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. Quit

2

Updated heap: 8 7 5 1 3

Select an operation

    1: Insert a number

    2. Delete the max

    3. Quit

2

Updated heap: 7 3 5 1

Select an operation

    1: Insert a number

    2. Delete the max

    3. Quit

3

Bye!

This is another sample run.

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. Quit

1

Enter a number: 100

Updated heap: 100 7 1 3

Select an operation

    1: Insert a number

    2. Delete the max

    3. Quit

3

Bye!

Explanation / Answer

#include<iostream>
using namespace std;
#include<vector>

vector<int> heap;

bool isHeap()
{
int l=heap.size();
for(int i=l-1;i>=0;i--)
{
if(i%2==0)
{
if(heap[(i/2)-1]<heap[i])
return false;
}
else
{
if(heap[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]<heap[i])
{
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]<heap[i])
{
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]<<" ";
}
}

deleteMax()
{
int l=heap.size();
cout<<l;
heap[0]=heap[l-1];
heap.pop_back();

for(int i=0;i<l;)
{
if(2*i+2<l-1)
{

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<<heap[i]<<" "<<i<<" ";
i=2*i+1;
}
else if(heap[2*i+2]>heap[2*i+1]&&heap[2*i+2]>heap[i])
{
int t=heap[i];
heap[i]=heap[2*i+2];
heap[2*i+2]=t;

cout<<heap[i]<<" "<<i<<" ";
i=2*i+2;
}
else break;
}

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<<heap[i]<<" "<<i<<" ";
i=2*i+1;
}
else break;
}
else break;
}
cout<<"Updated heap : ";
for(int i=0;i<l-1;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";
break;
}
}

return 0;
}

Related Questions

Navigate

• Browse (All)
• Browse W
• Subjects

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.