प्राथमिकता कतार

कंप्यूटर विज्ञान में, प्राथमिकता कतार एक नियमित कतार या स्टैक डेटा संरचना के समान एक अमूर्त डेटा-प्रकार है। प्राथमिकता कतार में प्रत्येक तत्व की एक संबद्ध प्राथमिकता होती है। प्राथमिकता कतार में, उच्च प्राथमिकता वाले तत्वों को लघु प्राथमिकता वाले तत्वों से पहले रखा जाता है।और कुछ कार्यान्वयन में, यदि दो तत्वों की प्राथमिकता समान है, तो उन्हें उसी क्रम में रखा जाता है जिसमें वे पंक्तिबद्ध थे। अन्य कार्यान्वयन में, समान प्राथमिकता वाले तत्वों का क्रम अपरिभाषित है।

जबकि प्राथमिकता कतारें प्रायः हीप (डेटा संरचना) का उपयोग करके कार्यान्वित की जाती हैं, इस प्रकार से यह अवधारणात्मक रूप से हीप से अलग होती हैं। किन्तु प्राथमिकता कतार अमूर्त डेटा संरचना है जैसे सूची (अमूर्त डेटा संरचना) या सहयोगी सरणी; जिस तरह सूची को लिंक की गई सूची के साथ या ऐरे डेटा संरचना के साथ क्रियान्वित किया जा सकता है, प्राथमिकता कतार के रूप में या किसी अन्य विधि जैसे कि अनियंत्रित सरणी के साथ क्रियान्वित किया जा सकता है।

संचालन

प्राथमिकता कतार को कम से कम निम्नलिखित परिचालनों का समर्थन करना चाहिए:

• is_empty: जांचें कि क्या कतार में कोई तत्व नहीं है।
• Insert_with_priority: संबंधित प्राथमिकता के साथ कतार (सार डेटा संरचना) में तत्व (गणित) सम्मिलित है ।
• pull_highest_priority_element: उस तत्व को कतार से रिमूव कर दें जिसकी सर्वोच्च प्राथमिकता है, और उसे वापस कर दें।

  इसे Pop_element(Off) , get_maximum_element या get_front(most)_element के नाम से भी जाना जाता है।

  कुछ परंपराएं कम मूल्यों को उच्च प्राथमिकता मानते हुए प्राथमिकताओं के क्रम को प्रतिलोम कर देती हैं, इसलिए इसे get_minimum_element के रूप में भी जाना जा सकता है, और प्रायः साहित्य में इसे get-min के रूप में जाना जाता है।

  इसके बजाय इसे अलग-अलग peek_at_highest_priority_element और delete_element फ़ंक्शंस के रूप में निर्दिष्ट किया जा सकता है, जिन्हें पुल_highest_priority_element बनाने के लिए जोड़ा जा सकता है।

इसके अतिरिक्त , पीक (डेटा संरचना ऑपरेशन) (इस संदर्भ में प्रायः फाइंड-मैक्स या फाइंड-मिन कहा जाता है), जो उच्चतम-प्राथमिकता वाले तत्व को लौटाता है किन्तु कतार को संशोधित नहीं करता है, इसे अधिक बार क्रियान्वित किया जाता है, और लगभग सदैव बिग ओ में निष्पादित होता है अंकन O(1) समय. यह ऑपरेशन और इसका O(1) प्रदर्शन प्राथमिकता कतारों के कई अनुप्रयोगों के लिए महत्वपूर्ण है।

इस प्रकार से अधिक उन्नत कार्यान्वयन अधिक जटिल संचालन का समर्थन कर सकते हैं, जैसे कि पुल_लोवेस्ट_प्रायोरिटी_एलिमेंट, पहले कुछ उच्चतम या निम्न-प्राथमिकता वाले तत्वों का निरीक्षण करना, कतार को साफ़ करना, कतार के सबसेट को साफ़ करना, बैच सम्मिलित करना, दो या दो से अधिक कतारों को में विलय करना,किसी भी तत्व प्राथमिकता बढ़ाना आदि।

स्टैक (अमूर्त डेटा संरचना) और क्यू (अमूर्त डेटा संरचना) को विशेष प्रकार की प्राथमिकता कतारों के रूप में कार्यान्वित किया जा सकता है, प्राथमिकता उस क्रम से निर्धारित होती है जिसमें तत्व इन्सर्ट किये जाते हैं। इस प्रकार से स्टैक में, प्रत्येक सम्मिलित तत्व की प्राथमिकता नीरस रूप से बढ़ रही है; इस प्रकार, इन्सर्ट किया गया अंतिम तत्व सदैव सबसे प्रथम पुनर्प्राप्त किया जाता है। किन्तु कतार में, प्रत्येक सम्मिलित तत्व की प्राथमिकता नीरस रूप से घट रही है; इस प्रकार, समिलित किया गया गया प्रथम तत्व सदैव सर्वप्रथम पुनर्प्राप्त किया जाता है।

कार्यान्वयन

अनुभवहीन कार्यान्वयन

प्राथमिकता कतार को क्रियान्वित करने के अनेक सरल,सामान्यतः अप्रभावी विधि हैं। वे यह समझने में सहायता करने के लिए सादृश्य प्रदान करते हैं कि प्राथमिकता कतार क्या है।

इस प्रकार से उदाहरण के लिए, कोई सभी तत्वों को अवर्गीकृत सूची (O(1) सम्मिलन टाइम ) में रख सकता है। जब भी सर्वोच्च-प्राथमिकता वाले तत्व का अनुरोध किया जाए, तो सभी तत्वों में से सर्वोच्च प्राथमिकता वाले तत्व को खोजें। (O(n) पुल टाइम),

'सम्मिलित करें' (नोड)
{
 सूची.जोड़ें(नोड)
}

'खींचना'()
{
 उच्चतम = सूची.get_first_element()
 सूची में foreach नोड
 {
 यदि उच्चतम.प्राथमिकता <नोड.प्राथमिकता
 {
 उच्चतम = नोड
 }
 }
 सूची.निकालें(उच्चतम)
 उच्चतम वापसी
}

दूसरे स्तिथि में, अनेक सभी तत्वों को प्राथमिकता क्रमबद्ध सूची (ओ (एन) प्रविष्टि सॉर्ट समय) में रख सकता है, जब भी उच्चतम प्राथमिकता वाले तत्व का अनुरोध किया जाता है, तो सूची में पहला वापस किया जा सकता है। (O(1) पुल टाइम )

'सम्मिलित करें' (नोड)
{
 सूची में foreach (सूचकांक, तत्व)।
 {
 यदि नोड.प्राथमिकता <तत्व.प्राथमिकता
 {
 list.insert_at_index(नोड,सूचकांक)
 तोड़ना
 }
 }
}

'खींचना'()
{
 उच्चतम = list.get_at_index(list.length-1)
 सूची.निकालें(उच्चतम)
 उच्चतम वापसी
}

सामान्य कार्यान्वयन

इस प्रकार से प्रदर्शन में सुधार करने के लिए, प्राथमिकता कतारें सामान्यतः हीप (डेटा संरचना) पर आधारित होती हैं, जो सम्मिलन और निष्कासन के लिए ओ (लॉग एन) प्रदर्शन देती हैं, और प्रारंभ में एन तत्वों के सेट से हीप (डेटा संरचना) बनाने के लिए ओ (एन) देती हैं। मूलभूत हीप डेटा संरचना के वेरिएंट जैसे पेयरिंग हीप्स या फाइबोनैचि हीप्स कुछ ऑपरेशनों के लिए उत्तम सीमाएं प्रदान कर सकते हैं।

किन्तु वैकल्पिक रूप से, जब सेल्फ-बैलेंसिंग बाइनरी सर्च ट्री का उपयोग किया जाता है, तब यह सम्मिलन और निष्कासन में भी O(लॉग एन) समय लगता है, चूंकि तत्वों के उपस्तिथ अनुक्रम से ट्री बनाने में ओ(एन लॉग एन) समय लगता है; यह विशिष्ट है जहां किसी के पास पहले से ही इन डेटा संरचनाओं तक पहुंच हो सकती है, जैसे कि तृतीय-पक्ष या मानक पुस्तकालयों के साथ। अंतरिक्ष-जटिलता के दृष्टिकोण से, लिंक की गई सूची के साथ स्व-संतुलन बाइनरी सर्च ट्री का उपयोग करने से अधिक भंडारण की आवश्यकता होती है, क्योंकि इसके लिए अन्य नोड्स के अतिरिक्त संदर्भों को संग्रहीत करने की आवश्यकता होती है।

कम्प्यूटेशनल-जटिलता के दृष्टिकोण से, प्राथमिकता कतारें सॉर्टिंग एल्गोरिदम के अनुरूप हैं। नीचे प्राथमिकता कतारों और सॉर्टिंग एल्गोरिदम की #समानता पर अनुभाग बताता है कि कैसे कुशल सॉर्टिंग एल्गोरिदम कुशल प्राथमिकता कतारें बना सकते हैं।

विशेषीकृत ढेर

अनेक विशिष्ट हीप (डेटा संरचना) डेटा संरचनाएं हैं जो या तो अतिरिक्त संचालन की आपूर्ति करती हैं या विशिष्ट प्रकार की कुंजियों, विशेष रूप से पूर्णांक कुंजियों के लिए हीप-आधारित कार्यान्वयन को उत्तम प्रदर्शन करती हैं। मान लीजिए कि संभावित कुंजियों का सेट {1, 2, ..., C} है।

• जब केवल सम्मिलित करें, तो फाइंड-मिन और एक्सट्रैक्ट-मिन की आवश्यकता होती है और पूर्णांक प्राथमिकताओं के स्तिथि में, बकेट कतार का निर्माण C सरणी के रूप में किया जा सकता है लिंक की गई सूचियाँ और सूचक top, प्रारंभ में C. कुंजी के साथ कोई वस्तु सम्मिलित करना k वस्तु को इसमें जोड़ता है k'th सूची, और अद्यतन top ← min(top, k), दोनों निरंतर समय में। एक्स्ट्रैक्ट-मिन इंडेक्स top वाली सूची से वस्तु को हटाता है और लौटाता है , फिर वृद्धि top यदि आवश्यक हो, जब तक कि यह फिर से गैर-रिक्त सूची की ओर संकेत न कर दे; इस प्रकार से अधिक व्यर्थ स्थिति में O(C) टाइम लगता है । ये कतारें ग्राफ़ के शीर्षों को उनकी डिग्री के आधार पर क्रमबद्ध करने के लिए उपयोगी होती हैं।
• वैन एम्डे बोस कदम ओ (लॉग लॉग सी) समय में न्यूनतम, अधिकतम, सम्मिलित करें, हटाएं, खोज, निकालने-मिनट, निकालने-अधिकतम, पूर्ववर्ती और उत्तराधिकारी] संचालन का समर्थन करता है, किन्तु इसमें लगभग लघु कतारों के लिए स्थान निवेस होती है ओ(2^m/2), जहां m प्राथमिकता मान में बिट्स की संख्या है। और हैशिंग से स्थान को अधिक लघु किया जा सकता है।
• माइकल फ्रेडमैन और डैन विलार्ड का फ़्यूज़न ट्री O(1) समय में न्यूनतम ऑपरेशन और $O(\log n/\log \log C)$ इन्सर्ट और एक्सट्रेक्ट-मिन ऑपरेशन को क्रियान्वित करता है। समय। चूंकि लेखक द्वारा यह कहा गया है कि, हमारे एल्गोरिदम में केवल सैद्धांतिक रुचि है; निष्पादन समय में सम्मिलित निरंतर कारक व्यावहारिकता को रोकते हैं।

इस प्रकार से उन अनुप्रयोगों के लिए जो प्रत्येक एक्सट्रैक्ट-मिन ऑपरेशन के लिए कई पीक (डेटा संरचना ऑपरेशन) ऑपरेशन करते हैं, प्रत्येक प्रविष्टि और निष्कासन के पश्चात सर्वोच्च प्राथमिकता वाले तत्व को कैश करके सभी ट्री और हीप कार्यान्वयन में पीक क्रियाओं के लिए समय जटिलता को O(1) तक कम किया जा सकता है। और सम्मिलन के लिए, यह अधिकतम स्थिर निवेस जोड़ता है, क्योंकि नए सम्मिलित किये गए तत्व की तुलना केवल पहले कैश किए गए न्यूनतम तत्व से की जाती है। रिमूव करने के लिए, इसमें अधिक से अधिक अतिरिक्त झलक निवेस जोड़ी जाती है, जो सामान्यतः डीलीट किये गए निवेस से सस्ती होती है, इसलिए समग्र समय जटिलता महत्वपूर्ण रूप से प्रभावित नहीं होती है।

मोनोटोन प्राथमिकता कतार विशेष कतारें होती हैं जिन्हें उस स्तिथि के लिए अनुकूलित किया जाता है जहां कोई भी वस्तु कभी नहीं इन्सर्ट किया जाता है जिसकी प्राथमिकता पहले निकाले गए किसी भी वस्तु की तुलना में कम हो (मिन-हीप के स्तिथि में)। यह प्रतिबंध प्राथमिकता कतारों के कई व्यावहारिक अनुप्रयोगों द्वारा पूर्ण किया जाता है।

चलने के समय का सारांश

Here are time complexities of various heap data structures. Function names assume a min-heap. For the meaning of "O(f)" and "Θ(f)" see Big O notation.

Operation	find-min	delete-min	insert	decrease-key	meld
Binary	Θ(1)	Θ(log n)	O(log n)	O(log n)	Θ(n)
Leftist	Θ(1)	Θ(log n)	Θ(log n)	O(log n)	Θ(log n)
Binomial	Θ(1)	Θ(log n)	Θ(1)	Θ(log n)	O(log n)
Fibonacci	Θ(1)	O(log n)	Θ(1)	Θ(1)	Θ(1)
Pairing	Θ(1)	O(log n)	Θ(1)	o(log n)	Θ(1)
Brodal	Θ(1)	O(log n)	Θ(1)	Θ(1)	Θ(1)
Rank-pairing	Θ(1)	O(log n)	Θ(1)	Θ(1)	Θ(1)
Strict Fibonacci	Θ(1)	O(log n)	Θ(1)	Θ(1)	Θ(1)
2–3 heap	O(log n)	O(log n)	O(log n)	Θ(1)	?

प्राथमिकता कतारों और सॉर्टिंग एल्गोरिदम की समानता

सॉर्ट करने के लिए प्राथमिकता कतार का उपयोग करना

इस प्रकार से प्राथमिकता कतारों के परिचालन शब्दार्थ स्वाभाविक रूप से सोर्टिंग विधि का सुझाव देते हैं: अर्थात क्रमबद्ध किए जाने वाले सभी तत्वों को प्राथमिकता कतार में रखे , और क्रमिक रूप से उन्हें रिमूव कर दें; वे क्रमबद्ध विधि से सामने आएंगे यह वास्तव में कई सोर्टिंग एल्गोरिथ्म द्वारा उपयोग की जाने वाली प्रक्रिया है, इस प्रकार से प्राथमिकता कतार द्वारा प्रदान की गई अमूर्तता (कंप्यूटर विज्ञान) की लेयर हटा दी जाती है। यह सॉर्टिंग विधि निम्नलिखित सॉर्टिंग एल्गोरिदम के समान है:

नाम	प्राथमिकता कतार कार्यान्वयन	श्रेष्ठ	औसत	निकृष्टतम
हीपसॉर्ट	हीप	$n\log(n)$	$n\log(n)$	$n\log(n)$
स्मूथसॉर्ट	लियोनार्डो हीप	$n$	$n\log(n)$	$n\log(n)$
चयन क्रम	अव्यवस्थित सारणी	$n^{2}$	$n^{2}$	$n^{2}$
सम्मिलन सॉर्ट	क्रमबद्ध सारणी	$n$	$n^{2}$	$n^{2}$
ट्री सॉर्ट	सेल्फ-बैलेंसिंग बाइनरी सर्च ट्री	$n\log(n)$	$n\log(n)$	$n\log(n)$

प्राथमिकता कतार बनाने के लिए सॉर्टिंग एल्गोरिदम का उपयोग करना

प्राथमिकता कतार को क्रियान्वित करने के लिए सॉर्टिंग एल्गोरिदम का भी उपयोग किया जा सकता है। विशेष रूप से, थोरुप कहते हैं: <ब्लॉककोट>

हम प्राथमिकता कतारों से सॉर्टिंग तक सामान्य नियतात्मक रैखिक स्थान में कमी प्रस्तुत करते हैं, जिसका अर्थ है कि यदि हम प्रति कुंजी एस (एन) समय में एन कुंजी को सॉर्ट कर सकते हैं, तो ओ (एस (एन)) में हटाने और डालने का समर्थन करने वाली प्राथमिकता कतार है। निरंतर समय में समय और खोज-मिनट आदि ।

अर्थात्, यदि कोई सॉर्टिंग एल्गोरिदम है जो प्रति कुंजी O(S) समय में सॉर्ट कर सकता है, जहां S, n और शब्द आकार का कुछ फ़ंक्शन है, फिर कोई प्राथमिकता कतार बनाने के लिए दी गई प्रक्रिया का उपयोग कर सकता है जहां सर्वोच्च-प्राथमिकता वाले तत्व को खींचना O(1) समय है, और नए तत्वों को सम्मिलित करना (और तत्वों को हटाना) O(S) समय है। उदाहरण के लिए, यदि किसी के पास ओ(एन लॉग एन) सॉर्ट एल्गोरिदम है, तो वह ओ(1) पुलिंग और ओ(लॉग एन) सम्मिलन के साथ प्राथमिकता कतार बना सकता है।

पुस्तकालय

प्राथमिकता कतार को प्रायः कंटेनर (सार डेटा संरचना) माना जाता है।

मानक टेम्पलेट लाइब्रेरी (STL), और C++ 1998 मानक, std::priority_queue को STL कंटेनर (प्रोग्रामिंग) एडाप्टर (प्रोग्रामिंग) में से के रूप में निर्दिष्ट करता है ) टेम्पलेट (प्रोग्रामिंग)एस। चूंकि , यह निर्दिष्ट नहीं करता है कि समान प्राथमिकता वाले दो तत्वों को कैसे परोसा जाना चाहिए, और वास्तव में, सामान्य कार्यान्वयन उन्हें कतार में उनके क्रम के अनुसार वापस नहीं करेगा। यह अधिकतम-प्राथमिकता-कतार क्रियान्वित करता है, और इसमें तीन पैरामीटर होते हैं: सॉर्टिंग के लिए तुलनात्मक ऑब्जेक्ट जैसे कि फ़ंक्शन ऑब्जेक्ट (यदि अनिर्दिष्ट है तो कम<T> पर डिफ़ॉल्ट), डेटा संरचनाओं को संग्रहीत करने के लिए अंतर्निहित कंटेनर (std::vector पर डिफ़ॉल्ट) <T>), और अनुक्रम के आरंभ और अंत में दो पुनरावर्तक। वास्तविक एसटीएल कंटेनरों के विपरीत, यह इटरेटर को इसके तत्वों की अनुमति नहीं देता है (यह सख्ती से इसकी अमूर्त डेटा संरचना परिभाषा का पालन करता है)। एसटीएल में बाइनरी मैक्स-हीप के रूप में अन्य रैंडम-एक्सेस कंटेनर में हेरफेर करने के लिए उपयोगिता कार्य भी हैं। बूस्ट (C++ लाइब्रेरीज़) का लाइब्रेरी हीप में कार्यान्वयन भी है।

पायथन का heapq मॉड्यूल सूची के शीर्ष पर बाइनरी मिन-हीप क्रियान्वित करता है।

जावा (प्रोग्रामिंग भाषा) की लाइब्रेरी में सम्मिलित है PriorityQueue वर्ग, जो न्यूनतम-प्राथमिकता-कतार क्रियान्वित करता है।

.NET की लाइब्रेरी में प्राथमिकता क्यू वर्ग सम्मिलित है, जो सरणी-समर्थित को क्रियान्वित करता है, चतुर्धातुक न्यूनतम-ढेर।

स्काला (प्रोग्रामिंग भाषा) की लाइब्रेरी में प्राथमिकता क्यू वर्ग सम्मिलित है, जो अधिकतम-प्राथमिकता-क्यू क्रियान्वित करता है।

गो (प्रोग्रामिंग भाषा) की लाइब्रेरी में [1] मॉड्यूल होता है, जो किसी भी संगत डेटा संरचना के शीर्ष पर मिन-हीप क्रियान्वित करता है।

मानक PHP लाइब्रेरी एक्सटेंशन में क्लास SplPriorityQueue सम्मिलित है।

Apple के कोर फाउंडेशन फ्रेमवर्क में CFBinaryHeap संरचना सम्मिलित है, जो मिन-हीप क्रियान्वित करती है।

अनुप्रयोग

बैंडविड्थ प्रबंधन

संगणक संजाल राउटर (कंप्यूटिंग) से ट्रांसमिशन लाइन पर बैंडविड्थ (कंप्यूटिंग) जैसे सीमित संसाधनों को प्रबंधित करने के लिए प्राथमिकता कतार का उपयोग किया जा सकता है। अपर्याप्त बैंडविड्थ के कारण आउटगोइंग ट्रैफ़िक कतार में लगने की स्थिति में, आगमन पर ट्रैफ़िक को सर्वोच्च प्राथमिकता वाली कतार से भेजने के लिए अन्य सभी कतारों को रोका जा सकता है। यह सुनिश्चित करता है कि प्राथमिकता वाले ट्रैफ़िक (जैसे कि वास्तविक समय ट्रैफ़िक, उदाहरण के लिए इंटरनेट प्रोटोकॉल पर आवाज़ कनेक्शन की वास्तविक समय परिवहन प्रोटोकॉल स्ट्रीम) को कम से कम देरी के साथ अग्रेषित किया जाता है और कतार के अधिकतम तक पहुंचने के कारण अस्वीकार होने की कम से कम संभावना होती है। क्षमता। सर्वोच्च प्राथमिकता कतार खाली होने पर अन्य सभी ट्रैफ़िक को संभाला जा सकता है। उपयोग किया जाने वाला अन्य तरीका उच्च प्राथमिकता वाली कतारों से असंगत रूप से अधिक ट्रैफ़िक भेजना है।

स्थानीय क्षेत्र नेटवर्क के लिए कई आधुनिक प्रोटोकॉल में मीडिया अभिगम नियंत्रण (मैक) उप-परत पर प्राथमिकता कतारों की अवधारणा भी सम्मिलित है ताकि यह सुनिश्चित किया जा सके कि उच्च-प्राथमिकता वाले एप्लिकेशन (जैसे वीओआईपी या आईपीटीवी) अन्य अनुप्रयोगों की तुलना में कम विलंबता का अनुभव करते हैं जिन्हें इसके साथ परोसा जा सकता है। सर्वोत्तम प्रयास वाली सेवा. उदाहरणों में IEEE 802.11e (IEEE 802.11 में संशोधन जो सेवा की गुणवत्ता प्रदान करता है) और ITU-T G.hn (उपस्तिथ होम वायरिंग (पावर लाइन संचार, फोन लाइन और कोएक्स पर ईथरनेट) का उपयोग करके हाई-स्पीड लोकल एरिया नेटवर्क के लिए मानक) सम्मिलित हैं। .

सामान्यतः सीमा (पोलिसर) उस बैंडविड्थ को सीमित करने के लिए निर्धारित की जाती है जो उच्चतम प्राथमिकता कतार से ट्रैफ़िक ले सकता है, ताकि उच्च प्राथमिकता वाले पैकेटों को अन्य सभी ट्रैफ़िक को रोकने से रोका जा सके। यह सीमासामान्यतः सिस्को सिस्टम्स, इंक. प्रबंधक को कॉल करो जैसे उच्च स्तरीय नियंत्रण उदाहरणों के कारण कभी नहीं पहुंचती है, जिसे प्रोग्राम की गई बैंडविड्थ सीमा से अधिक होने वाली कॉल को रोकने के लिए प्रोग्राम किया जा सकता है।

असतत घटना अनुकरण

प्राथमिकता कतार का अन्य उपयोग घटनाओं को अलग घटना सिमुलेशन में प्रबंधित करना है। घटनाओं को प्राथमिकता के रूप में उपयोग किए गए उनके सिमुलेशन समय के साथ कतार में जोड़ा जाता है। सिमुलेशन का निष्पादन बार-बार कतार के शीर्ष को खींचकर और उस पर घटना को निष्पादित करके आगे बढ़ता है।

यह भी देखें: शेड्यूलिंग (कंप्यूटिंग), कतारबद्ध सिद्धांत

दिज्क्स्ट्रा का एल्गोरिथ्म

जब ग्राफ़ को आसन्न सूची या मैट्रिक्स के रूप में संग्रहीत किया जाता है, तो दिज्क्स्ट्रा के एल्गोरिदम को कार्यान्वित करते समय न्यूनतम कुशलता से निकालने के लिए प्राथमिकता कतार का उपयोग किया जा सकता है, चूंकि किसी को प्राथमिकता कतार में किसी विशेष शीर्ष की प्राथमिकता को कुशलतापूर्वक बदलने की क्षमता की भी आवश्यकता होती है।

यदि इसके बजाय, ग्राफ़ को नोड ऑब्जेक्ट के रूप में संग्रहीत किया जाता है, और प्राथमिकता-नोड जोड़े को ढेर में डाला जाता है, तो किसी विशेष शीर्ष की प्राथमिकता को बदलना आवश्यक नहीं है यदि कोई विज़िट किए गए नोड्स को ट्रैक करता है। बार नोड पर जाने के बाद, यदि यह दोबारा ढेर में आता है (पहले इसके साथ कम प्राथमिकता संख्या जुड़ी हुई थी), तो इसे पॉप-ऑफ कर दिया जाता है और अनदेखा कर दिया जाता है।

हफ़मैन कोडिंग

हफ़मैन कोडिंग के लिए व्यक्ति को दो सबसे कम आवृत्ति वाले ट्री ों को बार-बार प्राप्त करने की आवश्यकता होती है। प्राथमिकता कतार हफ़मैन कोडिंग#संपीड़न है।

सर्वोत्तम-प्रथम खोज एल्गोरिदम

सर्वश्रेष्ठ-प्रथम खोज एल्गोरिदम, ए * खोज एल्गोरिदम की तरह, भारित ग्राफ़ के दो वर्टेक्स (ग्राफ़ सिद्धांत) या नोड (ग्राफ़ सिद्धांत) के बीच सबसे छोटा रास्ता ढूंढते हैं, सबसे आशाजनक मार्गों को पहले आज़माते हैं। अज्ञात मार्गों पर नज़र रखने के लिए प्राथमिकता कतार (जिसे फ्रिंज भी कहा जाता है) का उपयोग किया जाता है; जिसके लिए कुल पथ लंबाई का अनुमान (ए* के स्तिथि में निचली सीमा) सबसे छोटा है, उसे सर्वोच्च प्राथमिकता दी जाती है। यदि मेमोरी सीमाएं सर्वोत्तम-प्रथम खोज को अव्यवहारिक बनाती हैं, तो कम-प्राथमिकता वाली वस्तुओं को हटाने की अनुमति देने के लिए डबल-एंडेड प्राथमिकता कतार के साथ एसएमए* एल्गोरिदम जैसे वेरिएंट का उपयोग किया जा सकता है।

ROAM त्रिकोणासन एल्गोरिथ्म

रीयल-टाइम ऑप्टिमली एडाप्टिंग मेश (आरओएएम) एल्गोरिदम किसी इलाके के गतिशील रूप से बदलते त्रिकोण की गणना करता है। यह त्रिकोणों को विभाजित करके काम करता है जहां अधिक विवरण की आवश्यकता होती है और जहां कम विवरण की आवश्यकता होती है वहां उन्हें विलय कर देता है। एल्गोरिथ्म इलाके में प्रत्येक त्रिकोण को प्राथमिकता देता है,सामान्यतः उस त्रिकोण को विभाजित करने पर त्रुटि में कमी से संबंधित होता है। एल्गोरिथ्म दो प्राथमिकता कतारों का उपयोग करता है, उन त्रिकोणों के लिए जिन्हें विभाजित किया जा सकता है और दूसरा उन त्रिकोणों के लिए जिन्हें विलय किया जा सकता है। प्रत्येक चरण में उच्चतम प्राथमिकता वाले विभाजित कतार से त्रिकोण को विभाजित किया जाता है, या सबसे कम प्राथमिकता वाले मर्ज कतार से त्रिकोण को उसके पड़ोसियों के साथ विलय कर दिया जाता है।

न्यूनतम फैले हुए ट्री के लिए प्राइम का एल्गोरिदम

जुड़ा हुआ ग्राफ ़ और अप्रत्यक्ष ग्राफ़ के न्यूनतम फैलाव वाला ट्री को खोजने के लिए प्राइम के एल्गोरिदम में बाइनरी ढेर का उपयोग करके, कोई अच्छा रनिंग टाइम प्राप्त कर सकता है। यह न्यूनतम हीप प्राथमिकता कतार न्यूनतम हीप डेटा संरचना का उपयोग करती है जो सम्मिलित, न्यूनतम, अर्क-मिनट, कमी-कुंजी जैसे संचालन का समर्थन करती है। इस कार्यान्वयन में, वर्टेक्स (ग्राफ़ सिद्धांत) की प्राथमिकता तय करने के लिए किनारों के भारित ग्राफ़ का उपयोग किया जाता है। वजन जितना कम होगा, प्राथमिकता उतनी अधिक होगी और वजन जितना अधिक होगा, प्राथमिकता कम होगी।

समानांतर प्राथमिकता कतार

प्राथमिकता कतारों को तेज़ करने के लिए समानांतरीकरण का उपयोग किया जा सकता है, किन्तु प्राथमिकता कतार इंटरफ़ेस में कुछ बदलाव की आवश्यकता होती है। ऐसे परिवर्तनों का कारण यह है किसामान्यतः क्रमिक अद्यतन ही होता है ${\textstyle O(1)}$ या ${\textstyle O(\log n)}$ निवेस , और ऐसे ऑपरेशन को समानांतर करने का कोई व्यावहारिक लाभ नहीं है। संभावित परिवर्तन ही प्राथमिकता कतार में एकाधिक प्रोसेसर की समवर्ती पहुंच की अनुमति देना है। दूसरा संभावित परिवर्तन बैच संचालन की अनुमति देना है जो काम करता है ${\textstyle k}$ केवल तत्व के बजाय तत्व। उदाहरण के लिए, एक्सट्रैक्टमिन पहले को हटा देगा ${\textstyle k}$ सर्वोच्च प्राथमिकता वाले तत्व।

समवर्ती समानांतर पहुंच

यदि प्राथमिकता कतार समवर्ती पहुंच की अनुमति देती है, तो कई प्रक्रियाएं उस प्राथमिकता कतार पर समवर्ती रूप से संचालन कर सकती हैं। चूंकि , इससे दो मुद्दे उठते हैं। सबसे पहले, व्यक्तिगत संचालन के शब्दार्थ की परिभाषा अब स्पष्ट नहीं है। उदाहरण के लिए, यदि दो प्रक्रियाएं सर्वोच्च प्राथमिकता वाले तत्व को निकालना चाहती हैं, तो क्या उन्हें ही तत्व मिलना चाहिए या अलग-अलग? यह प्राथमिकता कतार का उपयोग करके प्रोग्राम के स्तर पर समानता को प्रतिबंधित करता है। इसके अतिरिक्त , क्योंकि कई प्रक्रियाओं की ही तत्व तक पहुंच होती है, इससे विवाद होता है।

नोड 3 डाला जाता है और नोड 2 के पॉइंटर को नोड 3 पर सेट करता है। उसके तुरंत बाद, नोड 2 हटा दिया जाता है और नोड 1 का पॉइंटर नोड 4 पर सेट कर दिया जाता है। अब नोड 3 अब पहुंच योग्य नहीं है।

प्राथमिकता कतार तक समवर्ती पहुंच को समवर्ती पढ़ें, समवर्ती लिखें (सीआरसीडब्ल्यू) PRAM मॉडल पर क्रियान्वित किया जा सकता है। निम्नलिखित में प्राथमिकता कतार को स्किप सूची के रूप में क्रियान्वित किया गया है। इसके अतिरिक्त , परमाणु तुल्यकालन आदिम, तुलना-और-स्वैप, का उपयोग स्किप सूची को लॉक (कंप्यूटर विज्ञान)-मुक्त बनाने के लिए किया जाता है। स्किप सूची के नोड्स में अद्वितीय कुंजी, प्राथमिकता, पॉइंटर (कंप्यूटर प्रोग्रामिंग) की सरणी डेटा संरचना, प्रत्येक स्तर के लिए, अगले नोड्स और डिलीट मार्क सम्मिलित होते हैं। यदि नोड किसी प्रक्रिया द्वारा हटाया जाने वाला है तो डिलीट मार्क चिह्नित करता है। यह सुनिश्चित करता है कि अन्य प्रक्रियाएं विलोपन पर उचित रूप से प्रतिक्रिया कर सकती हैं।

• इन्सर्ट(ई): सबसे पहले, कुंजी और प्राथमिकता वाला नया नोड बनाया जाता है। इसके अतिरिक्त , नोड को कई स्तर दिए गए हैं, जो पॉइंटर्स की सरणी के आकार को निर्धारित करते हैं। फिर नए नोड को सम्मिलित करने की सही स्थिति खोजने के लिए खोज की जाती है। खोज पहले नोड से और उच्चतम स्तर से शुरू होती है। फिर स्किप सूची को निम्नतम स्तर तक ले जाया जाता है जब तक कि सही स्थिति नहीं मिल जाती। खोज के दौरान, प्रत्येक स्तर के लिए अंतिम ट्रैवर्स किए गए नोड को उस स्तर पर नए नोड के लिए मूल नोड के रूप में सहेजा जाएगा। इसके अतिरिक्त , मूल नोड का सूचक जिस नोड की ओर इशारा करता है, उस स्तर पर नए नोड के उत्तराधिकारी नोड के रूप में सहेजा जाएगा। बाद में, नए नोड के प्रत्येक स्तर के लिए, मूल नोड के पॉइंटर्स को नए नोड पर सेट किया जाएगा। अंत में, नए नोड के प्रत्येक स्तर के लिए पॉइंटर्स को संबंधित उत्तराधिकारी नोड्स पर सेट किया जाएगा।
• एक्स्ट्रेक्ट-मिन: सबसे पहले, स्किप सूची को तब तक ट्रैवर्स किया जाता है जब तक कि नोड नहीं पहुंच जाता है जिसका डिलीट मार्क सेट नहीं है। यह डिलीट मार्क उस नोड के लिए सत्य पर सेट है। अंत में हटाए गए नोड के मूल नोड्स के पॉइंटर्स अपडेट किए जाते हैं।

यदि प्राथमिकता कतार तक समवर्ती पहुंच की अनुमति दी जाती है, तो दो प्रक्रियाओं के बीच टकराव उत्पन्न हो सकता है। उदाहरण के लिए, यदि प्रक्रिया नया नोड डालने का प्रयास कर रही है, किन्तु उसी समय अन्य प्रक्रिया उस नोड के पूर्ववर्ती को हटाने वाली है तो विरोध उत्पन्न होता है। There is a risk that the new node is added to the skip list, yet it is not longer reachable. ([[:File:concurrent_prio_queue_conflict.svg|छवि देखें)

के-तत्व संचालन

इस सेटिंग में, प्राथमिकता कतार पर संचालन को बैच के लिए सामान्यीकृत किया जाता है ${\textstyle k}$ तत्व. उदाहरण के लिए, k_extract-min हटा देता है ${\textstyle k}$ प्राथमिकता कतार के सबसे छोटे तत्व और उन्हें लौटाता है।

समानांतर प्रोग्रामिंग मॉडल | साझा-मेमोरी सेटिंग में, समानांतर प्राथमिकता कतार को समानांतर बाइनरी खोज ट्री और जॉइन-आधारित ट्री एल्गोरिदम का उपयोग करके आसानी से कार्यान्वित किया जा सकता है। विशेष रूप से, k_extract-min बाइनरी सर्च ट्री पर विभाजन से मेल खाता है ${\textstyle O(\log n)}$ निवेस और ट्री की पैदावार जिसमें सम्मिलित है ${\textstyle k}$ सबसे छोटे तत्व. k_insert को मूल प्राथमिकता कतार और सम्मिलन के बैच के संघ द्वारा क्रियान्वित किया जा सकता है। यदि बैच पहले से ही कुंजी द्वारा क्रमबद्ध है, तो k_insert है ${\textstyle O(k\log(1+{\frac {n}{k}}))}$ निवेस । अन्यथा, हमें पहले बैच को सॉर्ट करना होगा, इसलिए निवेस होगी ${\textstyle O(k\log(1+{\frac {n}{k}})+k\log k)=O(k\log n)}$. प्राथमिकता कतार के लिए अन्य ऑपरेशन इसी तरह क्रियान्वित किए जा सकते हैं। उदाहरण के लिए, k_decrease-key को पहले अंतर और फिर यूनियन क्रियान्वित करके किया जा सकता है, जो पहले तत्वों को हटाता है और फिर उन्हें अद्यतन कुंजी के साथ वापस सम्मिलित करता है। ये सभी ऑपरेशन अत्यधिक समानांतर हैं, और सैद्धांतिक और व्यावहारिक दक्षता संबंधित शोध पत्रों में पाई जा सकती है।

इस खंड का शेष भाग वितरित मेमोरी पर कतार-आधारित एल्गोरिदम पर चर्चा करता है। हम मानते हैं कि प्रत्येक प्रोसेसर की अपनी स्थानीय मेमोरी और स्थानीय (अनुक्रमिक) प्राथमिकता कतार होती है। वैश्विक (समानांतर) प्राथमिकता कतार के तत्व सभी प्रोसेसरों में वितरित किए जाते हैं।

k_extract-min को तीन प्रोसेसर के साथ प्राथमिकता कतार पर निष्पादित किया जाता है। हरे तत्व लौटाए जाते हैं और प्राथमिकता कतार से हटा दिए जाते हैं।

k_insert ऑपरेशन प्रोसेसर को तत्वों को समान रूप से यादृच्छिक रूप से निर्दिष्ट करता है जो तत्वों को उनकी स्थानीय कतारों में सम्मिलित करता है। ध्यान दें कि एकल तत्व अभी भी कतार में डाले जा सकते हैं। इस रणनीति का उपयोग करते हुए वैश्विक सबसे छोटे तत्व उच्च संभावना वाले प्रत्येक प्रोसेसर के स्थानीय सबसे छोटे तत्वों के संघ में हैं। इस प्रकार प्रत्येक प्रोसेसर वैश्विक प्राथमिकता कतार का प्रतिनिधि हिस्सा रखता है।

इस संपत्ति का उपयोग तब किया जाता है जब k_extract-min को सबसे छोटे के रूप में निष्पादित किया जाता है ${\textstyle m}$ प्रत्येक स्थानीय कतार के तत्वों को हटा दिया जाता है और परिणाम सेट में एकत्र किया जाता है। परिणाम सेट के तत्व अभी भी अपने मूल प्रोसेसर से जुड़े हुए हैं। तत्वों की संख्या ${\textstyle m}$ प्रत्येक स्थानीय कतार से हटाया जाना इस पर निर्भर करता है ${\textstyle k}$ और प्रोसेसर की संख्या ${\textstyle p}$.

समानांतर चयन द्वारा ${\textstyle k}$ परिणाम सेट के सबसे छोटे तत्व निर्धारित किए जाते हैं। उच्च संभावना के साथ ये वैश्विक हैं ${\textstyle k}$ सबसे छोटे तत्व. अगर नहीं, ${\textstyle m}$ प्रत्येक स्थानीय कतार से तत्वों को फिर से हटा दिया जाता है और परिणाम सेट में डाल दिया जाता है। यह ग्लोबल तक किया जाता है ${\textstyle k}$ परिणाम सेट में सबसे छोटे तत्व हैं। अब ये ${\textstyle k}$ तत्वों को वापस किया जा सकता है। परिणाम सेट के अन्य सभी तत्व वापस उनकी स्थानीय कतार में डाल दिए जाते हैं। K_extract-min का चलने का समय अपेक्षित है ${\textstyle O({\frac {k}{p}}\log(n))}$, कहाँ ${\textstyle k=\Omega (p\cdot \log(p))}$ और ${\textstyle n}$ प्राथमिकता कतार का आकार है.

k_extract-min ऑपरेशन के बाद परिणाम सेट के शेष तत्वों को सीधे स्थानीय कतार में वापस न ले जाकर प्राथमिकता कतार में और सुधार किया जा सकता है। यह परिणाम सेट और स्थानीय कतारों के बीच हर समय आगे और पीछे जाने वाले तत्वों को बचाता है।

साथ कई तत्वों को हटाकर काफी तेजी लाई जा सकती है। किन्तु सभी एल्गोरिदम इस प्रकार की प्राथमिकता कतार का उपयोग नहीं कर सकते हैं। उदाहरण के लिए डिज्क्स्ट्रा का एल्गोरिदम साथ कई नोड्स पर काम नहीं कर सकता है। एल्गोरिथ्म प्राथमिकता कतार से सबसे छोटी दूरी वाले नोड को लेता है और उसके सभी पड़ोसी नोड्स के लिए नई दूरी की गणना करता है। अगर आप निकालेंगे ${\textstyle k}$ नोड्स, नोड पर काम करने से दूसरे नोड की दूरी बदल सकती है ${\textstyle k}$ नोड्स. इसलिए के-एलिमेंट ऑपरेशंस का उपयोग करने से डिज्क्स्ट्रा के एल्गोरिदम की लेबल सेटिंग संपत्ति नष्ट हो जाती है।

यह भी देखें

• बैच कतार
• कमांड कतार
• कार्य अनुसूचक

अग्रिम पठन

• Cormen, Thomas H.; Leiserson, Charles E.; Rivest, Ronald L.; Stein, Clifford (2001) [1990]. "Section 6.5: Priority queues". Introduction to Algorithms (2nd ed.). MIT Press and McGraw-Hill. pp. 138–142. ISBN 0-262-03293-7.

बाहरी संबंध

• C++ reference for std::priority_queue
• Descriptions by Lee Killough
• PQlib - Open source Priority Queue library for C
• libpqueue is a generic priority queue (heap) implementation (in C) used by the Apache HTTP Server project.
• Survey of known priority queue structures by Stefan Xenos
• UC Berkeley - Computer Science 61B - Lecture 24: Priority Queues (video) - introduction to priority queues using binary heap