# Priority Queue

```cpp
#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

```cpp
// 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
        
```

```cpp
// 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;
}

```


---

# Agent Instructions: Querying This Documentation

If you need additional information that is not directly available in this page, you can query the documentation dynamically by asking a question.

Perform an HTTP GET request on the current page URL with the `ask` query parameter:

```
GET https://blog.gomchik.com/tech/c++/priority_queue.md?ask=<question>
```

The question should be specific, self-contained, and written in natural language.
The response will contain a direct answer to the question and relevant excerpts and sources from the documentation.

Use this mechanism when the answer is not explicitly present in the current page, you need clarification or additional context, or you want to retrieve related documentation sections.