priority queue c++ max heap code example

Example 1: min heap priority queue c++

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

Example 2: priority queue min heap

#include <bits/stdc++.h>
using namespace std;
 
// User defined class, Point
class Point
{
   int x;
   int y;
public:
   Point(int _x, int _y)
   {
      x = _x;
      y = _y;
   }
   int getX() const { return x; }
   int getY() const { return y; }
};
 
// To compare two points
class myComparator
{
public:
    int operator() (const Point& p1, const Point& p2)
    {
        return p1.getX() > p2.getX();
    }
};
 
// Driver code
int main ()
{
    // Creates a Min heap of points (order by x coordinate)
    priority_queue <Point, vector<Point>, myComparator > pq;
 
    // Insert points into the min heap
    pq.push(Point(10, 2));
    pq.push(Point(2, 1));
    pq.push(Point(1, 5));
 
    // One by one extract items from min heap
    while (pq.empty() == false)
    {
        Point p = pq.top();
        cout << "(" << p.getX() << ", " << p.getY() << ")";
        cout << endl;
        pq.pop();
    }
 
    return 0;
}

Example 3: create a min heap in java using priority queue

int arr[]={1,2,1,3,3,5,7};
        PriorityQueue<Integer> a=new PriorityQueue<>();
        for(int i:arr){
            a.add(i);
        }
        while(!a.isEmpty())
            System.out.println(a.poll());

Example 4: 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 5: priority queue cpp

// using GCC 10.2 (C++2a) compiler
#include <functional>
#include <queue>
#include <vector>
#include <iostream>
 
template<typename T> void print_queue(T& q) {
    while(!q.empty()) {
        std::cout << q.top() << " ";
        q.pop();
    }
    std::cout << '\n';
}
 
int main() {
    std::priority_queue<int> q;
 
    for(int n : {1,8,5,6,3,4,0,9,7,2})
        q.push(n);
 
    print_queue(q);
 
    std::priority_queue<int, std::vector<int>, std::greater<int> > q2;
 
    for(int n : {1,8,5,6,3,4,0,9,7,2})
        q2.push(n);
 
    print_queue(q2);
 
    // Using lambda to compare elements.
    auto cmp = [](int left, int right) { return (left ^ 1) < (right ^ 1); };
    std::priority_queue<int, std::vector<int>, decltype(cmp)> q3(cmp);
 
    for(int n : {1,8,5,6,3,4,0,9,7,2})
        q3.push(n);
 
    print_queue(q3);
 
}

Example 6: priority queue max heap in java

//Sol1
PriorityQueue<Integer> queue = new PriorityQueue<>(10, Collections.reverseOrder());


//Sol2
// PriorityQueue<Integer> pq = new PriorityQueue<>((x, y) -> y - x);
PriorityQueue<Integer> pq =new PriorityQueue<>((x, y) -> Integer.compare(y, x));


//Sol3
PriorityQueue<Integer> pq = new PriorityQueue<Integer>(defaultSize, new Comparator<Integer>() {
    public int compare(Integer lhs, Integer rhs) {
        if (lhs < rhs) return +1;
        if (lhs.equals(rhs)) return 0;
        return -1;
    }
});