प्राथमिकता कतार: Difference between revisions

Revision as of 18:56, 15 July 2023

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

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

संचालन

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

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)
 सूची.निकालें(उच्चतम)
 उच्चतम वापसी
}

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

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

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

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

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

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

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

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

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

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

Here are time complexities^[5] 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^[5]	Θ(1)	Θ(log n)	O(log n)	O(log n)	Θ(n)
Leftist	Θ(1)	Θ(log n)	Θ(log n)	O(log n)	Θ(log n)
Binomial^[5]^[6]	Θ(1)	Θ(log n)	Θ(1)^{[lower-alpha 1]}	Θ(log n)	O(log n)^{[lower-alpha 2]}
Fibonacci^[5]^[7]	Θ(1)	O(log n)^{[lower-alpha 1]}	Θ(1)	Θ(1)^{[lower-alpha 1]}	Θ(1)
Pairing^[8]	Θ(1)	O(log n)^{[lower-alpha 1]}	Θ(1)	o(log n)^{[lower-alpha 1]}^{[lower-alpha 3]}	Θ(1)
Brodal^[11]^{[lower-alpha 4]}	Θ(1)	O(log n)	Θ(1)	Θ(1)	Θ(1)
Rank-pairing^[13]	Θ(1)	O(log n)^{[lower-alpha 1]}	Θ(1)	Θ(1)^{[lower-alpha 1]}	Θ(1)
Strict Fibonacci^[14]	Θ(1)	O(log n)	Θ(1)	Θ(1)	Θ(1)
2–3 heap^[15]	O(log n)	O(log n)^{[lower-alpha 1]}	O(log n)^{[lower-alpha 1]}	Θ(1)	?

↑ ^1.0 ^1.1 ^1.2 ^1.3 ^1.4 ^1.5 ^1.6 ^1.7 ^1.8 Amortized time.
↑ n is the size of the larger heap.
↑ Lower bound of $\Omega (\log \log n),$ ^[9] upper bound of $O(2^{2{\sqrt {\log \log n}}}).$ ^[10]
↑ Brodal and Okasaki later describe a persistent variant with the same bounds except for decrease-key, which is not supported. Heaps with n elements can be constructed bottom-up in O(n).^[12]

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

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

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

नाम	प्राथमिकता कतार कार्यान्वयन	श्रेष्ठ	औसत	निकृष्टतम
हीपसॉर्ट	हीप	$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)$

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

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

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

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

पुस्तकालय

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

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

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

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

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

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

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

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

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

अनुप्रयोग

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

यदि प्राथमिकता कतार तक समवर्ती पहुंच की अनुमति दी जाती है, तो दो प्रक्रियाओं के बीच टकराव उत्पन्न हो सकता है। उदाहरण के लिए, यदि प्रक्रिया नया नोड डालने का प्रयास कर रही है, किन्तु उसी समय अन्य प्रक्रिया उस नोड के पूर्ववर्ती को हटाने वाली है तो विरोध उत्पन्न होता है।^[20] यह संकटजनक है कि नया नोड स्किप सूची में जोड़ा गया है, फिर भी यह अब पहुंच योग्य नहीं है. ([[:फ़ाइल: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 को पहले अंतर और फिर यूनियन क्रियान्वित करके किया जा सकता है, जो पहले अवयव ों को हटाता है और फिर उन्हें अद्यतन कुंजी के साथ वापस सम्मिलित करता है। ये सभी ऑपरेशन अत्यधिक समानांतर हैं, और सैद्धांतिक और व्यावहारिक दक्षता संबंधित शोध पत्रों में पाई जा सकती है।^[22]^[23]

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

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

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

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

^[24]

समानांतर चयन द्वारा ${\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}$ प्राथमिकता कतार का आकार है.^[24]

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

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

यह भी देखें

संदर्भ

↑ Cormen, Thomas H.; Leiserson, Charles E.; Rivest, Ronald L.; Stein, Clifford (2001) [1990]. "Chapter 20: Fibonacci Heaps". Introduction to Algorithms (2nd ed.). MIT Press and McGraw-Hill. pp. 476–497. ISBN 0-262-03293-7. तृतीय संस्करण, पृ. 518.
↑ Skiena, Steven (2010). एल्गोरिथम डिज़ाइन मैनुअल (2nd ed.). Springer Science+Business Media. ISBN 978-1-849-96720-4.
↑ P. van Emde Boas. Preserving order in a forest in less than logarithmic time. In Proceedings of the 16th Annual Symposium on Foundations of Computer Science, pages 75-84. IEEE Computer Society, 1975.
↑ Michael L. Fredman and Dan E. Willard. Surpassing the information theoretic bound with fusion trees. Journal of Computer and System Sciences, 48(3):533-551, 1994
↑ ^5.0 ^5.1 ^5.2 ^5.3 Cormen, Thomas H.; Leiserson, Charles E.; Rivest, Ronald L. (1990). Introduction to Algorithms (1st ed.). MIT Press and McGraw-Hill. ISBN 0-262-03141-8.
↑ "Binomial Heap | Brilliant Math & Science Wiki". brilliant.org (in English). Retrieved 2019-09-30.
↑ Fredman, Michael Lawrence; Tarjan, Robert E. (July 1987). "Fibonacci heaps and their uses in improved network optimization algorithms" (PDF). Journal of the Association for Computing Machinery. 34 (3): 596–615. CiteSeerX 10.1.1.309.8927. doi:10.1145/28869.28874.
↑ Iacono, John (2000), "Improved upper bounds for pairing heaps", Proc. 7th Scandinavian Workshop on Algorithm Theory (PDF), Lecture Notes in Computer Science, vol. 1851, Springer-Verlag, pp. 63–77, arXiv:1110.4428, CiteSeerX 10.1.1.748.7812, doi:10.1007/3-540-44985-X_5, ISBN 3-540-67690-2
↑ Fredman, Michael Lawrence (July 1999). "On the Efficiency of Pairing Heaps and Related Data Structures" (PDF). Journal of the Association for Computing Machinery. 46 (4): 473–501. doi:10.1145/320211.320214.
↑ Pettie, Seth (2005). Towards a Final Analysis of Pairing Heaps (PDF). FOCS '05 Proceedings of the 46th Annual IEEE Symposium on Foundations of Computer Science. pp. 174–183. CiteSeerX 10.1.1.549.471. doi:10.1109/SFCS.2005.75. ISBN 0-7695-2468-0.
↑ Brodal, Gerth S. (1996), "Worst-Case Efficient Priority Queues" (PDF), Proc. 7th Annual ACM-SIAM Symposium on Discrete Algorithms, pp. 52–58
↑ Goodrich, Michael T.; Tamassia, Roberto (2004). "7.3.6. Bottom-Up Heap Construction". Data Structures and Algorithms in Java (3rd ed.). pp. 338–341. ISBN 0-471-46983-1.
↑ Haeupler, Bernhard; Sen, Siddhartha; Tarjan, Robert E. (November 2011). "Rank-pairing heaps" (PDF). SIAM J. Computing. 40 (6): 1463–1485. doi:10.1137/100785351.
↑ Brodal, Gerth Stølting; Lagogiannis, George; Tarjan, Robert E. (2012). Strict Fibonacci heaps (PDF). Proceedings of the 44th symposium on Theory of Computing - STOC '12. pp. 1177–1184. CiteSeerX 10.1.1.233.1740. doi:10.1145/2213977.2214082. ISBN 978-1-4503-1245-5.
↑ Takaoka, Tadao (1999), Theory of 2–3 Heaps (PDF), p. 12
↑ Thorup, Mikkel (2007). "प्राथमिकता कतारों और छँटाई के बीच समानता". Journal of the ACM. 54 (6): 28. doi:10.1145/1314690.1314692. S2CID 11494634.
↑ "संग्रहीत प्रति" (PDF). Archived (PDF) from the original on 2011-07-20. Retrieved 2011-02-10.
↑ Cormen, Thomas H.; Leiserson, Charles E.; Rivest, Ronald L.; Stein, Clifford (2009) [1990]. Introduction to Algorithms (3rd ed.). MIT Press and McGraw-Hill. p. 634. ISBN 0-262-03384-4. "In order to implement Prim's algorithm efficiently, we need a fast way to select a new edge to add to the tree formed by the edges in A."
↑ "Prim's Algorithm". Geek for Geeks. Archived from the original on 9 September 2014. Retrieved 12 September 2014.
↑ ^20.0 ^20.1 Sundell, Håkan; Tsigas, Philippas (2005). "मल्टी-थ्रेड सिस्टम के लिए तेज़ और लॉक-मुक्त समवर्ती प्राथमिकता कतारें". Journal of Parallel and Distributed Computing. 65 (5): 609–627. doi:10.1109/IPDPS.2003.1213189. S2CID 20995116.
↑ Lindén, Jonsson (2013), "A Skiplist-Based Concurrent Priority Queue with Minimal Memory Contention", Technical Report 2018-003 (in Deutsch)
↑ Blelloch, Guy E.; Ferizovic, Daniel; Sun, Yihan (2016), "Just Join for Parallel Ordered Sets", Symposium on Parallel Algorithms and Architectures, Proc. of 28th ACM Symp. Parallel Algorithms and Architectures (SPAA 2016), ACM, pp. 253–264, arXiv:1602.02120, doi:10.1145/2935764.2935768, ISBN 978-1-4503-4210-0, S2CID 2897793
↑ Blelloch, Guy E.; Ferizovic, Daniel; Sun, Yihan (2018), "PAM: parallel augmented maps", Proceedings of the 23rd ACM SIGPLAN Symposium on Principles and Practice of Parallel Programming, ACM, pp. 290–304
↑ ^24.0 ^24.1 Sanders, Peter; Mehlhorn, Kurt; Dietzfelbinger, Martin; Dementiev, Roman (2019). अनुक्रमिक और समानांतर एल्गोरिदम और डेटा संरचनाएं - मूल टूलबॉक्स. Springer International Publishing. pp. 226–229. doi:10.1007/978-3-030-25209-0. ISBN 978-3-030-25208-3. S2CID 201692657.

अग्रिम पठन

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

[amortized-7] 1.0 ^1.1 ^1.2 ^1.3 ^1.4 ^1.5 ^1.6 ^1.7 ^1.8 Amortized time.

[meld-8] s the size of the larger heap.

[pairingdecreasekey-13] Lower bound of $\Omega (\log \log n),$ ^[9] upper bound of $O(2^{2{\sqrt {\log \log n}}}).$ ^[10]

[brodal-16] Brodal and Okasaki later describe a persistent variant with the same bounds except for decrease-key, which is not supported. Heaps with n elements can be constructed bottom-up in O(n).^[12]

[CLRS_priority_queue_pp476-1] Cormen, Thomas H.; Leiserson, Charles E.; Rivest, Ronald L.; Stein, Clifford (2001) [1990]. "Chapter 20: Fibonacci Heaps". Introduction to Algorithms (2nd ed.). MIT Press and McGraw-Hill. pp. 476–497. ISBN 0-262-03293-7. तृतीय संस्करण, पृ. 518.

[2] Skiena, Steven (2010). एल्गोरिथम डिज़ाइन मैनुअल (2nd ed.). Springer Science+Business Media. ISBN 978-1-849-96720-4.

[3] P. van Emde Boas. Preserving order in a forest in less than logarithmic time. In Proceedings of the 16th Annual Symposium on Foundations of Computer Science, pages 75-84. IEEE Computer Society, 1975.

[4] Michael L. Fredman and Dan E. Willard. Surpassing the information theoretic bound with fusion trees. Journal of Computer and System Sciences, 48(3):533-551, 1994

[CLRS-5] 5.0 ^5.1 ^5.2 ^5.3 Cormen, Thomas H.; Leiserson, Charles E.; Rivest, Ronald L. (1990). Introduction to Algorithms (1st ed.). MIT Press and McGraw-Hill. ISBN 0-262-03141-8.

[6] "Binomial Heap | Brilliant Math & Science Wiki". brilliant.org (in English). Retrieved 2019-09-30.

[Fredman_And_Tarjan-9] Fredman, Michael Lawrence; Tarjan, Robert E. (July 1987). "Fibonacci heaps and their uses in improved network optimization algorithms" (PDF). Journal of the Association for Computing Machinery. 34 (3): 596–615. CiteSeerX 10.1.1.309.8927. doi:10.1145/28869.28874.

[Iacono-10] Iacono, John (2000), "Improved upper bounds for pairing heaps", Proc. 7th Scandinavian Workshop on Algorithm Theory (PDF), Lecture Notes in Computer Science, vol. 1851, Springer-Verlag, pp. 63–77, arXiv:1110.4428, CiteSeerX 10.1.1.748.7812, doi:10.1007/3-540-44985-X_5, ISBN 3-540-67690-2

[Fredman1999-11] Fredman, Michael Lawrence (July 1999). "On the Efficiency of Pairing Heaps and Related Data Structures" (PDF). Journal of the Association for Computing Machinery. 46 (4): 473–501. doi:10.1145/320211.320214.

[12] Pettie, Seth (2005). Towards a Final Analysis of Pairing Heaps (PDF). FOCS '05 Proceedings of the 46th Annual IEEE Symposium on Foundations of Computer Science. pp. 174–183. CiteSeerX 10.1.1.549.471. doi:10.1109/SFCS.2005.75. ISBN 0-7695-2468-0.

[14] Brodal, Gerth S. (1996), "Worst-Case Efficient Priority Queues" (PDF), Proc. 7th Annual ACM-SIAM Symposium on Discrete Algorithms, pp. 52–58

[15] Goodrich, Michael T.; Tamassia, Roberto (2004). "7.3.6. Bottom-Up Heap Construction". Data Structures and Algorithms in Java (3rd ed.). pp. 338–341. ISBN 0-471-46983-1.

[17] Haeupler, Bernhard; Sen, Siddhartha; Tarjan, Robert E. (November 2011). "Rank-pairing heaps" (PDF). SIAM J. Computing. 40 (6): 1463–1485. doi:10.1137/100785351.

[18] Brodal, Gerth Stølting; Lagogiannis, George; Tarjan, Robert E. (2012). Strict Fibonacci heaps (PDF). Proceedings of the 44th symposium on Theory of Computing - STOC '12. pp. 1177–1184. CiteSeerX 10.1.1.233.1740. doi:10.1145/2213977.2214082. ISBN 978-1-4503-1245-5.

[19] Takaoka, Tadao (1999), Theory of 2–3 Heaps (PDF), p. 12

[20] Thorup, Mikkel (2007). "प्राथमिकता कतारों और छँटाई के बीच समानता". Journal of the ACM. 54 (6): 28. doi:10.1145/1314690.1314692. S2CID 11494634.

[21] "संग्रहीत प्रति" (PDF). Archived (PDF) from the original on 2011-07-20. Retrieved 2011-02-10.

[CLR-22] Cormen, Thomas H.; Leiserson, Charles E.; Rivest, Ronald L.; Stein, Clifford (2009) [1990]. Introduction to Algorithms (3rd ed.). MIT Press and McGraw-Hill. p. 634. ISBN 0-262-03384-4. "In order to implement Prim's algorithm efficiently, we need a fast way to select a new edge to add to the tree formed by the edges in A."

[GEEKS-23] "Prim's Algorithm". Geek for Geeks. Archived from the original on 9 September 2014. Retrieved 12 September 2014.

[skiplist-24] 20.0 ^20.1 Sundell, Håkan; Tsigas, Philippas (2005). "मल्टी-थ्रेड सिस्टम के लिए तेज़ और लॉक-मुक्त समवर्ती प्राथमिकता कतारें". Journal of Parallel and Distributed Computing. 65 (5): 609–627. doi:10.1109/IPDPS.2003.1213189. S2CID 20995116.

[25] Lindén, Jonsson (2013), "A Skiplist-Based Concurrent Priority Queue with Minimal Memory Contention", Technical Report 2018-003 (in Deutsch)

[join-based-26] Blelloch, Guy E.; Ferizovic, Daniel; Sun, Yihan (2016), "Just Join for Parallel Ordered Sets", Symposium on Parallel Algorithms and Architectures, Proc. of 28th ACM Symp. Parallel Algorithms and Architectures (SPAA 2016), ACM, pp. 253–264, arXiv:1602.02120, doi:10.1145/2935764.2935768, ISBN 978-1-4503-4210-0, S2CID 2897793

[pam-27] Blelloch, Guy E.; Ferizovic, Daniel; Sun, Yihan (2018), "PAM: parallel augmented maps", Proceedings of the 23rd ACM SIGPLAN Symposium on Principles and Practice of Parallel Programming, ACM, pp. 290–304

[AlgToolbox-28] 24.0 ^24.1 Sanders, Peter; Mehlhorn, Kurt; Dietzfelbinger, Martin; Dementiev, Roman (2019). अनुक्रमिक और समानांतर एल्गोरिदम और डेटा संरचनाएं - मूल टूलबॉक्स. Springer International Publishing. pp. 226–229. doi:10.1007/978-3-030-25209-0. ISBN 978-3-030-25208-3. S2CID 201692657.

[1]

[2]

[3]

[4]

[5]

[6]

[lower-alpha 1]

[lower-alpha 2]

[7]

[8]

[lower-alpha 3]

[11]

[lower-alpha 4]

[13]

[14]

[15]

[9]

[10]

[12]

[16]

[17]

[18]

[19]

[20]

[21]

[22]

[23]

[24]

@@ Line 2: / Line 2: @@
-[[कंप्यूटर विज्ञान]] में, '''प्राथमिकता कतार''' एक नियमित कतार या [[स्टैक (सार डेटा प्रकार)|स्टैक]] [[स्टैक (सार डेटा प्रकार)|डेटा]] संरचना के समान एक अमूर्त डेटा-प्रकार है। प्राथमिकता कतार में प्रत्येक तत्व की एक संबद्ध प्राथमिकता होती है। प्राथमिकता कतार में, उच्च प्राथमिकता वाले तत्वों को लघु  प्राथमिकता वाले तत्वों से पहले रखा  जाता है।और  कुछ कार्यान्वयन में, यदि दो तत्वों की प्राथमिकता समान है, तो उन्हें उसी क्रम में रखा  जाता है जिसमें वे पंक्तिबद्ध थे। अन्य कार्यान्वयन में, समान प्राथमिकता वाले तत्वों का क्रम अपरिभाषित है।
+[[कंप्यूटर विज्ञान]] में, '''प्राथमिकता कतार''' एक नियमित कतार या [[स्टैक (सार डेटा प्रकार)|स्टैक]] [[स्टैक (सार डेटा प्रकार)|डेटा]] संरचना के समान एक अमूर्त डेटा-प्रकार है। प्राथमिकता कतार में प्रत्येक अवयव  की एक संबद्ध प्राथमिकता होती है। प्राथमिकता कतार में, उच्च प्राथमिकता वाले अवयव  को लघु  प्राथमिकता वाले अवयव ों से पहले रखा  जाता है।और  कुछ कार्यान्वयन में, यदि दो अवयव  की प्राथमिकता समान है, तो उन्हें उसी क्रम में रखा  जाता है जिसमें वे पंक्तिबद्ध थे। अन्य कार्यान्वयन में, समान प्राथमिकता वाले अवयव  का क्रम अपरिभाषित है।
 जबकि प्राथमिकता कतारें प्रायः  हीप (डेटा संरचना) का उपयोग करके कार्यान्वित की जाती हैं, इस प्रकार से यह अवधारणात्मक रूप से हीप से अलग होती हैं। किन्तु प्राथमिकता कतार  अमूर्त डेटा संरचना है जैसे सूची (अमूर्त डेटा संरचना) या [[सहयोगी सरणी]]; जिस तरह  सूची को  लिंक की गई सूची के साथ या  ऐरे डेटा संरचना के साथ क्रियान्वित  किया जा सकता है,  प्राथमिकता कतार के रूप में  या किसी अन्य विधि जैसे कि  अनियंत्रित सरणी के साथ क्रियान्वित  किया जा सकता है।
@@ Line 10: / Line 13: @@
 प्राथमिकता कतार को कम से कम निम्नलिखित परिचालनों का समर्थन करना चाहिए:
-* is_empty: जांचें कि क्या कतार में कोई तत्व नहीं है।
+* is_empty: जांचें कि क्या कतार में कोई अवयव  नहीं है।
-* Insert_with_priority: संबंधित प्राथमिकता के साथ कतार (सार डेटा संरचना) में  [[तत्व (गणित)]] सम्मिलित है ।
+* Insert_with_priority: संबंधित प्राथमिकता के साथ कतार (सार डेटा संरचना) में  [[तत्व (गणित)|अवयव  (गणित)]] सम्मिलित है ।
-*pull_highest_priority_element: उस तत्व को कतार से रिमूव कर  दें जिसकी सर्वोच्च प्राथमिकता है, और उसे वापस कर दें।
+*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 बनाने के लिए जोड़ा जा सकता है।
+*: इसके अतरिक्त  इसे अलग-अलग peek_at_highest_priority_element और delete_element फ़ंक्शंस के रूप में निर्दिष्ट किया जा सकता है, जिन्हें पुल_highest_priority_element बनाने के लिए जोड़ा जा सकता है।
-इसके अतिरिक्त , [[पीक (डेटा प्रकार ऑपरेशन)|पीक (डेटा संरचना ऑपरेशन)]] (इस संदर्भ में प्रायः  फाइंड-मैक्स या फाइंड-मिन कहा जाता है), जो उच्चतम-प्राथमिकता वाले तत्व को लौटाता है किन्तु  कतार को संशोधित नहीं करता है, इसे अधिक  बार क्रियान्वित  किया जाता है, और लगभग सदैव  बिग ओ में निष्पादित होता है अंकन O(1) समय. यह ऑपरेशन और इसका O(1) प्रदर्शन प्राथमिकता कतारों के कई अनुप्रयोगों के लिए महत्वपूर्ण है।
+इसके अतिरिक्त , [[पीक (डेटा प्रकार ऑपरेशन)|पीक (डेटा संरचना ऑपरेशन)]] (इस संदर्भ में प्रायः  फाइंड-मैक्स या फाइंड-मिन कहा जाता है), जो उच्चतम-प्राथमिकता वाले अवयव  को लौटाता है किन्तु  कतार को संशोधित नहीं करता है, इसे अधिक  बार क्रियान्वित  किया जाता है, और लगभग सदैव  बिग ओ में निष्पादित होता है अंकन O(1) समय. यह ऑपरेशन और इसका O(1) प्रदर्शन प्राथमिकता कतारों के कई अनुप्रयोगों के लिए महत्वपूर्ण है।
-इस प्रकार से अधिक उन्नत कार्यान्वयन अधिक जटिल संचालन का समर्थन कर सकते हैं, जैसे कि पुल_लोवेस्ट_प्रायोरिटी_एलिमेंट, पहले कुछ उच्चतम या निम्न-प्राथमिकता वाले तत्वों का निरीक्षण करना, कतार को साफ़ करना, कतार के सबसेट को साफ़ करना, बैच सम्मिलित करना, दो या दो से अधिक कतारों को  में विलय करना,किसी  भी तत्व  प्राथमिकता बढ़ाना आदि।
+इस प्रकार से अधिक उन्नत कार्यान्वयन अधिक जटिल संचालन का समर्थन कर सकते हैं, जैसे कि पुल_लोवेस्ट_प्रायोरिटी_एलिमेंट, पहले कुछ उच्चतम या निम्न-प्राथमिकता वाले अवयव ों का निरीक्षण करना, कतार को साफ़ करना, कतार के सबसेट को साफ़ करना, बैच सम्मिलित करना, दो या दो से अधिक कतारों को  में विलय करना,किसी  भी अवयव   प्राथमिकता बढ़ाना आदि।
-स्टैक (अमूर्त डेटा संरचना) और क्यू (अमूर्त डेटा संरचना) को विशेष प्रकार की प्राथमिकता कतारों के रूप में कार्यान्वित किया जा सकता है, प्राथमिकता उस क्रम से निर्धारित होती है जिसमें तत्व इन्सर्ट किये  जाते हैं। इस प्रकार से  स्टैक में, प्रत्येक सम्मिलित तत्व की प्राथमिकता नीरस रूप से बढ़ रही है; इस प्रकार, इन्सर्ट किया  गया अंतिम तत्व सदैव  सबसे प्रथम   पुनर्प्राप्त किया जाता है। किन्तु   कतार में, प्रत्येक सम्मिलित तत्व की प्राथमिकता नीरस रूप से घट रही है; इस प्रकार, समिलित किया गया  गया प्रथम  तत्व सदैव  सर्वप्रथम  पुनर्प्राप्त किया जाता है।
+स्टैक (अमूर्त डेटा संरचना) और क्यू (अमूर्त डेटा संरचना) को विशेष प्रकार की प्राथमिकता कतारों के रूप में कार्यान्वित किया जा सकता है, प्राथमिकता उस क्रम से निर्धारित होती है जिसमें अवयव  इन्सर्ट किये  जाते हैं। इस प्रकार से  स्टैक में, प्रत्येक सम्मिलित अवयव  की प्राथमिकता नीरस रूप से बढ़ रही है; इस प्रकार, इन्सर्ट किया  गया अंतिम अवयव  सदैव  सबसे प्रथम   पुनर्प्राप्त किया जाता है। किन्तु   कतार में, प्रत्येक सम्मिलित अवयव  की प्राथमिकता नीरस रूप से घट रही है; इस प्रकार, समिलित किया गया  गया प्रथम  अवयव  सदैव  सर्वप्रथम  पुनर्प्राप्त किया जाता है।
 == कार्यान्वयन ==
@@ Line 29: / Line 32: @@
 प्राथमिकता कतार को क्रियान्वित  करने के अनेक  सरल,सामान्यतः अप्रभावी विधि  हैं। वे यह समझने में सहायता  करने के लिए  सादृश्य प्रदान करते हैं कि प्राथमिकता कतार क्या है।
-इस प्रकार से उदाहरण के लिए, कोई सभी तत्वों को  अवर्गीकृत सूची (O(1) सम्मिलन टाइम ) में रख सकता है। जब भी सर्वोच्च-प्राथमिकता वाले तत्व का अनुरोध किया जाए, तो सभी तत्वों में से सर्वोच्च प्राथमिकता वाले तत्व को खोजें। (O(n) पुल टाइम),
+इस प्रकार से उदाहरण के लिए, कोई सभी अवयव ों को  अवर्गीकृत सूची (O(1) सम्मिलन टाइम ) में रख सकता है। जब भी सर्वोच्च-प्राथमिकता वाले अवयव  का अनुरोध किया जाए, तो सभी अवयव ों में से सर्वोच्च प्राथमिकता वाले अवयव  को खोजें। (O(n) पुल टाइम),
   'सम्मिलित करें' (नोड)
@@ Line 50: / Line 53: @@
   }
-दूसरे स्तिथि  में, अनेक सभी तत्वों को प्राथमिकता क्रमबद्ध सूची (ओ (एन) प्रविष्टि सॉर्ट समय) में रख सकता है, जब भी उच्चतम प्राथमिकता वाले तत्व का अनुरोध किया जाता है, तो सूची में पहला वापस किया जा सकता है। (O(1) पुल टाइम )
+दूसरे स्तिथि  में, अनेक सभी अवयव ों को प्राथमिकता क्रमबद्ध सूची (ओ (एन) प्रविष्टि सॉर्ट समय) में रख सकता है, जब भी उच्चतम प्राथमिकता वाले अवयव  का अनुरोध किया जाता है, तो सूची में पहला वापस किया जा सकता है। (O(1) पुल टाइम )
   'सम्मिलित करें' (नोड)
   {
-   सूची में foreach (सूचकांक, तत्व)।
+   सूची में foreach (सूचकांक, अवयव )।
    {
-   यदि नोड.प्राथमिकता <तत्व.प्राथमिकता
+   यदि नोड.प्राथमिकता <अवयव .प्राथमिकता
    {
    list.insert_at_index(नोड,सूचकांक)
@@ Line 72: / Line 75: @@
 === सामान्य कार्यान्वयन ===
-इस प्रकार से प्रदर्शन में सुधार करने के लिए, प्राथमिकता कतारें सामान्यतः हीप (डेटा संरचना) पर आधारित होती हैं, जो सम्मिलन और निष्कासन के लिए ओ (लॉग एन) प्रदर्शन देती हैं, और प्रारंभ  में एन तत्वों के सेट से हीप (डेटा संरचना) बनाने के लिए ओ (एन) देती हैं। मूलभूत  हीप डेटा संरचना के वेरिएंट जैसे [[ युग्मन ढेर |पेयरिंग हीप्स]] या फाइबोनैचि हीप्स कुछ ऑपरेशनों के लिए उत्तम  सीमाएं प्रदान कर सकते हैं।<ref name="CLRS_priority_queue_pp476">{{Introduction to Algorithms|edition=2|chapter=Chapter 20: Fibonacci Heaps|pages=476–497}} तृतीय संस्करण, पृ. 518.</ref>
+इस प्रकार से प्रदर्शन में सुधार करने के लिए, प्राथमिकता कतारें सामान्यतः हीप (डेटा संरचना) पर आधारित होती हैं, जो सम्मिलन और निष्कासन के लिए ओ (लॉग एन) प्रदर्शन देती हैं, और प्रारंभ  में एन अवयव ों के सेट से हीप (डेटा संरचना) बनाने के लिए ओ (एन) देती हैं। मूलभूत  हीप डेटा संरचना के वेरिएंट जैसे [[ युग्मन ढेर |पेयरिंग हीप्स]] या फाइबोनैचि हीप्स कुछ ऑपरेशनों के लिए उत्तम  सीमाएं प्रदान कर सकते हैं।<ref name="CLRS_priority_queue_pp476">{{Introduction to Algorithms|edition=2|chapter=Chapter 20: Fibonacci Heaps|pages=476–497}} तृतीय संस्करण, पृ. 518.</ref>
-किन्तु वैकल्पिक रूप से, जब  [[ स्व-संतुलन द्विआधारी खोज वृक्ष |सेल्फ-बैलेंसिंग बाइनरी सर्च ट्री]] का उपयोग किया जाता है, तब यह सम्मिलन और निष्कासन में भी O(लॉग एन) समय लगता है, चूंकि  तत्वों के उपस्तिथ  अनुक्रम से ट्री   बनाने में ओ(एन लॉग एन) समय लगता है; यह विशिष्ट है जहां किसी के पास पहले से ही इन डेटा संरचनाओं तक पहुंच हो सकती है, जैसे कि तृतीय-पक्ष या मानक पुस्तकालयों के साथ। अंतरिक्ष-जटिलता के दृष्टिकोण से, लिंक की गई सूची के साथ स्व-संतुलन बाइनरी सर्च ट्री का उपयोग करने से अधिक भंडारण की आवश्यकता होती है, क्योंकि इसके लिए अन्य नोड्स के अतिरिक्त संदर्भों को संग्रहीत करने की आवश्यकता होती है।
+किन्तु वैकल्पिक रूप से, जब  [[ स्व-संतुलन द्विआधारी खोज वृक्ष |सेल्फ-बैलेंसिंग बाइनरी सर्च ट्री]] का उपयोग किया जाता है, तब यह सम्मिलन और निष्कासन में भी O(लॉग एन) समय लगता है, चूंकि  अवयव ों के उपस्तिथ  अनुक्रम से ट्री   बनाने में ओ(एन लॉग एन) समय लगता है; यह विशिष्ट है जहां किसी के पास पहले से ही इन डेटा संरचनाओं तक पहुंच हो सकती है, जैसे कि तृतीय-पक्ष या मानक पुस्तकालयों के साथ। अंतरिक्ष-जटिलता के दृष्टिकोण से, लिंक की गई सूची के साथ स्व-संतुलन बाइनरी सर्च ट्री का उपयोग करने से अधिक भंडारण की आवश्यकता होती है, क्योंकि इसके लिए अन्य नोड्स के अतिरिक्त संदर्भों को संग्रहीत करने की आवश्यकता होती है।
 कम्प्यूटेशनल-जटिलता के दृष्टिकोण से, प्राथमिकता कतारें सॉर्टिंग एल्गोरिदम के अनुरूप हैं। नीचे प्राथमिकता कतारों और सॉर्टिंग एल्गोरिदम की #समानता पर अनुभाग बताता है कि कैसे कुशल सॉर्टिंग एल्गोरिदम कुशल प्राथमिकता कतारें बना सकते हैं।
@@ Line 84: / Line 87: @@
 * [[वैन एम्डे बोस कदम]] ओ (लॉग लॉग सी) समय में न्यूनतम, अधिकतम, सम्मिलित करें, हटाएं, खोज, निकालने-मिनट, निकालने-अधिकतम, पूर्ववर्ती और उत्तराधिकारी] संचालन का समर्थन करता है, किन्तु  इसमें लगभग लघु  कतारों के लिए स्थान निवेस  होती है ओ(2<sup>m/2</sup>), जहां m प्राथमिकता मान में बिट्स की संख्या है।<ref>P. van Emde Boas. Preserving order in a forest in less than logarithmic time. In ''Proceedings of the 16th Annual Symposium on Foundations of Computer Science'', pages 75-84. IEEE Computer Society, 1975.</ref> और हैशिंग से स्थान को अधिक  लघु  किया जा सकता है।
 * [[माइकल फ्रेडमैन]] और [[डैन विलार्ड]] का [[संलयन वृक्ष|फ़्यूज़न ट्री]] O(1) समय में न्यूनतम ऑपरेशन और <math>O(\log n / \log \log C)</math> इन्सर्ट और एक्सट्रेक्ट-मिन ऑपरेशन को क्रियान्वित  करता है।  समय। चूंकि  लेखक द्वारा यह कहा गया है कि, हमारे एल्गोरिदम में केवल सैद्धांतिक रुचि है; निष्पादन समय में सम्मिलित  निरंतर कारक व्यावहारिकता को रोकते हैं।<ref>[[Michael Fredman|Michael L. Fredman]] and Dan E. Willard. Surpassing the information theoretic bound with fusion trees. ''Journal of Computer and System Sciences'', 48(3):533-551, 1994</ref>
-इस प्रकार से उन अनुप्रयोगों के लिए जो प्रत्येक एक्सट्रैक्ट-मिन ऑपरेशन के लिए कई पीक (डेटा संरचना ऑपरेशन) ऑपरेशन करते हैं, प्रत्येक प्रविष्टि और निष्कासन के पश्चात सर्वोच्च प्राथमिकता वाले तत्व को कैश करके सभी ट्री और हीप कार्यान्वयन में पीक क्रियाओं के लिए समय जटिलता को O(1) तक कम किया जा सकता है। और सम्मिलन के लिए, यह अधिकतम स्थिर निवेस  जोड़ता है, क्योंकि नए सम्मिलित किये गए तत्व की तुलना केवल पहले कैश किए गए न्यूनतम तत्व से की जाती है। रिमूव करने  के लिए, इसमें अधिक से अधिक  अतिरिक्त झलक निवेस  जोड़ी जाती है, जो सामान्यतः  डीलीट  किये गए निवेस  से सस्ती होती है, इसलिए समग्र समय जटिलता महत्वपूर्ण रूप से प्रभावित नहीं होती है।
+इस प्रकार से उन अनुप्रयोगों के लिए जो प्रत्येक एक्सट्रैक्ट-मिन ऑपरेशन के लिए कई पीक (डेटा संरचना ऑपरेशन) ऑपरेशन करते हैं, प्रत्येक प्रविष्टि और निष्कासन के पश्चात सर्वोच्च प्राथमिकता वाले अवयव  को कैश करके सभी ट्री और हीप कार्यान्वयन में पीक क्रियाओं के लिए समय जटिलता को O(1) तक कम किया जा सकता है। और सम्मिलन के लिए, यह अधिकतम स्थिर निवेस  जोड़ता है, क्योंकि नए सम्मिलित किये गए अवयव  की तुलना केवल पहले कैश किए गए न्यूनतम अवयव  से की जाती है। रिमूव करने  के लिए, इसमें अधिक से अधिक  अतिरिक्त झलक निवेस  जोड़ी जाती है, जो सामान्यतः  डीलीट  किये गए निवेस  से सस्ती होती है, इसलिए समग्र समय जटिलता महत्वपूर्ण रूप से प्रभावित नहीं होती है।
 [[मोनोटोन प्राथमिकता कतार]] विशेष कतारें होती हैं जिन्हें उस स्तिथि  के लिए अनुकूलित किया जाता है जहां कोई भी वस्तु   कभी नहीं इन्सर्ट किया  जाता है जिसकी प्राथमिकता पहले निकाले गए किसी भी वस्तु   की तुलना में कम हो (मिन-हीप के स्तिथि  में)। यह प्रतिबंध प्राथमिकता कतारों के कई व्यावहारिक अनुप्रयोगों द्वारा पूर्ण  किया जाता है।
@@ Line 95: / Line 98: @@
 === सॉर्ट करने के लिए प्राथमिकता कतार का उपयोग करना ===
-इस प्रकार से प्राथमिकता कतारों के [[परिचालन शब्दार्थ]] स्वाभाविक रूप से  सोर्टिंग  विधि का सुझाव देते हैं: अर्थात क्रमबद्ध किए जाने वाले सभी तत्वों को प्राथमिकता कतार में रखे , और क्रमिक रूप से उन्हें रिमूव कर  दें; वे क्रमबद्ध विधि  से सामने आएंगे यह वास्तव में कई [[छँटाई एल्गोरिथ्म|सोर्टिंग  एल्गोरिथ्म]] द्वारा उपयोग की जाने वाली प्रक्रिया है,  इस प्रकार से  प्राथमिकता कतार द्वारा प्रदान की गई अमूर्तता (कंप्यूटर विज्ञान) की लेयर हटा दी जाती है। यह सॉर्टिंग विधि निम्नलिखित सॉर्टिंग एल्गोरिदम के समान  है:
+इस प्रकार से प्राथमिकता कतारों के [[परिचालन शब्दार्थ]] स्वाभाविक रूप से  सोर्टिंग  विधि का सुझाव देते हैं: अर्थात क्रमबद्ध किए जाने वाले सभी अवयव  को प्राथमिकता कतार में रखे , और क्रमिक रूप से उन्हें रिमूव कर  दें; वे क्रमबद्ध विधि  से सामने आएंगे यह वास्तव में कई [[छँटाई एल्गोरिथ्म|सोर्टिंग  एल्गोरिथ्म]] द्वारा उपयोग की जाने वाली प्रक्रिया है,  इस प्रकार से  प्राथमिकता कतार द्वारा प्रदान की गई अमूर्तता (कंप्यूटर विज्ञान) की लेयर हटा दी जाती है। यह सॉर्टिंग विधि निम्नलिखित सॉर्टिंग एल्गोरिदम के समान  है:
 {|class="wikitable sortable"
@@ Line 144: / Line 147: @@
 हम प्राथमिकता कतारों से सॉर्टिंग तक  सामान्य नियतात्मक रैखिक स्थान में कमी प्रस्तुत करते हैं, जिसका अर्थ है कि यदि हम प्रति कुंजी एस (एन) समय में एन कुंजी को सॉर्ट कर सकते हैं, तो ओ (एस (एन)) में हटाने और डालने का समर्थन करने वाली  प्राथमिकता कतार है। निरंतर समय में समय और खोज-मिनट आदि ।
-अर्थात्, यदि कोई सॉर्टिंग एल्गोरिदम है जो प्रति कुंजी O(S) समय में सॉर्ट कर सकता है, जहां S, n और शब्द आकार का कुछ फ़ंक्शन है,<ref>{{cite web |url=http://courses.csail.mit.edu/6.851/spring07/scribe/lec17.pdf |title=संग्रहीत प्रति|access-date=2011-02-10 |url-status=live |archive-url=https://web.archive.org/web/20110720000413/http://courses.csail.mit.edu/6.851/spring07/scribe/lec17.pdf |archive-date=2011-07-20 }}</ref> फिर कोई प्राथमिकता कतार बनाने के लिए दी गई प्रक्रिया का उपयोग कर सकता है जहां सर्वोच्च-प्राथमिकता वाले तत्व को खींचना O(1) समय है, और नए तत्वों को सम्मिलित करना (और तत्वों को हटाना) O(S) समय है। उदाहरण के लिए, यदि किसी के पास ओ(एन लॉग एन) सॉर्ट एल्गोरिदम है, तो वह ओ(1) पुलिंग और ओ(लॉग एन) सम्मिलन के साथ प्राथमिकता कतार बना सकता है।
+अर्थात्, यदि कोई सॉर्टिंग एल्गोरिदम है जो प्रति कुंजी ओ(एस) समय में सॉर्ट कर सकता है, जहां ''S'', ''n'' और शब्द आकार का कुछ फ़ंक्शन है,<ref>{{cite web |url=http://courses.csail.mit.edu/6.851/spring07/scribe/lec17.pdf |title=संग्रहीत प्रति|access-date=2011-02-10 |url-status=live |archive-url=https://web.archive.org/web/20110720000413/http://courses.csail.mit.edu/6.851/spring07/scribe/lec17.pdf |archive-date=2011-07-20 }}</ref> यदि  कोई प्राथमिकता कतार बनाने के लिए दी गई प्रक्रिया का उपयोग कर सकता है जहां सर्वोच्च-प्राथमिकता वाले अवयव  को खींचना ओ(1) समय है, और नए अवयव  को सम्मिलित करना (और अवयव ों को हटाना) ओ(एस) समय है। उदाहरण के लिए, यदि किसी के पास ओ(एन लॉग एन) सॉर्ट एल्गोरिदम है, तो वह ओ(1) पुलिंग और ओ(लॉग एन) सम्मिलन के साथ प्राथमिकता कतार बना सकता है।
 == पुस्तकालय ==
@@ Line 150: / Line 153: @@
 प्राथमिकता कतार को प्रायः   [[कंटेनर (सार डेटा प्रकार)|कंटेनर (सार डेटा संरचना)]] माना जाता है।
-[[मानक टेम्पलेट लाइब्रेरी]] (STL), और [[C++]] 1998 मानक, [https://en.cppreference.com/w/cpp/container/priority_queue std::priority_queue] को STL [[कंटेनर (प्रोग्रामिंग)]] [[एडाप्टर (प्रोग्रामिंग)]] में से  के रूप में निर्दिष्ट करता है ) [[टेम्पलेट (प्रोग्रामिंग)]]एस। चूंकि , यह निर्दिष्ट नहीं करता है कि समान प्राथमिकता वाले दो तत्वों को कैसे परोसा जाना चाहिए, और वास्तव में, सामान्य कार्यान्वयन उन्हें कतार में उनके क्रम के अनुसार वापस नहीं करेगा। यह  अधिकतम-प्राथमिकता-कतार क्रियान्वित  करता है, और इसमें तीन पैरामीटर होते हैं: सॉर्टिंग के लिए  तुलनात्मक ऑब्जेक्ट जैसे कि फ़ंक्शन ऑब्जेक्ट (यदि अनिर्दिष्ट है तो कम<T> पर डिफ़ॉल्ट), डेटा संरचनाओं को संग्रहीत करने के लिए अंतर्निहित कंटेनर (std::vector पर डिफ़ॉल्ट) <T>), और अनुक्रम के आरंभ और अंत में दो पुनरावर्तक। वास्तविक एसटीएल कंटेनरों के विपरीत, यह [[इटरेटर]] को इसके तत्वों की अनुमति नहीं देता है (यह सख्ती से इसकी अमूर्त डेटा संरचना परिभाषा का पालन करता है)। एसटीएल में बाइनरी मैक्स-हीप के रूप में  अन्य रैंडम-एक्सेस कंटेनर में हेरफेर करने के लिए उपयोगिता कार्य भी हैं। बूस्ट (C++ लाइब्रेरीज़) का लाइब्रेरी हीप में कार्यान्वयन भी है।
+[[मानक टेम्पलेट लाइब्रेरी]] (एसटीएल), और [[C++|सी ++]] 1998 मानक, [https://en.cppreference.com/w/cpp/container/priority_queue std::priority_queue] को एसटीएल [[कंटेनर (प्रोग्रामिंग)]] [[एडाप्टर (प्रोग्रामिंग)]] में से  के रूप में निर्दिष्ट करता है ) [[टेम्पलेट (प्रोग्रामिंग)]]एस। चूंकि , यह निर्दिष्ट नहीं करता है कि समान प्राथमिकता वाले दो अवयव ों को कैसे सेवित करना  चाहिए, और वास्तव में, सामान्य कार्यान्वयन उन्हें कतार में उनके क्रम के अनुसार वापस नहीं करता है । यह  अधिकतम-प्राथमिकता-कतार क्रियान्वित  करता है, और इसमें तीन पैरामीटर होते हैं: सॉर्टिंग के लिए  तुलनात्मक ऑब्जेक्ट जैसे कि फ़ंक्शन ऑब्जेक्ट (यदि अनिर्दिष्ट है तो लघु <T> पर डिफ़ॉल्ट), डेटा संरचनाओं को संग्रहीत करने के लिए अंतर्निहित कंटेनर (एसटीडी::वेक्टर पर डिफ़ॉल्ट) <T>), और अनुक्रम के आरंभ और अंत में दो पुनरावर्तक सम्मिलित  है । वास्तविक एसटीएल कंटेनरों के विपरीत, यह [[इटरेटर]] को इसके अवयव  की अनुमति नहीं देता है (यह जटिलता  से इसकी अमूर्त डेटा संरचना परिभाषा का पालन करता है)। एसटीएल में बाइनरी मैक्स-हीप के रूप में  अन्य रैंडम-एक्सेस कंटेनर में हेरफेर करने के लिए उपयोगिता कार्य भी हैं। बूस्ट (C++ लाइब्रेरीज़) का लाइब्रेरी हीप में भी कार्यान्वयन  होता है।
 पायथन का [https://docs.python.org/library/heapq.html heapq] मॉड्यूल  सूची के शीर्ष पर  बाइनरी मिन-हीप क्रियान्वित  करता है।
@@ Line 156: / Line 159: @@
 [[जावा (प्रोग्रामिंग भाषा)]] की लाइब्रेरी में  सम्मिलित  है {{Javadoc:SE|java/util|PriorityQueue}} वर्ग, जो न्यूनतम-प्राथमिकता-कतार क्रियान्वित  करता है।
-.NET की लाइब्रेरी में  [https://docs.microsoft.com/en-us/dotnet/api/system.collections.generic.priorityqueue-2?view=net-6.0 प्राथमिकता क्यू] वर्ग सम्मिलित  है, जो  सरणी-समर्थित को क्रियान्वित  करता है, चतुर्धातुक न्यूनतम-ढेर।
+.नेट  की लाइब्रेरी में  [https://docs.microsoft.com/en-us/dotnet/api/system.collections.generic.priorityqueue-2?view=net-6.0 प्राथमिकता क्यू] वर्ग, जो एक सरणी-समर्थित, चतुर्धातुक मिन-हीप क्रियान्वित  करता है
 [[स्काला (प्रोग्रामिंग भाषा)]] की लाइब्रेरी में  [https://www.scala-lang.org/api/current/scala/collection/mutable/PriorityQueue.html प्राथमिकता क्यू] वर्ग सम्मिलित  है, जो अधिकतम-प्राथमिकता-क्यू क्रियान्वित  करता है।
@@ Line 162: / Line 165: @@
 गो (प्रोग्रामिंग भाषा) की लाइब्रेरी में  [http://golang.org/pkg/container/heap/container/heap] मॉड्यूल होता है, जो किसी भी संगत डेटा संरचना के शीर्ष पर  मिन-हीप क्रियान्वित  करता है।
-[[मानक PHP लाइब्रेरी]] एक्सटेंशन में क्लास [http://us2.php.net/manual/en/class.splpriorityqueue.php SplPriorityQueue] सम्मिलित  है।
+[[मानक PHP लाइब्रेरी|मानक पीएचपी  लाइब्रेरी]] एक्सटेंशन में क्लास [http://us2.php.net/manual/en/class.splpriorityqueue.php SplPriorityQueue] सम्मिलित  है।
-Apple के [[कोर फाउंडेशन]] फ्रेमवर्क में  [https://developer.apple.com/library/mac/#documentation/CoreFoundation/Reference/CFBinaryHeapRef/Reference/reference.html CFBinaryHeap] संरचना सम्मिलित  है, जो  मिन-हीप क्रियान्वित  करती है।
+एप्पल के [[कोर फाउंडेशन]] फ्रेमवर्क में  [https://developer.apple.com/library/mac/#documentation/CoreFoundation/Reference/CFBinaryHeapRef/Reference/reference.html CFBinaryHeap] संरचना सम्मिलित  है, जो  मिन-हीप क्रियान्वित  करती है।
 == अनुप्रयोग ==
@@ Line 170: / Line 173: @@
 === बैंडविड्थ प्रबंधन ===
-[[ संगणक संजाल | संगणक संजाल]] [[राउटर (कंप्यूटिंग)]] से ट्रांसमिशन लाइन पर [[बैंडविड्थ (कंप्यूटिंग)]] जैसे सीमित संसाधनों को प्रबंधित करने के लिए प्राथमिकता कतार का उपयोग किया जा सकता है। अपर्याप्त बैंडविड्थ के कारण आउटगोइंग [[ट्रैफ़िक]] कतार में लगने की स्थिति में, आगमन पर ट्रैफ़िक को सर्वोच्च प्राथमिकता वाली कतार से भेजने के लिए अन्य सभी कतारों को रोका जा सकता है। यह सुनिश्चित करता है कि प्राथमिकता वाले ट्रैफ़िक (जैसे कि वास्तविक समय ट्रैफ़िक, उदाहरण के लिए [[ इंटरनेट प्रोटोकॉल पर आवाज़ |इंटरनेट प्रोटोकॉल पर आवाज़]] कनेक्शन की [[वास्तविक समय परिवहन प्रोटोकॉल]] स्ट्रीम) को कम से कम देरी के साथ अग्रेषित किया जाता है और कतार के अधिकतम तक पहुंचने के कारण अस्वीकार होने की कम से कम संभावना होती है। क्षमता। सर्वोच्च प्राथमिकता कतार खाली होने पर अन्य सभी ट्रैफ़िक को संभाला जा सकता है। उपयोग किया जाने वाला  अन्य तरीका उच्च प्राथमिकता वाली कतारों से असंगत रूप से अधिक ट्रैफ़िक भेजना है।
+[[ संगणक संजाल | '''संगणक संजाल''']] '''[[राउटर (कंप्यूटिंग)]]''' से ट्रांसमिशन लाइन पर [[बैंडविड्थ (कंप्यूटिंग)]] जैसे सीमित संसाधनों को प्रबंधित करने के लिए प्राथमिकता कतार का उपयोग किया जा सकता है। अपर्याप्त बैंडविड्थ के कारण आउटगोइंग [[ट्रैफ़िक]] कतार में लगने की स्थिति में, आगमन पर ट्रैफ़िक को सर्वोच्च प्राथमिकता वाली कतार से भेजने के लिए अन्य सभी कतारों को रोका जा सकता है। यह सुनिश्चित करता है कि प्राथमिकता वाले ट्रैफ़िक (जैसे कि वास्तविक समय ट्रैफ़िक, उदाहरण के लिए [[ इंटरनेट प्रोटोकॉल पर आवाज़ |वीओआईपी]] कनेक्शन की [[वास्तविक समय परिवहन प्रोटोकॉल|आरटीपी]] स्ट्रीम) को लघु से ;लघु देरी के साथ अग्रेषित किया जाता है और कतार के अधिकतम तक पहुंचने के कारण अस्वीकार होने की कम से कम संभावना होती है। इस प्रकार से  सर्वोच्च प्राथमिकता कतार रिक्त  होने पर अन्य सभी ट्रैफ़िक को संभाला जा सकता है। उपयोग किया जाने वाले   अन्य  विधि से   उच्च प्राथमिकता वाली कतारों के असंगत रूप से अधिक ट्रैफ़िक भेजना है।
-स्थानीय क्षेत्र नेटवर्क के लिए कई आधुनिक प्रोटोकॉल में [[ मीडिया अभिगम नियंत्रण |मीडिया अभिगम नियंत्रण]] (मैक) उप-परत पर प्राथमिकता कतारों की अवधारणा भी सम्मिलित  है ताकि यह सुनिश्चित किया जा सके कि उच्च-प्राथमिकता वाले एप्लिकेशन (जैसे [[वीओआईपी]] या [[आईपीटीवी]]) अन्य अनुप्रयोगों की तुलना में कम विलंबता का अनुभव करते हैं जिन्हें इसके साथ परोसा जा सकता है। [[सर्वोत्तम प्रयास वाली सेवा]]. उदाहरणों में IEEE 802.11e (IEEE 802.11 में  संशोधन जो [[सेवा की गुणवत्ता]] प्रदान करता है) और [[ITU-T]] G.hn (उपस्तिथ  होम वायरिंग (पावर लाइन संचार, फोन लाइन और कोएक्स पर ईथरनेट) का उपयोग करके हाई-स्पीड [[लोकल एरिया नेटवर्क]] के लिए  मानक) सम्मिलित  हैं। .
+इस प्रकार से स्थानीय क्षेत्र नेटवर्क के लिए कई आधुनिक प्रोटोकॉल में [[ मीडिया अभिगम नियंत्रण |मीडिया एक्सेस कंट्रोल  ]] (मैक) उप-परत पर प्राथमिकता कतारों की अवधारणा भी सम्मिलित  है जिससे यह सुनिश्चित किया जा सके कि उच्च-प्राथमिकता वाले एप्लिकेशन (जैसे [[वीओआईपी]] या [[आईपीटीवी]]) अन्य अनुप्रयोगों की तुलना में कम विलंबता का अनुभव करते हैं जिन्हें इसके साथ सेवित  जा सकता है। [[सर्वोत्तम प्रयास वाली सेवा|बेस्ट-एफ्फ़ोर्ट सर्विस]] के अतिरिक्त  उदाहरणों में आईईईई 802.11ई  (आईईईई 802.11 में  संशोधन जो  [[सेवा की गुणवत्ता|क्वालिटी ऑफ  सर्विस]] प्रदान करता है) और आईटीयू-टी जी.एच.एन (उपस्तिथ  होम वायरिंग (पावर लाइन संचार, फोन लाइन और कोएक्स पर ईथरनेट) का उपयोग करके हाई-स्पीड [[लोकल एरिया नेटवर्क]] के लिए  मानक) सम्मिलित  हैं। .
-सामान्यतः   सीमा (पोलिसर) उस बैंडविड्थ को सीमित करने के लिए निर्धारित की जाती है जो उच्चतम प्राथमिकता कतार से ट्रैफ़िक ले सकता है, ताकि उच्च प्राथमिकता वाले पैकेटों को अन्य सभी ट्रैफ़िक को रोकने से रोका जा सके। यह सीमासामान्यतः सिस्को सिस्टम्स, इंक. [[ प्रबंधक को कॉल करो |प्रबंधक को कॉल करो]] जैसे उच्च स्तरीय नियंत्रण उदाहरणों के कारण कभी नहीं पहुंचती है, जिसे प्रोग्राम की गई बैंडविड्थ सीमा से अधिक होने वाली कॉल को रोकने के लिए प्रोग्राम किया जा सकता है।
+सामान्यतः   सीमा (पोलिसर) उस बैंडविड्थ को सीमित करने के लिए निर्धारित की जाती है जो उच्चतम प्राथमिकता कतार से ट्रैफ़िक ले सकता है, जिससे उच्च प्राथमिकता वाले पैकेटों को अन्य सभी ट्रैफ़िक को रोकने से रोका जा सकता है । यह सीमासामान्यतः सिस्को सिस्टम्स, इंक. [[ प्रबंधक को कॉल करो |प्रबंधक को कॉल करो]] जैसे उच्च स्तरीय नियंत्रण उदाहरणों के कारण कभी नहीं पहुंचती है, जिसे प्रोग्राम की गई बैंडविड्थ सीमा से अधिक होने वाली कॉल को रोकने के लिए प्रोग्राम किया जा सकता है।
 === [[असतत घटना अनुकरण]] ===
@@ Line 183: / Line 186: @@
 === दिज्क्स्ट्रा का एल्गोरिथ्म ===
-जब ग्राफ़ को आसन्न सूची या मैट्रिक्स के रूप में संग्रहीत किया जाता है, तो दिज्क्स्ट्रा के एल्गोरिदम को कार्यान्वित करते समय न्यूनतम कुशलता से निकालने के लिए प्राथमिकता कतार का उपयोग किया जा सकता है, चूंकि  किसी को प्राथमिकता कतार में किसी विशेष शीर्ष की प्राथमिकता को कुशलतापूर्वक बदलने की क्षमता की भी आवश्यकता होती है।
+जब ग्राफ़ को आसन्न सूची या मैट्रिक्स के रूप में संग्रहीत किया जाता है, तो दिज्क्स्ट्रा के एल्गोरिदम को कार्यान्वित करते समय न्यूनतम कुशलता से निकालने के लिए प्राथमिकता कतार का उपयोग किया जा सकता है, चूंकि  किसी को प्राथमिकता कतार में किसी विशेष शीर्ष की प्राथमिकता को कुशलतापूर्वक परिवर्तन  की क्षमता की आवश्यकता होती है।
-यदि इसके बजाय,  ग्राफ़ को नोड ऑब्जेक्ट के रूप में संग्रहीत किया जाता है, और प्राथमिकता-नोड जोड़े को ढेर में डाला जाता है, तो किसी विशेष शीर्ष की प्राथमिकता को बदलना आवश्यक नहीं है यदि कोई विज़िट किए गए नोड्स को ट्रैक करता है।  बार  नोड पर जाने के बाद, यदि यह दोबारा ढेर में आता है (पहले इसके साथ कम प्राथमिकता संख्या जुड़ी हुई थी), तो इसे पॉप-ऑफ कर दिया जाता है और अनदेखा कर दिया जाता है।
+यदि इसके अतरिक्त , ग्राफ़ को नोड ऑब्जेक्ट के रूप में संग्रहीत किया जाता है, और प्राथमिकता-नोड जोड़े को हीप में डाला जाता है, तो किसी विशेष शीर्ष की प्राथमिकता को परिवर्तित करना  आवश्यक नहीं है यदि कोई विज़िट किए गए नोड्स को ट्रैक करता है। तत्पश्चात  बार नोड पर जाने के अतिरिक्त , यदि यह दोबारा हीप में आता है (पहले इसके साथ कम प्राथमिकता संख्या जुड़ी हुई थी), तो इसे पॉप-ऑफ कर दिया जाता है और अनदेखा कर दिया जाता है।
 === [[हफ़मैन कोडिंग]] ===
-हफ़मैन कोडिंग के लिए व्यक्ति को दो सबसे कम आवृत्ति वाले ट्री  ों को बार-बार प्राप्त करने की आवश्यकता होती है।  प्राथमिकता कतार हफ़मैन कोडिंग#संपीड़न है।
+इस प्रकार से हफ़मैन कोडिंग के लिए व्यक्ति को दो सामान्य  लघु  आवृत्ति वाले ट्री  को बार-बार प्राप्त करने की आवश्यकता होती है।  प्राथमिकता कतार हफ़मैन कोडिंग की विधि  है।
 === [[सर्वोत्तम-प्रथम खोज]] एल्गोरिदम ===
-सर्वश्रेष्ठ-प्रथम खोज एल्गोरिदम, ए * खोज एल्गोरिदम की तरह,  [[भारित ग्राफ]]़ के दो वर्टेक्स (ग्राफ़ सिद्धांत) या [[नोड (ग्राफ़ सिद्धांत)]] के बीच सबसे छोटा रास्ता ढूंढते हैं, सबसे आशाजनक मार्गों को पहले आज़माते हैं। अज्ञात मार्गों पर नज़र रखने के लिए प्राथमिकता कतार (जिसे फ्रिंज भी कहा जाता है) का उपयोग किया जाता है; जिसके लिए कुल पथ लंबाई का अनुमान (ए* के स्तिथि  में निचली सीमा) सबसे छोटा है, उसे सर्वोच्च प्राथमिकता दी जाती है। यदि मेमोरी सीमाएं सर्वोत्तम-प्रथम खोज को अव्यवहारिक बनाती हैं, तो कम-प्राथमिकता वाली वस्तुओं को हटाने की अनुमति देने के लिए [[डबल-एंडेड प्राथमिकता कतार]] के साथ [[एसएमए*]] एल्गोरिदम जैसे वेरिएंट का उपयोग किया जा सकता है।
+सर्वश्रेष्ठ-प्रथम खोज एल्गोरिदम, ए * खोज एल्गोरिदम की तरह,  [[भारित ग्राफ]] के दो वर्टेक्स (ग्राफ़ सिद्धांत) या [[नोड (ग्राफ़ सिद्धांत)]] के मध्य  अधिक  लघु  रास्ता ढूंढते हैं, इस प्रकार से  आशाजनक मार्गों को पहले जांचते  हैं। अज्ञात मार्गों पर द्रष्टि  रखने के लिए प्राथमिकता कतार (जिसे फ्रिंज भी कहा जाता है) का उपयोग किया जाता है; जिसके लिए कुल पथ लंबाई का अनुमान (ए* के स्तिथि  में निचली सीमा) अधिक लघु  है, उसे सर्वोच्च प्राथमिकता दी जाती है। यदि मेमोरी सीमाएं सर्वोत्तम-प्रथम खोज को अव्यवहारिक बनाती हैं, तो कम-प्राथमिकता वाली वस्तुओं को हटाने की अनुमति देने के लिए [[डबल-एंडेड प्राथमिकता कतार]] के साथ [[एसएमए*]] एल्गोरिदम जैसे वेरिएंट का उपयोग किया जा सकता है।
-=== [[ROAM]] त्रिकोणासन एल्गोरिथ्म ===
+=== [[ROAM|आरओएम]] त्रिकोणासन एल्गोरिथ्म ===
-रीयल-टाइम ऑप्टिमली एडाप्टिंग मेश (आरओएएम) एल्गोरिदम किसी इलाके के गतिशील रूप से बदलते त्रिकोण की गणना करता है। यह त्रिकोणों को विभाजित करके काम करता है जहां अधिक विवरण की आवश्यकता होती है और जहां कम विवरण की आवश्यकता होती है वहां उन्हें विलय कर देता है। एल्गोरिथ्म इलाके में प्रत्येक त्रिकोण को प्राथमिकता देता है,सामान्यतः उस त्रिकोण को विभाजित करने पर त्रुटि में कमी से संबंधित होता है। एल्गोरिथ्म दो प्राथमिकता कतारों का उपयोग करता है,  उन त्रिकोणों के लिए जिन्हें विभाजित किया जा सकता है और दूसरा उन त्रिकोणों के लिए जिन्हें विलय किया जा सकता है। प्रत्येक चरण में उच्चतम प्राथमिकता वाले विभाजित कतार से त्रिकोण को विभाजित किया जाता है, या सबसे कम प्राथमिकता वाले मर्ज कतार से त्रिकोण को उसके पड़ोसियों के साथ विलय कर दिया जाता है।
+इस प्रकार से रीयल-टाइम ऑप्टिमली एडाप्टिंग मेश (आरओएएम) एल्गोरिदम किसी स्तिथि के गतिशील रूप से परिवर्तित  त्रिकोण की गणना करता है। यह त्रिकोणों को विभाजित करके कार्य  करता है जहां अधिक विवरण की आवश्यकता होती है और जहां लघु विवरण की आवश्यकता होती है वहां उन्हें विलय कर देता है। एल्गोरिथ्म स्तिथि में प्रत्येक त्रिकोण को प्राथमिकता देता है,सामान्यतः उस त्रिकोण को विभाजित करने पर त्रुटि में कमी से संबंधित होता है। एल्गोरिथ्म दो प्राथमिकता कतारों का उपयोग करता है,  उन त्रिकोणों के लिए जिन्हें विभाजित किया जा सकता है और दूसरा उन त्रिकोणों के लिए जिन्हें विलय किया जा सकता है। प्रत्येक चरण में उच्चतम प्राथमिकता वाले विभाजित कतार से त्रिकोण को विभाजित किया जाता है, या अधिक लघु  प्राथमिकता वाले मर्ज कतार से त्रिकोण को उसके निकटतम  के साथ विलय कर दिया जाता है।
 === न्यूनतम फैले हुए ट्री   के लिए प्राइम का एल्गोरिदम ===
-[[ जुड़ा हुआ ग्राफ ]]़ और [[अप्रत्यक्ष ग्राफ]]़ के [[न्यूनतम फैलाव वाला पेड़|न्यूनतम फैलाव वाला ट्री]]   को खोजने के लिए प्राइम के एल्गोरिदम में [[ बाइनरी ढेर |बाइनरी ढेर]] का उपयोग करके, कोई अच्छा रनिंग टाइम प्राप्त कर सकता है। यह न्यूनतम हीप प्राथमिकता कतार न्यूनतम हीप डेटा संरचना का उपयोग करती है जो सम्मिलित, न्यूनतम, अर्क-मिनट, कमी-कुंजी जैसे संचालन का समर्थन करती है।<ref name="CLR">{{Introduction to Algorithms |edition=3 |pages=634}} "In order to implement Prim's algorithm efficiently, we need a fast way to select a new edge to add to the tree formed by the edges in A."</ref> इस कार्यान्वयन में, वर्टेक्स (ग्राफ़ सिद्धांत) की प्राथमिकता तय करने के लिए किनारों के भारित ग्राफ़ का उपयोग किया जाता है। वजन जितना कम होगा, प्राथमिकता उतनी अधिक होगी और वजन जितना अधिक होगा, प्राथमिकता कम होगी।<ref name="GEEKS">
+[[ जुड़ा हुआ ग्राफ ]] और [[अप्रत्यक्ष ग्राफ]] के [[न्यूनतम फैलाव वाला पेड़|न्यूनतम फैलाव वाला ट्री]]   को खोजने के लिए प्राइम के एल्गोरिदम में [[ बाइनरी ढेर |बाइनरी]] हीप का उपयोग करके, कोई सही  रनिंग टाइम प्राप्त कर सकता है। यह न्यूनतम हीप प्राथमिकता कतार न्यूनतम हीप डेटा संरचना का उपयोग करती है जो सम्मिलित, न्यूनतम, अर्क-मिनट, कमी-कुंजी जैसे संचालन का समर्थन करती है।<ref name="CLR">{{Introduction to Algorithms |edition=3 |pages=634}} "In order to implement Prim's algorithm efficiently, we need a fast way to select a new edge to add to the tree formed by the edges in A."</ref> इस कार्यान्वयन में, वर्टेक्स (ग्राफ़ सिद्धांत) की प्राथमिकता तय करने के लिए किनारों के भारित ग्राफ़ का उपयोग किया जाता है। वजन जितना कम होगा, प्राथमिकता उतनी अधिक होगी और वजन जितना अधिक होगा, प्राथमिकता लघु  होगी।<ref name="GEEKS">
 {{cite web
   |url         = http://www.geeksforgeeks.org/greedy-algorithms-set-5-prims-minimum-spanning-tree-mst-2/
@@ Line 212: / Line 215: @@
 </ref>
 ==समानांतर प्राथमिकता कतार ==
-प्राथमिकता कतारों को तेज़ करने के लिए समानांतरीकरण का उपयोग किया जा सकता है, किन्तु  प्राथमिकता कतार इंटरफ़ेस में कुछ बदलाव की आवश्यकता होती है। ऐसे परिवर्तनों का कारण यह है किसामान्यतः क्रमिक अद्यतन ही होता है <math display="inline">O(1)</math> या <math display="inline">O(\log n)</math> निवेस , और ऐसे ऑपरेशन को समानांतर करने का कोई व्यावहारिक लाभ नहीं है।  संभावित परिवर्तन  ही प्राथमिकता कतार में एकाधिक प्रोसेसर की समवर्ती पहुंच की अनुमति देना है। दूसरा संभावित परिवर्तन बैच संचालन की अनुमति देना है जो काम करता है <math display="inline">k</math> केवल  तत्व के बजाय तत्व। उदाहरण के लिए, एक्सट्रैक्टमिन पहले को हटा देगा <math display="inline">k</math> सर्वोच्च प्राथमिकता वाले तत्व।
+प्राथमिकता कतारों को तीव्र  करने के लिए समानांतरीकरण का उपयोग किया जा सकता है, किन्तु  प्राथमिकता कतार इंटरफ़ेस में कुछ परिवर्तन  की आवश्यकता होती है। ऐसे परिवर्तनों का कारण यह है किसामान्यतः क्रमिक अद्यतन ही होता है <math display="inline">O(1)</math> या <math display="inline">O(\log n)</math> निवेस , और ऐसे ऑपरेशन को समानांतर करने का कोई व्यावहारिक निवेस नहीं है।  संभावित परिवर्तन  ही प्राथमिकता कतार में एकाधिक प्रोसेसर की समवर्ती पहुंच की अनुमति देना है। दूसरा संभावित परिवर्तन बैच संचालन की अनुमति देना है जो कार्य करता है  केवल  अवयव <math display="inline">k</math> के अतरिक्त  इस प्रकार से   उदाहरण के लिए, एक्सट्रैक्टमिन  पहले  को हटा देगा <math display="inline">k</math> सर्वोच्च प्राथमिकता वाले अवयव है ।
 === समवर्ती समानांतर पहुंच ===
-यदि प्राथमिकता कतार समवर्ती पहुंच की अनुमति देती है, तो कई प्रक्रियाएं उस प्राथमिकता कतार पर समवर्ती रूप से संचालन कर सकती हैं। चूंकि , इससे दो मुद्दे उठते हैं। सबसे पहले, व्यक्तिगत संचालन के शब्दार्थ की परिभाषा अब स्पष्ट नहीं है। उदाहरण के लिए, यदि दो प्रक्रियाएं सर्वोच्च प्राथमिकता वाले तत्व को निकालना चाहती हैं, तो क्या उन्हें  ही तत्व मिलना चाहिए या अलग-अलग? यह प्राथमिकता कतार का उपयोग करके प्रोग्राम के स्तर पर समानता को प्रतिबंधित करता है। इसके अतिरिक्त , क्योंकि कई प्रक्रियाओं की  ही तत्व तक पहुंच होती है, इससे विवाद होता है।
+यदि प्राथमिकता कतार समवर्ती पहुंच की अनुमति देती है, तो कई प्रक्रियाएं उस प्राथमिकता कतार पर समवर्ती रूप से संचालन कर सकती हैं। चूंकि , इससे दो मुद्दे उठते हैं। सर्वप्रथम , व्यक्तिगत संचालन के शब्दार्थ की परिभाषा अब स्पष्ट नहीं है। उदाहरण के लिए, यदि दो प्रक्रियाएं सर्वोच्च प्राथमिकता वाले अवयव  को निकालना चाहती हैं, तो क्या उन्हें  ही अवयव  मिलना चाहिए या अलग-अलग? यह प्राथमिकता कतार का उपयोग करके प्रोग्राम के स्तर पर समानता को प्रतिबंधित करता है। इसके अतिरिक्त , क्योंकि कई प्रक्रियाओं की  ही अवयव  तक पहुंच होती है, इससे विवाद होता है।
-[[File:concurrent_prio_queue_conflict.svg|thumb|नोड 3 डाला जाता है और नोड 2 के पॉइंटर को नोड 3 पर सेट करता है। उसके तुरंत बाद, नोड 2 हटा दिया जाता है और नोड 1 का पॉइंटर नोड 4 पर सेट कर दिया जाता है। अब नोड 3 अब पहुंच योग्य नहीं है।]]प्राथमिकता कतार तक समवर्ती पहुंच को समवर्ती पढ़ें, समवर्ती लिखें (सीआरसीडब्ल्यू) PRAM मॉडल पर क्रियान्वित  किया जा सकता है। निम्नलिखित में प्राथमिकता कतार को  स्किप सूची के रूप में क्रियान्वित  किया गया है।<ref name = skiplist>{{cite journal |last1= Sundell |first1=Håkan |last2= Tsigas |first2= Philippas |date=2005 |title=मल्टी-थ्रेड सिस्टम के लिए तेज़ और लॉक-मुक्त समवर्ती प्राथमिकता कतारें|url= https://doi.org/10.1016/j.jpdc.2004.12.005 |journal= Journal of Parallel and Distributed Computing |volume= 65 |issue= 5 |pages= 609–627 |doi= 10.1109/IPDPS.2003.1213189|s2cid=20995116 }}</ref><ref>{{citation|surname1=Lindén, Jonsson|periodical=Technical Report 2018-003|title=A Skiplist-Based Concurrent Priority Queue with Minimal Memory Contention|date=2013|language=de|url=http://www.it.uu.se/research/publications/reports/2018-003/
+[[File:concurrent_prio_queue_conflict.svg|thumb|नोड 3 डाला जाता है और नोड 2 के पॉइंटर को नोड 3 पर सेट करता है। उसके तुरंत बाद, नोड 2 हटा दिया जाता है और नोड 1 का पॉइंटर नोड 4 पर सेट कर दिया जाता है। अब नोड 3 अब पहुंच योग्य नहीं है।]]प्राथमिकता कतार तक समवर्ती पहुंच को समवर्ती पढ़ें, समवर्ती लिखें (सीआरसीडब्ल्यू) पीआरएएम  मॉडल पर क्रियान्वित  किया जा सकता है। निम्नलिखित में प्राथमिकता कतार को  स्किप सूची के रूप में क्रियान्वित  किया गया है।<ref name = skiplist>{{cite journal |last1= Sundell |first1=Håkan |last2= Tsigas |first2= Philippas |date=2005 |title=मल्टी-थ्रेड सिस्टम के लिए तेज़ और लॉक-मुक्त समवर्ती प्राथमिकता कतारें|url= https://doi.org/10.1016/j.jpdc.2004.12.005 |journal= Journal of Parallel and Distributed Computing |volume= 65 |issue= 5 |pages= 609–627 |doi= 10.1109/IPDPS.2003.1213189|s2cid=20995116 }}</ref><ref>{{citation|surname1=Lindén, Jonsson|periodical=Technical Report 2018-003|title=A Skiplist-Based Concurrent Priority Queue with Minimal Memory Contention|date=2013|language=de|url=http://www.it.uu.se/research/publications/reports/2018-003/
-}}</ref> इसके अतिरिक्त ,  परमाणु तुल्यकालन आदिम, तुलना-और-स्वैप, का उपयोग स्किप सूची को [[लॉक (कंप्यूटर विज्ञान)]]-मुक्त बनाने के लिए किया जाता है। स्किप सूची के नोड्स में  अद्वितीय कुंजी,  प्राथमिकता, [[पॉइंटर (कंप्यूटर प्रोग्रामिंग)]] की  सरणी डेटा संरचना, प्रत्येक स्तर के लिए, अगले नोड्स और  डिलीट मार्क सम्मिलित  होते हैं। यदि नोड किसी प्रक्रिया द्वारा हटाया जाने वाला है तो डिलीट मार्क चिह्नित करता है। यह सुनिश्चित करता है कि अन्य प्रक्रियाएं विलोपन पर उचित रूप से प्रतिक्रिया कर सकती हैं।
+}}</ref> इसके अतिरिक्त ,  परमाणु तुल्यकालन आदिम, तुलना-और-स्वैप, का उपयोग स्किप सूची को [[लॉक (कंप्यूटर विज्ञान)]]-नि शुल्क  बनाने के लिए किया जाता है। स्किप सूची के नोड्स में  अद्वितीय कुंजी,  प्राथमिकता, [[पॉइंटर (कंप्यूटर प्रोग्रामिंग)]] की  सरणी डेटा संरचना, प्रत्येक स्तर के लिए, अगले नोड्स और  डिलीट मार्क सम्मिलित  होते हैं। यदि नोड किसी प्रक्रिया द्वारा हटाया जाने वाला है तो डिलीट मार्क चिह्नित करता है। यह सुनिश्चित करता है कि अन्य प्रक्रियाएं विलोपन पर उचित रूप से प्रतिक्रिया कर सकती हैं।
-*इन्सर्ट(ई): सबसे पहले,  कुंजी और प्राथमिकता वाला  नया नोड बनाया जाता है। इसके अतिरिक्त , नोड को कई स्तर दिए गए हैं, जो पॉइंटर्स की सरणी के आकार को निर्धारित करते हैं। फिर नए नोड को सम्मिलित करने की सही स्थिति खोजने के लिए  खोज की जाती है। खोज पहले नोड से और उच्चतम स्तर से शुरू होती है। फिर स्किप सूची को निम्नतम स्तर तक ले जाया जाता है जब तक कि सही स्थिति नहीं मिल जाती। खोज के दौरान, प्रत्येक स्तर के लिए अंतिम ट्रैवर्स किए गए नोड को उस स्तर पर नए नोड के लिए मूल नोड के रूप में सहेजा जाएगा। इसके अतिरिक्त , मूल नोड का सूचक जिस नोड की ओर इशारा करता है, उस स्तर पर नए नोड के उत्तराधिकारी नोड के रूप में सहेजा जाएगा। बाद में, नए नोड के प्रत्येक स्तर के लिए, मूल नोड के पॉइंटर्स को नए नोड पर सेट किया जाएगा। अंत में, नए नोड के प्रत्येक स्तर के लिए पॉइंटर्स को संबंधित उत्तराधिकारी नोड्स पर सेट किया जाएगा।
+*इन्सर्ट(ई): सर्व प्रथम ,  कुंजी और प्राथमिकता वाला  नया नोड बनाया जाता है। इसके अतिरिक्त , नोड को कई स्तर दिए गए हैं, जो पॉइंटर्स की सरणी के आकार को निर्धारित करते हैं। फिर नए नोड को सम्मिलित करने की सही स्थिति खोजने के लिए  खोज की जाती है। इस प्रकार से  खोज पहले नोड से और उच्चतम स्तर से प्रारंभ होती है। इसके पश्चात स्किप सूची को निम्नतम स्तर तक ले जाया जाता है जब तक कि सही स्थिति नहीं मिल जाती। खोज के समय , प्रत्येक स्तर के लिए अंतिम ट्रैवर्स किए गए नोड को उस स्तर पर नए नोड के लिए मूल नोड के रूप में सहेजा जाएगा। इसके अतिरिक्त , मूल नोड का सूचक जिस नोड की ओर संकेत करता है, उस स्तर पर नए नोड के उत्तराधिकारी नोड के रूप में सहेजा जाएगा। तत्पश्चात , नए नोड के प्रत्येक स्तर के लिए, मूल नोड के पॉइंटर्स को नए नोड पर सेट किया जाएगा। अंत में, नए नोड के प्रत्येक स्तर के लिए पॉइंटर्स को संबंधित उत्तराधिकारी नोड्स पर सेट किया जाएगा।
-*एक्स्ट्रेक्ट-मिन: सबसे पहले, स्किप सूची को तब तक ट्रैवर्स किया जाता है जब तक कि  नोड नहीं पहुंच जाता है जिसका डिलीट मार्क सेट नहीं है। यह डिलीट मार्क उस नोड के लिए सत्य पर सेट है। अंत में हटाए गए नोड के मूल नोड्स के पॉइंटर्स अपडेट किए जाते हैं।
+*एक्स्ट्रेक्ट-मिन: सर्व प्रथम, स्किप सूची को तब तक ट्रैवर्स किया जाता है जब तक कि  नोड नहीं पहुंच जाता है जिसका डिलीट मार्क सेट नहीं है। यह डिलीट मार्क उस नोड के लिए सत्य पर सेट है। अंत में हटाए गए नोड के मूल नोड्स के पॉइंटर्स अपडेट किए जाते हैं।
+यदि प्राथमिकता कतार तक समवर्ती पहुंच की अनुमति दी जाती है, तो दो प्रक्रियाओं के बीच टकराव उत्पन्न हो सकता है। उदाहरण के लिए, यदि  प्रक्रिया  नया नोड डालने का प्रयास कर रही है, किन्तु  उसी समय  अन्य प्रक्रिया उस नोड के पूर्ववर्ती को हटाने वाली है तो  विरोध उत्पन्न होता है।<ref name = skiplist/> यह संकटजनक  है कि नया नोड स्किप सूची में जोड़ा गया है, फिर भी यह अब पहुंच योग्य नहीं है. ([[:फ़ाइल:concurrent_prio_queue_conflict.svg|छवि देखें)
-यदि प्राथमिकता कतार तक समवर्ती पहुंच की अनुमति दी जाती है, तो दो प्रक्रियाओं के बीच टकराव उत्पन्न हो सकता है। उदाहरण के लिए, यदि  प्रक्रिया  नया नोड डालने का प्रयास कर रही है, किन्तु  उसी समय  अन्य प्रक्रिया उस नोड के पूर्ववर्ती को हटाने वाली है तो  विरोध उत्पन्न होता है।<ref name = skiplist/> 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|छवि देखें)
+=== के-अवयव  संचालन ===
+इस सेटिंग में, प्राथमिकता कतार पर संचालन को  बैच के लिए सामान्यीकृत किया जाता है <math display="inline">k</math> अवयव .
-=== के-तत्व संचालन ===
+उदाहरण के लिए, k_extract-min हटा देता है <math display="inline">k</math> प्राथमिकता कतार के सबसे छोटे अवयव  और उन्हें लौटाता है।
-इस सेटिंग में, प्राथमिकता कतार पर संचालन को  बैच के लिए सामान्यीकृत किया जाता है <math display="inline">k</math> तत्व.
-उदाहरण के लिए, k_extract-min हटा देता है <math display="inline">k</math> प्राथमिकता कतार के सबसे छोटे तत्व और उन्हें लौटाता है।
-[[समानांतर प्रोग्रामिंग मॉडल]] | साझा-मेमोरी सेटिंग में, समानांतर प्राथमिकता कतार को समानांतर [[बाइनरी खोज पेड़|बाइनरी खोज ट्री]]   और [[जॉइन-आधारित ट्री एल्गोरिदम]] का उपयोग करके आसानी से कार्यान्वित किया जा सकता है। विशेष रूप से, k_extract-min बाइनरी सर्च ट्री पर  विभाजन से मेल खाता है <math display="inline">O(\log n)</math> निवेस  और  ट्री   की पैदावार जिसमें सम्मिलित  है <math display="inline">k</math> सबसे छोटे तत्व. k_insert को मूल प्राथमिकता कतार और सम्मिलन के बैच के संघ द्वारा क्रियान्वित  किया जा सकता है। यदि बैच पहले से ही कुंजी द्वारा क्रमबद्ध है, तो k_insert है <math display="inline">O(k\log (1+\frac{n}{k}))</math> निवेस । अन्यथा, हमें पहले बैच को सॉर्ट करना होगा, इसलिए निवेस  होगी <math display="inline">O(k\log (1+\frac{n}{k})+k\log k)=O(k\log n)</math>. प्राथमिकता कतार के लिए अन्य ऑपरेशन इसी तरह क्रियान्वित  किए जा सकते हैं। उदाहरण के लिए, k_decrease-key को पहले अंतर और फिर यूनियन क्रियान्वित  करके किया जा सकता है, जो पहले तत्वों को हटाता है और फिर उन्हें अद्यतन कुंजी के साथ वापस सम्मिलित करता है। ये सभी ऑपरेशन अत्यधिक समानांतर हैं, और सैद्धांतिक और व्यावहारिक दक्षता संबंधित शोध पत्रों में पाई जा सकती है।<ref name="join-based">{{citation
+[[समानांतर प्रोग्रामिंग मॉडल]] | साझा-मेमोरी सेटिंग में, समानांतर प्राथमिकता कतार को समानांतर [[बाइनरी खोज पेड़|बाइनरी खोज ट्री]]   और [[जॉइन-आधारित ट्री एल्गोरिदम]] का उपयोग करके आसानी से कार्यान्वित किया जा सकता है। विशेष रूप से, k_extract-min बाइनरी सर्च ट्री पर  विभाजन से मेल खाता है <math display="inline">O(\log n)</math> निवेस  और  ट्री   की पैदावार जिसमें सम्मिलित  है <math display="inline">k</math> सबसे छोटे अवयव . k_insert को मूल प्राथमिकता कतार और सम्मिलन के बैच के संघ द्वारा क्रियान्वित  किया जा सकता है। यदि बैच पहले से ही कुंजी द्वारा क्रमबद्ध है, तो k_insert है <math display="inline">O(k\log (1+\frac{n}{k}))</math> निवेस । अन्यथा, हमें पहले बैच को सॉर्ट करना होगा, इसलिए निवेस  होगी <math display="inline">O(k\log (1+\frac{n}{k})+k\log k)=O(k\log n)</math>. प्राथमिकता कतार के लिए अन्य ऑपरेशन इसी तरह क्रियान्वित  किए जा सकते हैं। उदाहरण के लिए, k_decrease-key को पहले अंतर और फिर यूनियन क्रियान्वित  करके किया जा सकता है, जो पहले अवयव ों को हटाता है और फिर उन्हें अद्यतन कुंजी के साथ वापस सम्मिलित करता है। ये सभी ऑपरेशन अत्यधिक समानांतर हैं, और सैद्धांतिक और व्यावहारिक दक्षता संबंधित शोध पत्रों में पाई जा सकती है।<ref name="join-based">{{citation
   | last1 = Blelloch | first1 = Guy E.
   | last2 = Ferizovic | first2 = Daniel
@@ Line 249: / Line 253: @@
   | year = 2018}}</ref>
-इस खंड का शेष भाग वितरित मेमोरी पर कतार-आधारित एल्गोरिदम पर चर्चा करता है। हम मानते हैं कि प्रत्येक प्रोसेसर की अपनी स्थानीय मेमोरी और  स्थानीय (अनुक्रमिक) प्राथमिकता कतार होती है। वैश्विक (समानांतर) प्राथमिकता कतार के तत्व सभी प्रोसेसरों में वितरित किए जाते हैं।
+इस खंड का शेष भाग वितरित मेमोरी पर कतार-आधारित एल्गोरिदम पर चर्चा करता है। हम मानते हैं कि प्रत्येक प्रोसेसर की अपनी स्थानीय मेमोरी और  स्थानीय (अनुक्रमिक) प्राथमिकता कतार होती है। वैश्विक (समानांतर) प्राथमिकता कतार के अवयव  सभी प्रोसेसरों में वितरित किए जाते हैं।
-[[File:BulkDeletionPQ.svg|thumb|k_extract-min को तीन प्रोसेसर के साथ प्राथमिकता कतार पर निष्पादित किया जाता है। हरे तत्व लौटाए जाते हैं और प्राथमिकता कतार से हटा दिए जाते हैं।]]k_insert ऑपरेशन प्रोसेसर को तत्वों को समान रूप से यादृच्छिक रूप से निर्दिष्ट करता है जो तत्वों को उनकी स्थानीय कतारों में सम्मिलित करता है। ध्यान दें कि एकल तत्व अभी भी कतार में डाले जा सकते हैं। इस रणनीति का उपयोग करते हुए वैश्विक सबसे छोटे तत्व उच्च संभावना वाले प्रत्येक प्रोसेसर के स्थानीय सबसे छोटे तत्वों के संघ में हैं। इस प्रकार प्रत्येक प्रोसेसर वैश्विक प्राथमिकता कतार का  प्रतिनिधि हिस्सा रखता है।
+[[File:BulkDeletionPQ.svg|thumb|k_extract-min को तीन प्रोसेसर के साथ प्राथमिकता कतार पर निष्पादित किया जाता है। हरे अवयव  लौटाए जाते हैं और प्राथमिकता कतार से हटा दिए जाते हैं।]]k_insert ऑपरेशन प्रोसेसर को अवयव ों को समान रूप से यादृच्छिक रूप से निर्दिष्ट करता है जो अवयव ों को उनकी स्थानीय कतारों में सम्मिलित करता है। ध्यान दें कि एकल अवयव  अभी भी कतार में डाले जा सकते हैं। इस रणनीति का उपयोग करते हुए वैश्विक सबसे छोटे अवयव  उच्च संभावना वाले प्रत्येक प्रोसेसर के स्थानीय सबसे छोटे अवयव ों के संघ में हैं। इस प्रकार प्रत्येक प्रोसेसर वैश्विक प्राथमिकता कतार का  प्रतिनिधि हिस्सा रखता है।
-इस संपत्ति का उपयोग तब किया जाता है जब k_extract-min को सबसे छोटे के रूप में निष्पादित किया जाता है <math display="inline">m</math> प्रत्येक स्थानीय कतार के तत्वों को हटा दिया जाता है और परिणाम सेट में एकत्र किया जाता है। परिणाम सेट के तत्व अभी भी अपने मूल प्रोसेसर से जुड़े हुए हैं। तत्वों की संख्या <math display="inline">m</math> प्रत्येक स्थानीय कतार से हटाया जाना इस पर निर्भर करता है <math display="inline">k</math> और प्रोसेसर की संख्या <math display="inline">p</math>.
+इस संपत्ति का उपयोग तब किया जाता है जब k_extract-min को सबसे छोटे के रूप में निष्पादित किया जाता है <math display="inline">m</math> प्रत्येक स्थानीय कतार के अवयव ों को हटा दिया जाता है और परिणाम सेट में एकत्र किया जाता है। परिणाम सेट के अवयव  अभी भी अपने मूल प्रोसेसर से जुड़े हुए हैं। अवयव ों की संख्या <math display="inline">m</math> प्रत्येक स्थानीय कतार से हटाया जाना इस पर निर्भर करता है <math display="inline">k</math> और प्रोसेसर की संख्या <math display="inline">p</math>.
   <ref name=AlgToolbox>{{cite book | first1=Peter | last1=Sanders | first2=Kurt | last2=Mehlhorn | first3=Martin | last3=Dietzfelbinger | first4=Roman | last4= Dementiev | title=अनुक्रमिक और समानांतर एल्गोरिदम और डेटा संरचनाएं - मूल टूलबॉक्स| publisher=Springer International Publishing | date=2019 | pages=226–229 | doi=10.1007/978-3-030-25209-0| isbn=978-3-030-25208-3 | s2cid=201692657 }}</ref>
-समानांतर चयन द्वारा <math display="inline">k</math> परिणाम सेट के सबसे छोटे तत्व निर्धारित किए जाते हैं। उच्च संभावना के साथ ये वैश्विक हैं <math display="inline">k</math> सबसे छोटे तत्व. अगर नहीं, <math display="inline">m</math> प्रत्येक स्थानीय कतार से तत्वों को फिर से हटा दिया जाता है और परिणाम सेट में डाल दिया जाता है। यह ग्लोबल तक किया जाता है <math display="inline">k</math> परिणाम सेट में सबसे छोटे तत्व हैं। अब ये <math display="inline">k</math> तत्वों को वापस किया जा सकता है। परिणाम सेट के अन्य सभी तत्व वापस उनकी स्थानीय कतार में डाल दिए जाते हैं। K_extract-min का चलने का समय अपेक्षित है <math display="inline"> O(\frac{k}{p} \log(n)) </math>, कहाँ <math display="inline">k = \Omega(p \cdot \log (p))</math> और <math display="inline">n</math> प्राथमिकता कतार का आकार है.<ref name="AlgToolbox"/>
+'''समानांतर चयन द्वारा''' <math display="inline">k</math> परिणाम सेट के सबसे छोटे अवयव  निर्धारित किए जाते हैं। उच्च संभावना के साथ ये वैश्विक हैं <math display="inline">k</math> सबसे छोटे अवयव . यदि  नहीं, <math display="inline">m</math> प्रत्येक स्थानीय कतार से अवयव को फिर से हटा दिया जाता है और परिणाम सेट में डाल दिया जाता है। यह ग्लोबल तक किया जाता है <math display="inline">k</math> परिणाम सेट में सबसे छोटे अवयव  हैं। अब ये <math display="inline">k</math> अवयव को वापस किया जा सकता है। परिणाम सेट के अन्य सभी अवयव  वापस उनकी स्थानीय कतार में डाल दिए जाते हैं। K_निकालें-मिनट का चलने का समय अपेक्षित है <math display="inline"> O(\frac{k}{p} \log(n)) </math>, जहाँ  <math display="inline">k = \Omega(p \cdot \log (p))</math> और <math display="inline">n</math> प्राथमिकता कतार का आकार है.<ref name="AlgToolbox"/>
-k_extract-min ऑपरेशन के बाद परिणाम सेट के शेष तत्वों को सीधे स्थानीय कतार में वापस न ले जाकर प्राथमिकता कतार में और सुधार किया जा सकता है। यह परिणाम सेट और स्थानीय कतारों के बीच हर समय आगे और पीछे जाने वाले तत्वों को बचाता है।
+k_extract-min ऑपरेशन के बाद परिणाम सेट के शेष अवयव  को सीधे स्थानीय कतार में वापस न ले जाकर प्राथमिकता कतार में और सुधार किया जा सकता है। यह परिणाम सेट और स्थानीय कतारों के बीच हर समय आगे और पीछे जाने वाले अवयव को बचाता है।
-साथ कई तत्वों को हटाकर काफी तेजी लाई जा सकती है। किन्तु  सभी एल्गोरिदम इस प्रकार की प्राथमिकता कतार का उपयोग नहीं कर सकते हैं। उदाहरण के लिए डिज्क्स्ट्रा का एल्गोरिदम  साथ कई नोड्स पर काम नहीं कर सकता है। एल्गोरिथ्म प्राथमिकता कतार से सबसे छोटी दूरी वाले नोड को लेता है और उसके सभी पड़ोसी नोड्स के लिए नई दूरी की गणना करता है। अगर आप निकालेंगे <math display="inline">k</math> नोड्स,  नोड पर काम करने से दूसरे नोड की दूरी बदल सकती है <math display="inline">k</math> नोड्स. इसलिए के-एलिमेंट ऑपरेशंस का उपयोग करने से डिज्क्स्ट्रा के एल्गोरिदम की लेबल सेटिंग संपत्ति नष्ट हो जाती है।
+इसके अतिरिक्त  अवयव  को हटाकर अधिक  तीव्र लाई जा सकती है। किन्तु  सभी एल्गोरिदम इस प्रकार की प्राथमिकता कतार का उपयोग नहीं कर सकते हैं। उदाहरण के लिए डिज्क्स्ट्रा का एल्गोरिदम  साथ कई नोड्स पर कार्य  नहीं कर सकता है। एल्गोरिथ्म प्राथमिकता कतार से सबसे छोटी दूरी वाले नोड को लेता है और उसके सभी निकटतम  नोड्स के लिए नई दूरी की गणना करता है। यदि  आप निकालेंगे <math display="inline">k</math> नोड्स,  नोड पर कार्य  करने से दूसरे <math display="inline">k</math> नोड की दूरी परिवर्तित कर  सकती है  नोड्स. इसलिए के-एलिमेंट ऑपरेशंस का उपयोग करने से डिज्क्स्ट्रा के एल्गोरिदम की लेबल सेटिंग संपत्ति नष्ट हो जाती है।
 == यह भी देखें ==
@@ Line 265: / Line 269: @@
 * [[बैच कतार]]
 * कमांड कतार
-* [[कार्य अनुसूचक]]
+* [[कार्य अनुसूचक|जॉब  शेड्यूलर]]
 == संदर्भ ==

v t e Well-known data structures
Types	Collection Container
Abstract	Associative array Multimap Retrieval Data Structure List Stack Queue Double-ended queue Priority queue Double-ended priority queue Set Multiset Disjoint-set
Arrays	Bit array Circular buffer Dynamic array Hash table Hashed array tree Sparse matrix
Linked	Association list Linked list Skip list Unrolled linked list XOR linked list
Trees	B-tree Binary search tree AA tree AVL tree Red–black tree Self-balancing tree Splay tree Heap Binary heap Binomial heap Fibonacci heap R-tree R* tree R+ tree Hilbert R-tree Trie Hash tree
Graphs	Binary decision diagram Directed acyclic graph Directed acyclic word graph
List of data structures

Anonymous

Search

प्राथमिकता कतार: Difference between revisions

Namespaces

More

Page actions

Revision as of 18:56, 15 July 2023

Contents

संचालन

कार्यान्वयन

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

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

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

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

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

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

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

पुस्तकालय

अनुप्रयोग

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

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

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

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

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

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

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

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

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

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

यह भी देखें

संदर्भ

अग्रिम पठन

बाहरी संबंध

Navigation

Navigation

Wiki tools

Wiki tools

Anonymous

Search

प्राथमिकता कतार: Difference between revisions

Revision as of 18:56, 15 July 2023

संचालन

कार्यान्वयन

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

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

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

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

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

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

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

पुस्तकालय

अनुप्रयोग

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

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

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

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

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

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

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

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

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

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

यह भी देखें

संदर्भ

अग्रिम पठन

बाहरी संबंध

Navigation

Wiki tools

Page tools

Other projects

Categories