creating heap in c++ class
/*
HEAP CONSTRUCTION (BOTH MIN AND MAX)
AUTHOR: UTKARSH SINHA
*/
#include<bits/stdc++.h>
using namespace std;
void swap(int &a, int &b){
int temp = a;
a = b;
b = temp;
}
void print(vector<int> v){
for(auto x : v)
cout << x << " ";
cout << endl;
}
class Heap{
vector<int> heapElement;
int type;
int heapSize;
void siftDown(int idx, vector<int> &v);
void siftUp(int idx, vector<int> &v);
void minHeap(vector<int> &v);
void maxHeap(vector<int> &v);
public:
Heap(int type);
void buildHeap(vector<int> v);
void insert(int x);
int remove();
int top();
};
Heap::Heap(int type){
this->type = type;
if(this->type == 0) cout << "Min-Heap Created!\n";
else cout << "Max-Heap Created!\n";
}
void Heap::buildHeap(vector<int> v){
int n = v.size();
heapSize = n;
for(int i=n-1; i>=0; i--){
siftDown(i, v);
}
heapElement = v;
cout << "Build Done!\n";
}
void Heap::siftDown(int idx, vector<int>& v){
if(type == 0){
int j = 2 * idx + 1;
int n = heapSize;
while(j < n-1){
j = (v[j] < v[j+1]) ? j : j+1;
if(v[idx] > v[j]){
swap(v[idx], v[j]);
idx = j;
j = 2 * j + 1;
} else break;
}
} else {
int j = 2 * idx + 1;
int n = heapSize;
while(j < n-1){
j = (v[j] > v[j+1]) ? j : j+1;
if(v[idx] < v[j]){
swap(v[idx], v[j]);
idx = j;
j = 2 * j + 1;
} else break;
}
}
}
void Heap::siftUp(int idx, vector<int> &v){
if(type == 0){
int n = heapSize;
int temp = v[n-1];
while(idx > 0 && temp < v[idx/2]){
v[idx] = v[idx/2];
idx = idx/2;
}
v[idx] = temp;
} else {
int n = heapSize;
int temp = v[n-1];
while(idx > 0 && temp > v[idx/2]){
v[idx] = v[idx/2];
idx = idx/2;
}
v[idx] = temp;
}
}
void Heap::insert(int x){
heapElement.push_back(x);
heapSize++;
siftUp(heapSize-1, heapElement);
}
int Heap::remove(){
int temp = heapElement[0];
heapElement[0] = heapElement[heapSize-1];
heapSize--;
siftDown(0, heapElement);
return temp;
}
int Heap::top(){
return heapElement[0];
}
int main(){
vector<int> v = {102,117,18,12,31,8,30,23,44};
print(v);
Heap min_heap(0);
Heap max_heap(1);
min_heap.buildHeap(v);
max_heap.buildHeap(v);
cout << "Minimum Element: " << min_heap.top() << endl;
cout << "Maximum Element: " << max_heap.top() << endl;
min_heap.insert(2);
max_heap.insert(200);
cout << "Minimum Element: " << min_heap.top() << endl;
cout << "Maximum Element: " << max_heap.top() << endl;
min_heap.remove();
max_heap.remove();
cout << "Minimum Element: " << min_heap.top() << endl;
cout << "Maximum Element: " << max_heap.top() << endl;
min_heap.remove();
max_heap.remove();
cout << "Minimum Element: " << min_heap.top() << endl;
cout << "Maximum Element: " << max_heap.top() << endl;
return 0;
}
