C++ का priority_queue

एक priority_queue एक line है जहाँ सबसे important item हमेशा पहले बाहर आता है, सबसे sick patient को पहले treat करने वाले एक emergency room की तरह। Default से, सबसे बड़ा पहले जाता है।

In this page:

priority_queue क्या है?
push(), pop() और top()
Max-heap बनाम Min-heap
Custom Comparators
Practical Use: Top-K Elements

Syntax

cpp

#include <queue>

std::priority_queue<data_type> queue_name;
queue_name.push(value);
queue_name.top();
queue_name.pop();

priority_queue क्या है?

std::priority_queue एक container adapter है जो हमेशा सबसे बड़ा element top पर accessible रखता है, internally एक binary heap (default से एक max-heap) की तरह implemented।

यह तब इस्तेमाल होता है जब आपको एक बदलते collection से बार-बार current maximum (या minimum) चाहिए।

उदाहरण: What is priority_queue?

cpp

#include <iostream>
#include <queue>

int main() {
	std::priority_queue<int> pq; // largest element always accessible at top
	pq.push(3);
	pq.push(7);
	pq.push(1);
	std::cout << pq.top() << std::endl;
	return 0;
}

push(), pop() और top()

push() एक element insert करता है और re-heapify करता है। top() इसे remove किए बिना highest-priority element return करता है। pop() top element remove करता है, जिसके बाद अगला-highest element नया top बन जाता है।

उदाहरण: push(), pop() and top()

cpp

#include <iostream>
#include <queue>

int main() {
	std::priority_queue<int> pq;
	pq.push(5);
	pq.push(9);
	std::cout << pq.top() << std::endl; // highest priority, no removal
	pq.pop();
	std::cout << pq.top() << std::endl;
	return 0;
}

Max-heap बनाम Min-heap

Default से, priority_queue एक max-heap है (सबसे बड़ा top पर)। एक min-heap (सबसे छोटा top पर) पाने के लिए, underlying container specify करें और comparator की तरह std::greater इस्तेमाल करें।

उदाहरण: Max-heap vs Min-heap

cpp

#include <iostream>
#include <queue>
#include <vector>

int main() {
	std::priority_queue<int, std::vector<int>, std::greater<int>> minHeap; // smallest on top
	minHeap.push(5);
	minHeap.push(1);
	minHeap.push(3);
	std::cout << minHeap.top() << std::endl;
	return 0;
}

Custom Comparators

एक priority_queue एक custom comparator (एक function object या lambda-based struct) supply करके किसी भी rule से elements order कर सकता है, जैसे objects को एक specific field से order करना।

उदाहरण: Custom Comparators

cpp

// Include std::cout and std::cin
#include <iostream>
#include <queue>
// Include std::vector
#include <vector>
#include <cstdlib>

// Define a structure type named CompareAbs
struct CompareAbs {
	bool operator()(int a, int b) { return abs(a) < abs(b); }
};

// Program execution starts in main()
int main() {
	std::priority_queue<int, std::vector<int>, CompareAbs> pq;
	pq.push(-10);
	pq.push(3);
	// Print to the console with cout
	std::cout << pq.top() << std::endl;
	// Return 0 to signal that the program finished successfully
	return 0;
}

Practical Use: Top-K Elements

एक common priority_queue pattern पूरे collection को sort किए बिना data की एक stream में k largest (या smallest) elements ढूंढना है।

उदाहरण: Practical Use: Top-K Elements

cpp

#include <iostream>
#include <queue>
#include <vector>

int main() {
	std::priority_queue<int, std::vector<int>, std::greater<int>> minHeap; // keep only the 2 largest
	int values[] = {5, 1, 9, 3};
	for (int v : values) {
		minHeap.push(v);
		if (minHeap.size() > 2) minHeap.pop();
	}
	std::cout << minHeap.top() << std::endl;
	return 0;
}

Chapter Quiz — Complete all 15 topics to unlock

0/15 topics done

Complete these topics first:

← Previous Lesson C++ queue STL Next Lesson → C++ Memory Management