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 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>
#include <stdio.h>
using namespace std;
int heapify(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 0;
}

int main()
{
int big, temp, a[20], n, i, j, ch;
std::cout<<" Enter the array size: ";
std::cin>>n;
std::cout<<" Enter the elements in an array: ";
for(i=0; i<n; i++)
{
std::cin>>a[i];
}
for(i=0; i<n; i++)
{
std::cout<<a[i] <<" ";
}
std::cout<<" Select an Operation: ";
std::cout<<" 1. Insert an number ";
std::cout<<" 2. Delete a max";
std::cout<<" 3. Sorting";
std::cin>>ch;
switch(ch)
{
case 1:
std::cout<<" Insert a number: ";
std::cin>>a[i];
std::cout<<" The Array elements are: ";
for(i=0; i<=n; ++i)
{
std::cout<<a[i] <<" ";
}
break;
case 2:
big = a[0];
for(i=0; i<n; i++)
{
if(big < a[i])
{
big = a[i];
}
}
std::cout<<" Delete Maximum number";
std::cout<<" Maximum number: " <<big;
for(i=0; i<n; ++i)
{
if(a[i] == big)
{
for(int j=i; j<n-1; j++)
{
a[j] = a[j+1];
}
temp++;
break;
}
}
std::cout<<" The Array elements are: ";
for(i=0; i<n-1; i++)
std::cout<<a[i] <<" ";
break;
case 3:
std::cout<<" Heap sort: ";
for(i=n-1; i>0; i--)
{
int num = a[i];
a[i] = a[0];
a[0] = num;
heapify(a, 1, i -1);
}
for(i=0; i<n; i++)
{
std::cout<<a[i] <<" ";
}
break;   
}
}

OUTPUT

Enter the array size: 5
Enter the elements in an array: 3 2 5 4 1
Select an Operation: 1
1. Insert an number
2. Delete a max
3. Sorting
Insert a number: 6
The Array elements are: 3 2 5 4 1 6

Enter the array size:
Enter the elements in an array: 3 2 5 4 1
Select an Operation: 2
1. Insert an number
2. Delete a max
3. Sorting
Delete Maximum number
Maximum number: 5
The Array elements are: 3 2 4 1

Enter the array size: 5
Enter the elements in an array: 3 2 5 4 1
Select an Operation: 3
1. Insert an number
2. Delete a max
3. Sorting
Heap sort: 2 5 4 1 3

Related Questions

Navigate

• Browse (All)
• Browse W
• Subjects

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