min heap c++ code example

Example 1: min heap in c++

priority_queue <int, vector<int>, greater<int>> minHeap;

Example 2: max heap in c++

priority_queue <int> maxHeap;

Example 3: min heap priority queue c++

#include<queue>
std::priority_queue <int, std::vector<int>, std::greater<int> > minHeap;

Example 4: max heap c++ stl;

// C++ program to show that priority_queue is by 
// default a Max Heap 
#include <bits/stdc++.h> 
using namespace std; 

// Driver code 
int main () 
{ 
	// Creates a max heap 
	priority_queue <int> pq; 
	pq.push(5); 
	pq.push(1); 
	pq.push(10); 
	pq.push(30); 
	pq.push(20); 

	// One by one extract items from max heap 
	while (pq.empty() == false) 
	{ 
		cout << pq.top() << " "; 
		pq.pop(); 
	} 

	return 0; 
}

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

Example 6: max heap c++

#include <iostream>
using namespace std;
void max_heap(int *a, int m, int n) {
   int j, t;
   t = a[m];
   j = 2 * m;
   while (j <= n) {
      if (j < n && a[j+1] > a[j])
         j = j + 1;
      if (t > a[j])
         break;
      else if (t <= a[j]) {
         a[j / 2] = a[j];
         j = 2 * j;
      }
   }
   a[j/2] = t;
   return;
}
void build_maxheap(int *a,int n) {
   int k;
   for(k = n/2; k >= 1; k--) {
      max_heap(a,k,n);
   }
}
int main() {
   int n, i;
   cout<<"enter no of elements of array\n";
   cin>>n;
   int a[30];
   for (i = 1; i <= n; i++) {
      cout<<"enter elements"<<" "<<(i)<<endl;
      cin>>a[i];
   }
   build_maxheap(a,n);
   cout<<"Max Heap\n";
   for (i = 1; i <= n; i++) {
      cout<<a[i]<<endl;
   }
}

Tags:

Cpp Example