You need to define the following data types ELEMENT is a data type that contains
ID: 3804869 • Letter: Y
Question
You need to define the following data types ELEMENT is a data type that contains a field named key, which is of type int. In later assignments, you will have to add on other fields to ELEMENT, without having to change the functions. Note that ELEMENT should not be of type int. HEAP is a data type that contains three fields named capacity (of type int), size (of type int), and H (an array of type ELEMENT with index ranging from 0 to capacity). The functions that you are required to implement are Initialize(n) which returns an object of type HEAP with capacity n and size 0. BuildHeap(heap, A), where heap is a HEAP object and A is an array of type ELEMENT. This function copies the elements in A into heap- H and uses the linear time build heap algorithm to obtain a heap of size size(A). Insert(heap, k) which inserts an element with key equal to k into the min-heap heap. o DeleteMin(heap) which deletes the element with minimum key and returns it to the caller. DecreaseKey(heap, element, value) which decreases the key field of element to value, if the latter is not larger than the former. Note that you have make necessary adjustment to make sure that heap order is maintained. print Heap(heap) which prints out the heap information, including capacity, size, and the key fields of the elements in the array with index going from 1 to sizeExplanation / Answer
# include<iostream>
using namespace std;
struct element {
int key;
};
struct heap {
int capacity;
int size;
struct element *H;
heap(int c) {
capacity=c;
H=(element*)malloc(sizeof(element)*capacity);
size=0;
}
};
heap *myheap;
int A[1001];
void readfile() {
FILE *f=fopen("HEAPinput.txt","r");
if(!f) {
return;
}
char line[10];
int k,p=1;
while(fgets(line,10,f)!=NULL) {
k=atoi(line);
A[p++]=k;
}
myheap->size=p-1;
}
void initialize(int k) {
myheap=new heap(k);
}
void min_heapify(int i,int n) {
int j, temp;
temp = myheap->H[i].key;
j = 2 * i;
while (j <= n) {
if (j < n && myheap->H[j+1].key < myheap->H[j].key)
j = j + 1;
if (temp < myheap->H[j].key)
break;
else if (temp >= myheap->H[j].key) {
myheap->H[j/2].key = myheap->H[j].key;
j = 2 * j;
}
}
myheap->H[j/2].key = temp;
return;
}
void build_minheap(int n) {
for(int i = n/2; i >= 1; --i) {
min_heapify(i,n);
}
}
void startheap() {
int n=myheap->size;
for(int i=1;i<=n;++i) {
myheap->H[i].key=A[i];
}
build_minheap(n);
}
void insertElement(int k) {
myheap->H[myheap->size].key=k;
myheap->size+=1;
build_minheap(myheap->size);
}
void deleteElement() {
for(int i=1;i<myheap->size;++i) {
myheap->H[i].key=myheap->H[i+1].key;
}
myheap->size-=1;
build_minheap(myheap->size);
}
void insertAtIndex(int k, int id) {
myheap->H[id].key-=k;
build_minheap(myheap->size);
}
void writetostd() {
for(int i=1;i<=myheap->size;++i) {
cout<<myheap->H[i].key<<" ";
}
cout<<endl;
}
int main() {
int n,k,id;
char c;
int f=1;
while (true) {
if(!f) break;
cin>>c;
switch (c) {
case 'S':
f=0;
break;
case 'C':
cin>>n;
initialize(n);
break;
case 'R':
readfile();
startheap();
break;
case 'W':
writetostd();
break;
case 'I':
cin>>k;
insertElement(k);
break;
case 'D':
deleteElement();
break;
case 'K':
cin>>id>>k;
insertAtIndex(k,id);
break;
default:
break;
}
}
}
Related Questions
drjack9650@gmail.com
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.