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

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

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

संचालन

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

• 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'वीं सूची, और अद्यतन 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)	?

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

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

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

Name	Priority Queue Implementation	Best	Average	Worst
Heapsort	Heap	$n\log(n)$	$n\log(n)$	$n\log(n)$
Smoothsort	Leonardo Heap	$n$	$n\log(n)$	$n\log(n)$
Selection sort	Unordered Array	$n^{2}$	$n^{2}$	$n^{2}$
Insertion sort	Ordered Array	$n$	$n^{2}$	$n^{2}$
Tree sort	Self-balancing binary search tree	$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