This has to be done in C++ Test case 1 Command.txt C 7 R W I 4 W D W K 3 1 W S H
ID: 3807015 • Letter: T
Question
This has to be done in C++
Test case 1
Command.txt
C 7
R
W
I 4
W
D
W
K 3 1
W
S
HEAPinput.txt
7
8
7
5
2
3
6
9
Expectedoutput.txt
heap size: 7
heap capacity: 7
2 3 5 7 8 6 9
Could not insert key, heap is full.
heap size: 7
heap capacity: 7
2 3 5 7 8 6 9
delete 2
heap size: 6
heap capacity: 7
3 7 5 9 8 6
heap size: 6
heap capacity: 7
1 7 3 9 8 6
Test case 2
command.txt
C 1000
R
W
HEAPinput.txt
1001
0
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74...
998
999
1000
output.txt
heap size: 1001
heap capacity: 1001
0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 ... 999 1000
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 Delete Min(heap) which deletes the element with minimum key and returns it to the caller. DecreaseKeyCheap, 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 size.Explanation / Answer
I have given all functions as you mentioned. Here i called only four funtion in the driver program. you can modify as per requirments.
include<iostream>
typedef int Element;
Element key;
class Heap{
int capcity;
int size;
Element[] h;
Public Initialize(int n){
Capcity = n;
h= new int[capcity];
Size=0;
h[0]=0;
}
Private int lchild(int pos)
{
return 2*pos;
}
Private int rchild(int pos){
return 2*pos+1;
}
Private int parent(int pos){
return pos/2;
}
Private Boolean isleaf(int pos){
return ((pos>size/2)&&(pos<=size));
}
Private void swap(int pos,int pos2){
Int tmp;
Tmp =hpos1];
H[pos1]=h[pos2];
H[pos2]=tmp;
}
Public void insert(int ele){
Size++;
H[size]=ele;
Int cur=size;
While(h[cur]<h[par(cur)]){
Swap(cur,par(cur));
Cur=par(cur);
}
}
Public void print(){
Int I;
For(i=1; i<=size;i++)
{
cout<<h[i]+” “);
}
Public int delete(){
Swap(1,size); size--;
If(size!=0)
Pushdown(1);
Return h[size+1];
}
Private void pushdown (int pos){
Int schild;
While(!isleaf(pos){
Schild =lchild(pos);
If((schild<size)&&(h[schild]>h[schild+1]))
Schild=schild+1;
If(h[pos]<= h[schild])
Return;
Swap(pos,schild);
Pos=schild;
}
}
Public void min()
{
Cout<<”the minimum value is”+h[1];
}
}
Void main()
{
Heap hp = new Heap();
Char c; int k;
Cout<<”Minimum Heap”;
do{
Cout<<”Enter your option”;
Cout<<”Inserts element press ‘I’ with key”;
Cout<<”To initialize heap capacity enter ‘C’ with capcity”;
Cout<<”To writ heap information press ‘W’”;
Cout<<”To Read file from heap ‘R’”;
Cout<<”To Delete minimum element press ‘D’”;
Cout<<”To Stop program ‘S’”;
}
Cin>>c;
Switch(c)
{
Case ‘I’:
cin >> k;
hp.insert(k);
break;
case ‘C’:
cin>>n; hp.initialize(n); break;
case’D’:
hp.delete(); break;
case 'S':
exit;
break;
case 'R':
hp.print();
break;
}
}
Related Questions
drjack9650@gmail.com
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.