-
Notifications
You must be signed in to change notification settings - Fork 0
/
Max Heap.cpp
97 lines (82 loc) · 2.17 KB
/
Max Heap.cpp
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
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
#include<iostream>
using namespace std;
/// Max Heap
const int Size=10;
struct node{
int arr[Size+1];
int n;
};
void show_heap(struct node *Node){
if(Node->n==0){ cout<<"Empty"<<endl; return; }
for(int i=1;i<=Node->n;i++) cout<<Node->arr[i]<<" ";
cout<<endl;
}
void insert_heap(int value,struct node *Node){
if(Size+1<Node->n){
cout<<"Overflow"<<endl;
}
else {
Node->n=Node->n+1;
Node->arr[Node->n]=value;
int temp=Node->n;
while(1){
if(temp==0||temp/2==0) break;
int parents=Node->arr[temp/2];
int child=Node->arr[temp];
if(parents<child){
swap(Node->arr[temp/2],Node->arr[temp]);
} else break;
temp/=2;
}
}
}
void delete_heap(struct node *Node){
if(Node->n==0){ cout<<"Empty! Can not delete"<<endl; return; }
swap(Node->arr[1],Node->arr[Node->n]);
Node->n=Node->n-1;
int parents=1;
int left_child=2*parents;
int right_child=(2*parents)+1;
if(Node->n<=2) return;
while(left_child<=Node->n){
cout<<left_child<<endl;
int Maxx=left_child;
if(right_child<=Node->n){
Maxx=max(Node->arr[left_child],Node->arr[right_child]);
}
if(Maxx==Node->arr[left_child]){
swap(Node->arr[parents],Node->arr[left_child]);
parents=left_child;
}
else if(right_child<=Node->n){
swap(Node->arr[parents],Node->arr[right_child]);
parents=right_child;
}
left_child=2*parents;
right_child=(2*parents)+1;
}
}
int main()
{
struct node *Node,d;
Node=&d;
Node->n=0;
cout<<"Enter The Operation"<<endl;
cout<<"1 for insertion"<<endl;
cout<<"2 for Deletion"<<endl;
cout<<"3 for Show Heap"<<endl;
cout<<"4 for Exit"<<endl;
while(1){
int operation;
cin>>operation;
if(operation==1){
int value;
cin>>value;
insert_heap(value,Node);
} else if(operation==2){
delete_heap(Node);
}else if(operation==3){
show_heap(Node);
} else return 0;
}
}