In this assignment you will be working with minheaps, and operations Insert, Del
ID: 3762616 • Letter: I
Question
In this assignment you will be working with minheaps, and operations Insert, Delete, and Change. Your input file consists of data items, together with some information which tells you what to do with them. Each data item is a real number. The size of the array can be taken to be 500.
The first character in each line of your input file tells you what operation to perform on the data item listed in that line. I stands for insert, D stands for delete, and C stands for change. P stands for printing the data during a POSTORDER traversal of the tree. For example, consider the following input file:
I1 I5 I7
PC 7 10
PI 10 I3
PC 10 20 P
Then, the output will be:
Note that to perform Change and Delete, you have to find the item first, and this requires a search. So C 10 20 means that your program searches for 10. If it finds it, it changes all occurrences of 10 to 20 and also adjusts the heap. Note further that we allow duplicates, so Change and Delete operations must change all occurrences of the data stored in the heap.
Explanation / Answer
Note: in question it is asked to write code for minheap but the output is for max heap
i have implimented min heap
if you want max heap then you can change the code for min_heapify and heapify codes accordingly
#include <iostream>
using namespace std;
void min_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;
}
void heapify(int *a,int n)
{
int j, temp;
temp = a[n/2];
j = (n/2) * 2;
while (j > 1)
{
if (j < n && a[j+1] < a[j])
j = j + 1;
if (temp < a[j])
break;
else if (temp >= a[j])
{
a[j] = a[j/2];
j = j/2;
}
}
a[j/2] = temp;
return;
}
void build_minheap(int *a, int n)
{
int i;
for(i = n/2; i >= 1; i--)
{
min_heapify(a,i,n);
}
}
int insert(int a[],int ele, int n )
{
if(n==500)
return 0;
a[n]=ele;
heapify(a,n);
return 1;
}
int delet(int a[], int ele, int n)
{
int i,j;
for(i=1,j=1;i<=n;i++){
if(a[i]!=ele)
{
a[j]=a[i];
j++;
}
}
build_minheap(a,j);
return j;
}
void change(int a[], int old, int nw, int n)
{
int i;
for(i=1;i<=n;i++)
{
if(a[i]==old)
a[i]=nw;
}
build_minheap(a,n);
}
void print(int a[], int n)
{
for(int i=1;i<=n;i++)
cout<<a[i]<<", ";
cout<<endl;
}
int main()
{
int i, x;
char c;
int o,l,n=0;
int a[200];
while(cin>>c)
{
if(c=='P')
print(a,n);
if(c=='D')
{
cin>>o;
n=delet(a,o,n);
}
if(c=='I')
{
cin>>o;
if(insert(a,o,n+1))
n++;
}
if(c=='C')
{
cin>>o;
cin>>l;
change(a,o,l,n);
}
}
// build_minheap(a, n);
cout<<"Min Heap ";
for (i = 1; i <= n; i++)
{
cout<<a[i]<<endl;
}
}