priority queue data structure c with illustration
चित्रण के साथ C ++ में प्राथमिकता कतार का परिचय।
प्राथमिकता कतार कतार का एक विस्तार है जिसे हमने अपने अंतिम ट्यूटोरियल में चर्चा की है।
यह कुछ पहलुओं में कतार के समान है और फिर भी यह निम्नलिखित बिंदुओं में साधारण कतार से अलग है:
- प्राथमिकता कतार में प्रत्येक आइटम प्राथमिकता के साथ जुड़ा हुआ है।
- सर्वोच्च प्राथमिकता वाला आइटम कतार से हटाया जाने वाला पहला आइटम है।
- यदि एक से अधिक वस्तुओं की समान प्राथमिकता है, तो कतार में उनके आदेश को माना जाता है।
=> निरपेक्ष सी ++ प्रशिक्षण श्रृंखला के लिए यहां क्लिक करें।
हम प्राथमिकता कतार को कतार के संशोधित संस्करण के रूप में देख सकते हैं, सिवाय इसके कि जब आइटम को कतार से बाहर ले जाना है, तो सर्वोच्च प्राथमिकता वाली वस्तु को पहले पुनर्प्राप्त किया जाता है। इसलिए हम प्राथमिकता के आधार पर वस्तुओं को संसाधित करने की आवश्यकता होने पर कतारों के बजाय प्राथमिकता वाले कतारों का उपयोग करना पसंद करते हैं।
आप क्या सीखेंगे:
बुनियादी संचालन
आइए हम प्राथमिकता कतार द्वारा समर्थित कुछ बुनियादी कार्यों पर चर्चा करते हैं।
- सम्मिलित करें (आइटम, प्राथमिकता): किसी दिए गए प्राथमिकता के साथ एक आइटम को प्राथमिकता कतार में सम्मिलित करता है।
- getHighestPriority (): सर्वोच्च प्राथमिकता वाला आइटम देता है।
- हटाएँ सर्वोच्च प्राथमिकता वाला आइटम निकालता है।
उपर्युक्त परिचालनों के अलावा, हम सामान्य कतार परिचालनों का उपयोग भी कर सकते हैं जैसे कि isEmpty (), isFull () और झांकना ()।
चित्रण
आइए हम प्राथमिकता कतार का एक उदाहरण देखें। सादगी उद्देश्यों के लिए, हम ASCII वर्णों को प्राथमिकता कतार में आइटम के रूप में उपयोग करेंगे। ASCII मूल्य जितना अधिक होगा, उच्च प्राथमिकता है।
प्रारंभिक स्थिति - प्राथमिकता कतार (PQ) - {} => खाली
उपरोक्त चित्रण से, हम देखते हैं कि सम्मिलित ऑपरेशन एक साधारण कतार के समान है। लेकिन जब हम प्राथमिकता पंक्ति के लिए 'deleteHighestPriority' कहते हैं, तो सर्वोच्च प्राथमिकता वाला तत्व पहले हटा दिया जाता है।
इसलिए पहली बार जब हम इस फ़ंक्शन को कॉल करते हैं, तो आइटम O को हटा दिया जाता है जबकि दूसरी बार, आइटम M को हटा दिया जाता है क्योंकि इसमें G और A की उच्च प्राथमिकता होती है।
C ++ में प्राथमिकता कतार का कार्यान्वयन
प्राथमिकता कतारों का उपयोग करके लागू किया जा सकता है:
# 1) सूची / लिंक की गई सूचियाँ
हम सरणियों का उपयोग करके प्राथमिकता वाले कतारों को लागू कर सकते हैं और यह प्राथमिकता कतारों के लिए सबसे सरल कार्यान्वयन है।
प्राथमिकता कतार में आइटमों का प्रतिनिधित्व करने के लिए, हम नीचे एक संरचना की घोषणा कर सकते हैं:
struct pq_item{ int item; int priority; };हमने प्रत्येक आइटम के लिए प्राथमिकता घोषित की है।
प्राथमिकता कतार में एक नया आइटम डालने के लिए हमें बस सरणी के अंत में आइटम सम्मिलित करना होगा।
GetHighestPriority () का उपयोग करके कतार से तत्व प्राप्त करने के लिए, हमें शुरुआत से सरणी को पीछे करना होगा और आइटम को सर्वोच्च प्राथमिकता के साथ वापस करना होगा।
इसी प्रकार, DeleteHighestPriority ऑपरेशन का उपयोग करके कतार से आइटम को हटाने के लिए, हमें पूरे सरणी को ट्रैवस करना होगा और आइटम को सर्वोच्च प्राथमिकता से हटाना होगा। फिर हटाए गए आइटम के बाद सभी अन्य तत्वों को स्थानांतरित करें, एक स्थिति वापस।
हम लिंक की गई सूची का उपयोग करके प्राथमिकता कतार को भी लागू कर सकते हैं। हम सभी ऑपरेशनों को एक समान तरीके से कर सकते हैं जैसे कि सरणियाँ। फर्क सिर्फ इतना है कि हमें डिलीट डिलीट करने के बाद एलिमेंट्स की जरूरत नहीं है।
# 2) हीप्स
प्राथमिकता कतार को लागू करने के लिए ढेर का उपयोग करना सबसे कुशल तरीका है और यह लिंक्ड सूचियों और सरणियों की तुलना में बहुत बेहतर प्रदर्शन प्रदान करता है। लिंक की गई सूची और सरणी के विपरीत, ढेर कार्यान्वयन प्राथमिकता कतार के संचालन को सम्मिलित करने और हटाने के लिए O (logn) समय लेता है। ऑपरेशन करें, getHighestPyerity में O (1) समय लगता है।
# 3) C ++ में मानक टेम्पलेट लाइब्रेरी (STL) में निर्मित प्राथमिकता कतार
सी ++ में, हमारे पास कंटेनर अनुकूली वर्ग के रूप में एक प्राथमिकता कतार है, इस तरह से डिज़ाइन किया गया है कि कतार में सबसे पहला तत्व पहला तत्व है और सभी तत्व घटते क्रम में हैं।
इस प्रकार प्राथमिकता कतार में प्रत्येक वस्तु की एक निश्चित प्राथमिकता होती है।
हमारे पास एसटीएल में वर्ग है, जिसमें प्राथमिकता कतार कार्यान्वयन है।
प्राथमिकता कतार द्वारा समर्थित विभिन्न ऑपरेशन निम्नानुसार हैं:
- प्राथमिकता_करना :: आकार (): कतार का आकार लौटाता है।
- प्राथमिकता_करना :: खाली (): जाँच करता है कि कतार खाली है और अपनी स्थिति लौटाता है या नहीं।
- प्रायोरिटी_क्यू :: टॉप (): प्राथमिकता कतार के सबसे ऊपरी तत्व का संदर्भ देता है।
- प्रायोरिटी_क्यू :: पुश (): प्राथमिकता कतार के अंत में एक आइटम जोड़ता है।
- प्रायोरिटी_क्व्यू :: पॉप (): प्राथमिकता कतार से पहला तत्व निकालता है।
- प्राथमिकता_करना :: स्वैप (): एक ही प्रकार और आकार के एक अन्य के साथ एक प्राथमिकता कतार की सामग्री को स्वैप करने के लिए उपयोग किया जाता है।
- प्राथमिकता कतार मूल्य प्रकार: मूल्य प्रकार प्राथमिकता कतार के अंदर संग्रहीत तत्व का प्रकार देता है। यह भी टेम्पलेट पैरामीटर के लिए एक पर्याय के रूप में कार्य करता है।
- प्राथमिकता_करना :: emplace (): कतार के शीर्ष पर प्राथमिकता कतार कंटेनर में एक नया तत्व सम्मिलित करने के लिए उपयोग किया जाता है।
अगले कार्यक्रम में, हम C ++ में एसटीएल में प्राथमिकता कतार की कार्यक्षमता देखेंगे।
#include #include using namespace std; void displaypq(priority_queue pq) { priority_queue pqueue = pq; while (!pqueue.empty()) { cout << ' ' << pqueue.top(); pqueue.pop(); } cout << '
'; } int main () { priority_queue pq; pq.push(1); pq.push(3); pq.push(5); pq.push(7); pq.push(9); cout << 'Size of the queue(pq.size()): ' << pq.size(); cout << '
Top element of the queue(pq.top()): ' << pq.top(); cout << '
The priority queue pq is : '; displaypq(pq); cout << '
Priority queue, after pq.pop() operation : '; pq.pop(); displaypq(pq); return 0; } आउटपुट:
सबसे अच्छा डेटा रिकवरी सॉफ़्टवेयर विंडोज़ 10
कतार का आकार (pq.size ()): 5
कतार का शीर्ष तत्व (pq.top ()): 9
प्राथमिकता कतार pq है: ९ 3 ५ ३ १
प्राथमिकता कतार, pq.pop () ऑपरेशन के बाद: 7 5 3 1
प्राथमिकता कतार के लिए जावा कार्यान्वयन
जावा में प्राथमिकता कतार एक विशेष कतार है जहां कतार में सभी तत्वों को कतार के साथ आपूर्ति किए गए तुलनित्र का उपयोग करके प्राकृतिक आदेश या कस्टम ऑर्डर के अनुसार आदेश दिया जाता है।
जावा में एक प्राथमिकता कतार नीचे दी गई दिखती है:
जावा प्राथमिकता कतार में, तत्वों को ऐसे व्यवस्थित किया जाता है कि सबसे कम तत्व कतार के सामने होता है और सबसे बड़ा तत्व कतार के पीछे होता है। इसलिए जब हम तत्व को प्राथमिकता कतार से हटाते हैं, तो यह हमेशा सबसे छोटा तत्व होता है जिसे हटा दिया जाता है।
जावा में प्राथमिकता कतार को लागू करने वाला वर्ग 'प्रायोरिटी क्यू' है और जावा के संग्रह ढांचे का एक हिस्सा है। यह जावा के 'कतार' इंटरफ़ेस को लागू करता है।
जावा प्रायोरिटी वर्ग के लिए श्रेणी पदानुक्रम निम्नलिखित है।
नीचे दिए गए जावा में आइटम के रूप में पूर्णांक के साथ प्राथमिकता कतार कार्यक्षमता का एक उदाहरण है।
import java.util.*; class Main { public static void main(String args()) { // Create empty priority queue PriorityQueue priority_Queue = new PriorityQueue(); // Adding items to the priority_Queue using add() priority_Queue.add(1); priority_Queue.add(3); priority_Queue.add(5); priority_Queue.add(7); // display the most priority element System.out.println('peek()::Head value:' + priority_Queue.peek()); // Print all elements in Priotity queue System.out.println('The priority queue:'); Iterator itr = priority_Queue.iterator(); while (itr.hasNext()) System.out.print(itr.next() + ' '); // poll() function to remove the queue elements priority_Queue.poll(); System.out.println('
After poll() function, priority queue:'); Iterator itr2 = priority_Queue.iterator(); while (itr2.hasNext()) System.out.print(itr2.next() + ' '); // remove() function with priority queue priority_Queue.remove(5); System.out.println('
After Remove(5) function, priority queue:'); Iterator itr3 = priority_Queue.iterator(); while (itr3.hasNext()) System.out.print(itr3.next() + ' '); // Check if an element is present using contains() boolean b = priority_Queue.contains(3); System.out.println ( '
Priority queue contains 3?: ' + b); // use toArray() function to get objects from the queue and display the array elements Object() arr = priority_Queue.toArray(); System.out.println ( 'Array elements: '); for (int i = 0; i आउटपुट:
झांकना () :: प्रमुख मूल्य: 1
प्राथमिकता कतार:
१ ३ ५ 5
मतदान के बाद () फ़ंक्शन, प्राथमिकता कतार:
३ 3 ५
निकालें (5) फ़ंक्शन के बाद, प्राथमिकता कतार:
३ 7
प्राथमिकता कतार में 3 शामिल हैं ?: सच
ऐरे तत्व:
मूल्य: 3
मान: 7
उपरोक्त कार्यक्रम में, हम प्राथमिकता के एक ऑब्जेक्ट को बनाने के लिए जावा के प्रायोरिटी क्यू वर्ग का उपयोग करते हैं जिसमें एक इंटेगर ऑब्जेक्ट होता है। हम 'ऐड' फ़ंक्शन का उपयोग करके तत्वों को कतार में जोड़ते हैं। फिर पोल () फ़ंक्शन को कहा जाता है और यह कतार के सामने से तत्व को हटाता है जो कम से कम तत्व होता है।
फिर से हम 'निकालें ()' फ़ंक्शन को कहते हैं जो कतार से पैरामीटर के रूप में निर्दिष्ट तत्व को हटा देता है। यदि कोई विशेष तत्व कतार में मौजूद है, तो हम यह जांचने के लिए कि इसमें “Contains ()” फ़ंक्शन का उपयोग किया गया है। अंत में, हम कतार को एक सरणी ऑब्जेक्ट में 'एअर्रे ()' फ़ंक्शन का उपयोग करके परिवर्तित करते हैं।
आवेदन
- ऑपरेटिंग सिस्टम लोड संतुलन और बाधा हैंडलर: ऑपरेटिंग सिस्टम फ़ंक्शंस जैसे लोड बैलेंसिंग और इंटरप्टर्स हैंडलिंग को प्राथमिकता कतारों का उपयोग करके लागू किया जाता है। लोड बैलेंसिंग गतिविधि हमारे लोड बैलेंसिंग को प्रभावी ढंग से चलाने के लिए संसाधनों को उच्चतम प्राथमिकता के साथ शेड्यूल करती है। इंटरप्ट हैंडलिंग को सर्वोच्च प्राथमिकता के साथ इंटरप्ट को सर्विस करके किया जाता है। प्राथमिकता वाले कतारों का उपयोग करके इस कार्यक्षमता को प्रभावी ढंग से लागू किया जा सकता है।
- रूटिंग: रूटिंग एक फ़ंक्शन है जो नेटवर्क संसाधनों को रूट करने के लिए उपयोग किया जाता है ताकि हम न्यूनतम घुमाव समय के साथ अधिकतम थ्रूपुट प्राप्त करें। इसे प्राथमिकता कतार का उपयोग करके भी लागू किया जा सकता है।
- अस्पताल की इमरजेंसी: अस्पताल के आपातकालीन कक्ष में, रोगी की स्थिति कितनी गंभीर है, इसके अनुसार रोगियों को उपस्थित किया जाता है। इसे प्राथमिकता कतारों का उपयोग करके सिम्युलेटेड किया जा सकता है।
- दिज्क्स्ट्रा का सबसे छोटा पथ एल्गोरिथम: यहाँ ग्राफ़ को एक आसन्न सूची के रूप में संग्रहीत किया गया है और हम दिक्क्स्ट्रा के सबसे छोटे पथ एल्गोरिथम को लागू करने के लिए आसन्न सूची से कुशलता से न्यूनतम भारित किनारे को निकालने के लिए प्राथमिकता कतार का उपयोग कर सकते हैं।
- प्राथमिकता कतार का उपयोग नोड कुंजियों को संग्रहीत करने और फैले हुए पेड़ को लागू करते समय न्यूनतम कुंजी नोड को निकालने के लिए भी किया जा सकता है।
निष्कर्ष
प्राथमिकता कतारें कतार के विस्तार के अलावा और कुछ नहीं हैं। लेकिन FIFO दृष्टिकोण का उपयोग करके वस्तुओं को जोड़ने / हटाने वाली कतारों के विपरीत, प्राथमिकता कतार में वस्तुओं को प्राथमिकता के अनुसार कतार से हटा दिया जाता है। इस प्रकार कतार में प्रत्येक वस्तु प्राथमिकता के साथ जुड़ी हुई है और सर्वोच्च प्राथमिकता वाली वस्तु कतार से हटने वाली पहली है।
प्राथमिकता कतार में तीन मुख्य ऑपरेशन होते हैं अर्थात् सम्मिलित करें (), getHighestPriority () और deleteHighestPyerity ()। प्राथमिकता पंक्ति को सरणियों या लिंक की गई सूची का उपयोग करके लागू किया जा सकता है लेकिन कार्य बहुत कुशल नहीं है। प्राथमिकता कतार को ढेर का उपयोग करके भी लागू किया जा सकता है और प्रदर्शन बहुत तेज है।
C ++ में, हमारे पास एक कंटेनर क्लास भी है जो एक प्राथमिकता कतार की कार्यक्षमता को लागू करता है। जावा में, एक अंतर्निर्मित वर्ग प्राथमिकता_ चक्र है जो प्राथमिकता कतार की कार्यक्षमता प्रदान करता है।
प्राथमिकता कतार मुख्य रूप से उन अनुप्रयोगों में उपयोग की जाती है जिन्हें प्राथमिकता के अनुसार संसाधित करने के लिए वस्तुओं की आवश्यकता होती है। उदाहरण के लिए, इसका उपयोग इंटरप्ट हैंडलिंग में किया जाता है।
हमारा आगामी ट्यूटोरियल सभी परिपत्र कतार के बारे में पता लगाएगा जो कतार का एक और विस्तार है।
=> विशेषज्ञों से पूरा सी ++ कोर्स के लिए यहां जाएं।
अनुशंसित पाठ
- कतार डेटा संरचना चित्रण के साथ C ++ में
- एसटीएल में प्राथमिकता कतार
- चित्रण के साथ C ++ में स्टैक डेटा संरचना
- चित्रण के साथ C ++ में परिपत्र लिंक्ड सूची डेटा संरचना
- सी + + में चित्र संरचना के साथ लिंक्ड सूची डेटा संरचना
- संदेह के साथ सी ++ में संदिग्ध रूप से सूचीबद्ध डेटा संरचना
- C ++ में डेटा स्ट्रक्चर्स का परिचय
- टेस्ट मैसेजिंग क्यू कैसे टेस्ट करें: IBM WebSphere MQ Intro Tutorial