-
Notifications
You must be signed in to change notification settings - Fork 47
/
Copy pathBinary Heap Operations
139 lines (121 loc) · 3 KB
/
Binary Heap Operations
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
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
// Initial Template for C++
#include <bits/stdc++.h>
using namespace std;
typedef long long int ll;
// Structure for Min Heap
struct MinHeap {
int *harr;
int capacity;
int heap_size;
// Constructor for Min Heap
MinHeap(int c) {
heap_size = 0;
capacity = c;
harr = new int[c];
}
~MinHeap() { delete[] harr; }
int parent(int i) { return (i - 1) / 2; }
int left(int i) { return (2 * i + 1); }
int right(int i) { return (2 * i + 2); }
void MinHeapify(int); // Implemented in user editor
int extractMin();
void decreaseKey(int i, int new_val);
void deleteKey(int i);
void insertKey(int k);
};
// Position this line where user code will be pasted.
// Driver code
int main() {
int t;
cin >> t;
while (t--) {
ll a;
cin >> a;
MinHeap h(a);
for (ll i = 0; i < a; i++) {
int c;
int n;
cin >> c;
if (c == 1) {
cin >> n;
h.insertKey(n);
}
if (c == 2) {
cin >> n;
h.deleteKey(n);
}
if (c == 3) {
cout << h.extractMin() << " ";
}
}
cout << endl;
// delete h.harr;
h.harr = NULL;
}
return 0;
}
// } Driver Code Ends
/*The structure of the class is
struct MinHeap
{
int *harr;
int capacity, heap_size;
MinHeap(int cap) {heap_size = 0; capacity = cap; harr = new int[cap];}
int extractMin();
void deleteKey(int i);
void insertKey(int k);
int parent(int i);
int left(int i);
int right(int i);
};*/
// You need to write code for below three functions
/* Removes min element from min heap and returns it */
int MinHeap :: extractMin()
{ if(heap_size == 0)
return -1;
int a = harr[0];
swap(harr[0],harr[heap_size-1]);
heap_size--;
MinHeapify(0);
return a;
}
/* Removes element from position x in the min heap */
void MinHeap :: deleteKey(int i)
{ if(i<0 || i>=heap_size)
return;
decreaseKey(i,INT_MIN);
extractMin();
}
/* Inserts an element at position x into the min heap*/
void MinHeap ::insertKey(int k)
{
if(heap_size == capacity)
return;
harr[heap_size] = INT_MAX;
heap_size++;
decreaseKey(heap_size-1,k);
}
// Decrease Key operation, helps in deleting key from heap
void MinHeap::decreaseKey(int i, int new_val)
{
harr[i] = new_val;
while (i != 0 && harr[parent(i)] > harr[i])
{
swap(harr[i], harr[parent(i)]);
i = parent(i);
}
}
/* You may call below MinHeapify function in
above codes. Please do not delete this code
if you are not writing your own MinHeapify */
void MinHeap::MinHeapify(int i) {
int l = left(i);
int r = right(i);
int smallest = i;
if (l < heap_size && harr[l] < harr[i]) smallest = l;
if (r < heap_size && harr[r] < harr[smallest]) smallest = r;
if (smallest != i) {
swap(harr[i], harr[smallest]);
MinHeapify(smallest);
}
}