Priority Queue

#include <queue>

priority_queue<int> pq;             // create priority queue for ints

pq.push(10);                        // push integer in priority queue
pq.top();                           // get the top element from pq without popping it
pq.pop();                           // pop the top element from pq. It returns void

while(!pq.empty()){                 // pq.empty returns whether pq is empty or not
    
}

Note: If we update the value of a node inside our priority_queue, that node will not be auto-heapified and hence will not be placed at correct position. Our priority queue will become inconsistent. So whenever you have to update a node inside priority queue

• update the node's value

• create a new node* pointing to that node and push that in priority queue

• our new node* will be placed at correct position.

Since we are updating the value in the node and the priority queue contains only node pointers, the old node pointer and fresh node pointer, both will point to same node which always contain the updated value. So when we will process this priority queue, it doesn't matter which pointer is popped out first since both are pointing to node with updated value. Now, to prevent multiple processing of node, keep a "isProcessed" field inside every node, initially set to false. whenever you process that node for the first time (can be via old pointer or via fresh pointer, doesn't matter), set that isProcessed field to true. Check this field whenever you are processing a node after popping it out, ignore that node if it is already processed

// priority queue with custom object

class Student {
    
    private:
        string name; 
        int marks;
        
    public:
        Student(string name, int marks){
            this->name = name;
            this->marks = marks;
        }
        
        string getName(){
            return name;
        }
        
        int getMarks() {
            return marks;
        }
};

class StudentComparator {
    public:
        bool operator() (Student& lowerPriorityStudent, Student& higherPriorityStudent)
        {
            return higherPriorityStudent.getMarks() > lowerPriorityStudent.getMarks();
        }
};

int main() {

    priority_queue<Student, vector<Student>, StudentComparator> pq;
    
    pq.push(Student("A1", 90));
    pq.push(Student("A2", 12));
    pq.push(Student("A3", 45));
    pq.push(Student("A4", 30));
    pq.push(Student("A5", 50));
    
    
    while(!pq.empty()){
        Student top = pq.top();
        cout << top.getName() << ", " << top.getMarks() << endl;
        pq.pop();
    }
    return 0;
}


Result:
    A1, 90
    A5, 50
    A3, 45
    A4, 30
    A2, 12
        

// priority queue when keys inside the nodes of priority queue are updated during prrocessing (e.g. in dijkstra)

#include <iostream>
#include <queue>

using namespace std;



class Node {
	public:
		int key; 		// priority queue will do sorting based on key
		string label;	// label is general metadaata stored in the node.
		bool processed; // whenever we update key in a node, we insert a new node pointer in the pq
						// To prevent multiple processing of same node, we use this flag to keep track 
						// if some node is already processed

		Node(int key, string label, bool processed): key(key), label(label), processed(processed){

		}
};


class NodeComparator{
	public:
		bool operator()(Node* &lowerPriorityNode, Node* &higherPriorityNode){
			return higherPriorityNode->key <= lowerPriorityNode->key;
		}
};



int main(int argc, char const *argv[])
{
	// Always use Node* instead of Node. If there is some update in node key which decreases node's priority
	// (by increasing its key value here in this example), then stale node will be popped earlier than the updated node
	// which is wrong. If we use pointer, then stale node pointer and fresh node pointer, both will point to same node
	// which contains the updated value of key.
	// https://stackoverflow.com/a/27305600
	priority_queue<Node*, vector<Node*>, NodeComparator> pq;


	Node* n3 = new Node(50, "N3", false);


	pq.push(new Node(10, "N1", false));
	pq.push(new Node(3, "N2", false));
	pq.push(n3);
	pq.push(new Node(150, "N4", false));
	pq.push(new Node(1, "N5", false));
	pq.push(new Node(100, "N6", false));
	pq.push(new Node(15, "N7", false));

	cout << "Priority Queue Initialised\n\n" << endl;

	n3->key = 5;
	pq.push(n3);

	cout << "n3 key updated\n" << endl;

	cout << "\n\nstarting processing of nodes in priority queue \n" << endl;
	while(!pq.empty()){
		Node* top = pq.top();
		pq.pop();

		if(!top->processed){
			// process node
			cout << "top node = " << top->label << " : " << top->key << endl;
			top->processed = true;
		}
	}

	return 0;
}