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

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

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

संचालन

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

• 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) पुल टाइम),

insert(node)
{
    list.append(node)
}
pull()
{
    highest = list.get_first_element()
    foreach node in list
    {
        if highest.priority < node.priority
        {
            highest = node
        }
    }
    list.remove(highest)
    return highest
}

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

insert(node)
{
    foreach (index, element) in list
    {
        if node.priority < element.priority
        {
            list.insert_at_index(node,index)
            break
        }
    }
}

pull()
{
    highest = list.get_at_index(list.length-1)
    list.remove(highest)
    return highest
}

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

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

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

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

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

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

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

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

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

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

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

पुस्तकालय

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

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

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

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

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

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

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

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

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

अनुप्रयोग

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

के-अवयव संचालन

इस सेटिंग में, प्राथमिकता क्रम पर संचालन को बैच के लिए सामान्यीकृत किया जाता है ${\textstyle k}$ अवयव .

उदाहरण के लिए, k_अर्क-मिन हटा देता है ${\textstyle k}$ प्राथमिकता क्रम के सबसे छोटे अवयव और उन्हें लौटाता है।

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

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

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

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

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

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

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

इसके अतिरिक्त अवयव को हटाकर अधिक तीव्र लाई जा सकती है। किन्तु सभी एल्गोरिदम इस प्रकार की प्राथमिकता क्रम का उपयोग नहीं कर सकते हैं। उदाहरण के लिए डिज्क्स्ट्रा का एल्गोरिदम साथ कई नोड्स पर कार्य नहीं कर सकता है। एल्गोरिथ्म प्राथमिकता क्रम से सबसे छोटी दूरी वाले नोड को लेता है और उसके सभी निकटतम नोड्स के लिए नई दूरी की गणना करता है। यदि आप निकालेंगे ${\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