heap using stl code example

Example 1: max heap in c++

priority_queue <int> maxHeap;

Example 2: 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;
}

Tags:

Cpp Example