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

Revision as of 16:34, 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] <ब्लॉककोट>

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

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

पुस्तकालय

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

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

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

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

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

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

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

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

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

अनुप्रयोग

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

समानांतर प्रोग्रामिंग मॉडल | साझा-मेमोरी सेटिंग में, समानांतर प्राथमिकता कतार को समानांतर बाइनरी खोज ट्री और जॉइन-आधारित ट्री एल्गोरिदम का उपयोग करके आसानी से कार्यान्वित किया जा सकता है। विशेष रूप से, k_extract-min बाइनरी सर्च ट्री पर विभाजन से मेल खाता है ${\textstyle O(\log n)}$ निवेस और ट्री की पैदावार जिसमें सम्मिलित है ${\textstyle k}$ सबसे छोटे तत्व. k_insert को मूल प्राथमिकता कतार और सम्मिलन के बैच के संघ द्वारा क्रियान्वित किया जा सकता है। यदि बैच पहले से ही कुंजी द्वारा क्रमबद्ध है, तो k_insert है ${\textstyle O(k\log(1+{\frac {n}{k}}))}$ निवेस । अन्यथा, हमें पहले बैच को सॉर्ट करना होगा, इसलिए निवेस होगी ${\textstyle O(k\log(1+{\frac {n}{k}})+k\log k)=O(k\log n)}$ . प्राथमिकता कतार के लिए अन्य ऑपरेशन इसी तरह क्रियान्वित किए जा सकते हैं। उदाहरण के लिए, k_decrease-key को पहले अंतर और फिर यूनियन क्रियान्वित करके किया जा सकता है, जो पहले तत्वों को हटाता है और फिर उन्हें अद्यतन कुंजी के साथ वापस सम्मिलित करता है। ये सभी ऑपरेशन अत्यधिक समानांतर हैं, और सैद्धांतिक और व्यावहारिक दक्षता संबंधित शोध पत्रों में पाई जा सकती है।^[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_extract-min का चलने का समय अपेक्षित है ${\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 1: / Line 1: @@
 {{short description|Abstract data type in computer science}}
-[[कंप्यूटर विज्ञान]] में, '''प्राथमिकता कतार'''  अमूर्त डेटा प्रकार है। अमूर्त डेटा-प्रकार  नियमित कतार (अमूर्त डेटा प्रकार) या [[स्टैक (सार डेटा प्रकार)]] डेटा संरचना के समान। प्राथमिकता कतार में प्रत्येक तत्व की  संबद्ध ''प्राथमिकता'' होती है। प्राथमिकता कतार में, उच्च प्राथमिकता वाले तत्वों को कम प्राथमिकता वाले तत्वों से पहले परोसा जाता है। कुछ कार्यान्वयन में, यदि दो तत्वों की प्राथमिकता समान है, तो उन्हें उसी क्रम में परोसा जाता है जिसमें वे पंक्तिबद्ध थे। अन्य कार्यान्वयन में, समान प्राथमिकता वाले तत्वों का क्रम अपरिभाषित है।
-जबकि प्राथमिकता कतारें अक्सर हीप (डेटा संरचना) का उपयोग करके कार्यान्वित की जाती हैं, वे अवधारणात्मक रूप से हीप से अलग होती हैं। प्राथमिकता कतार  अमूर्त डेटा संरचना है जैसे सूची (अमूर्त डेटा प्रकार) या [[सहयोगी सरणी]]; जिस तरह  सूची को  लिंक की गई सूची के साथ या  ऐरे डेटा संरचना के साथ लागू किया जा सकता है,  प्राथमिकता कतार को  ढेर या किसी अन्य विधि जैसे कि  अनियंत्रित सरणी के साथ लागू किया जा सकता है।
+[[कंप्यूटर विज्ञान]] में, '''प्राथमिकता कतार''' एक नियमित कतार या [[स्टैक (सार डेटा प्रकार)|स्टैक]] [[स्टैक (सार डेटा प्रकार)|डेटा]] संरचना के समान एक अमूर्त डेटा-प्रकार है। प्राथमिकता कतार में प्रत्येक तत्व की एक संबद्ध प्राथमिकता होती है। प्राथमिकता कतार में, उच्च प्राथमिकता वाले तत्वों को लघु  प्राथमिकता वाले तत्वों से पहले रखा  जाता है।और  कुछ कार्यान्वयन में, यदि दो तत्वों की प्राथमिकता समान है, तो उन्हें उसी क्रम में रखा  जाता है जिसमें वे पंक्तिबद्ध थे। अन्य कार्यान्वयन में, समान प्राथमिकता वाले तत्वों का क्रम अपरिभाषित है।
+जबकि प्राथमिकता कतारें प्रायः  हीप (डेटा संरचना) का उपयोग करके कार्यान्वित की जाती हैं, इस प्रकार से यह अवधारणात्मक रूप से हीप से अलग होती हैं। किन्तु प्राथमिकता कतार  अमूर्त डेटा संरचना है जैसे सूची (अमूर्त डेटा संरचना) या [[सहयोगी सरणी]]; जिस तरह  सूची को  लिंक की गई सूची के साथ या  ऐरे डेटा संरचना के साथ क्रियान्वित  किया जा सकता है,  प्राथमिकता कतार के रूप में  या किसी अन्य विधि जैसे कि  अनियंत्रित सरणी के साथ क्रियान्वित  किया जा सकता है।
 ==संचालन ==
@@ Line 10: / Line 11: @@
 * 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 के रूप में जाना जाता है।
+*: कुछ परंपराएं कम मूल्यों को उच्च प्राथमिकता मानते हुए प्राथमिकताओं के क्रम को प्रतिलोम कर  देती हैं, इसलिए इसे get_minimum_element के रूप में भी जाना जा सकता है, और प्रायः  साहित्य में इसे get-min के रूप में जाना जाता है।
 *: इसके बजाय इसे अलग-अलग peek_at_highest_priority_element और delete_element फ़ंक्शंस के रूप में निर्दिष्ट किया जा सकता है, जिन्हें पुल_highest_priority_element बनाने के लिए जोड़ा जा सकता है।
-इसके अलावा, [[पीक (डेटा प्रकार ऑपरेशन)]] (इस संदर्भ में अक्सर फाइंड-मैक्स या फाइंड-मिन कहा जाता है), जो उच्चतम-प्राथमिकता वाले तत्व को लौटाता है लेकिन कतार को संशोधित नहीं करता है, इसे बहुत बार लागू किया जाता है, और लगभग हमेशा बिग ओ में निष्पादित होता है अंकन|O(1) समय. यह ऑपरेशन और इसका O(1) प्रदर्शन प्राथमिकता कतारों के कई अनुप्रयोगों के लिए महत्वपूर्ण है।
+इसके अतिरिक्त , [[पीक (डेटा प्रकार ऑपरेशन)|पीक (डेटा संरचना ऑपरेशन)]] (इस संदर्भ में प्रायः  फाइंड-मैक्स या फाइंड-मिन कहा जाता है), जो उच्चतम-प्राथमिकता वाले तत्व को लौटाता है किन्तु  कतार को संशोधित नहीं करता है, इसे अधिक  बार क्रियान्वित  किया जाता है, और लगभग सदैव  बिग ओ में निष्पादित होता है अंकन O(1) समय. यह ऑपरेशन और इसका O(1) प्रदर्शन प्राथमिकता कतारों के कई अनुप्रयोगों के लिए महत्वपूर्ण है।
-अधिक उन्नत कार्यान्वयन अधिक जटिल संचालन का समर्थन कर सकते हैं, जैसे कि पुल_लोवेस्ट_प्रायोरिटी_एलिमेंट, पहले कुछ उच्चतम या निम्न-प्राथमिकता वाले तत्वों का निरीक्षण करना, कतार को साफ़ करना, कतार के सबसेट को साफ़ करना, बैच सम्मिलित करना, दो या दो से अधिक कतारों को  में विलय करना, प्राथमिकता बढ़ाना किसी तत्व आदि का
+इस प्रकार से अधिक उन्नत कार्यान्वयन अधिक जटिल संचालन का समर्थन कर सकते हैं, जैसे कि पुल_लोवेस्ट_प्रायोरिटी_एलिमेंट, पहले कुछ उच्चतम या निम्न-प्राथमिकता वाले तत्वों का निरीक्षण करना, कतार को साफ़ करना, कतार के सबसेट को साफ़ करना, बैच सम्मिलित करना, दो या दो से अधिक कतारों को  में विलय करना,किसी  भी तत्व  प्राथमिकता बढ़ाना आदि।
-स्टैक (अमूर्त डेटा प्रकार) और क्यू (अमूर्त डेटा प्रकार) को विशेष प्रकार की प्राथमिकता कतारों के रूप में कार्यान्वित किया जा सकता है, प्राथमिकता उस क्रम से निर्धारित होती है जिसमें तत्व डाले जाते हैं।  स्टैक में, प्रत्येक सम्मिलित तत्व की प्राथमिकता नीरस रूप से बढ़ रही है; इस प्रकार, डाला गया अंतिम तत्व हमेशा सबसे पहले पुनर्प्राप्त किया जाता है।  कतार में, प्रत्येक सम्मिलित तत्व की प्राथमिकता नीरस रूप से घट रही है; इस प्रकार, डाला गया पहला तत्व हमेशा सबसे पहले पुनर्प्राप्त किया जाता है।
+स्टैक (अमूर्त डेटा संरचना) और क्यू (अमूर्त डेटा संरचना) को विशेष प्रकार की प्राथमिकता कतारों के रूप में कार्यान्वित किया जा सकता है, प्राथमिकता उस क्रम से निर्धारित होती है जिसमें तत्व इन्सर्ट किये  जाते हैं। इस प्रकार से  स्टैक में, प्रत्येक सम्मिलित तत्व की प्राथमिकता नीरस रूप से बढ़ रही है; इस प्रकार, इन्सर्ट किया  गया अंतिम तत्व सदैव  सबसे प्रथम   पुनर्प्राप्त किया जाता है। किन्तु   कतार में, प्रत्येक सम्मिलित तत्व की प्राथमिकता नीरस रूप से घट रही है; इस प्रकार, समिलित किया गया  गया प्रथम  तत्व सदैव  सर्वप्रथम  पुनर्प्राप्त किया जाता है।
 == कार्यान्वयन ==
@@ Line 26: / Line 27: @@
 === अनुभवहीन कार्यान्वयन ===
-प्राथमिकता कतार को लागू करने के कई सरल, आमतौर पर अप्रभावी तरीके हैं। वे यह समझने में मदद करने के लिए  सादृश्य प्रदान करते हैं कि प्राथमिकता कतार क्या है।
+प्राथमिकता कतार को क्रियान्वित  करने के अनेक  सरल,सामान्यतः अप्रभावी विधि  हैं। वे यह समझने में सहायता  करने के लिए  सादृश्य प्रदान करते हैं कि प्राथमिकता कतार क्या है।
-उदाहरण के लिए, कोई सभी तत्वों को  अवर्गीकृत सूची (O(1) सम्मिलन समय) में रख सकता है। जब भी सर्वोच्च-प्राथमिकता वाले तत्व का अनुरोध किया जाए, तो सभी तत्वों में से सर्वोच्च प्राथमिकता वाले तत्व को खोजें। (O(n) पुल टाइम),
+इस प्रकार से उदाहरण के लिए, कोई सभी तत्वों को  अवर्गीकृत सूची (O(1) सम्मिलन टाइम ) में रख सकता है। जब भी सर्वोच्च-प्राथमिकता वाले तत्व का अनुरोध किया जाए, तो सभी तत्वों में से सर्वोच्च प्राथमिकता वाले तत्व को खोजें। (O(n) पुल टाइम),
   'सम्मिलित करें' (नोड)
@@ Line 49: / Line 50: @@
   }
-दूसरे मामले में, कोई सभी तत्वों को प्राथमिकता क्रमबद्ध सूची (ओ (एन) प्रविष्टि सॉर्ट समय) में रख सकता है, जब भी उच्चतम प्राथमिकता वाले तत्व का अनुरोध किया जाता है, तो सूची में पहला वापस किया जा सकता है। (O(1) खींचने का समय)
+दूसरे स्तिथि  में, अनेक सभी तत्वों को प्राथमिकता क्रमबद्ध सूची (ओ (एन) प्रविष्टि सॉर्ट समय) में रख सकता है, जब भी उच्चतम प्राथमिकता वाले तत्व का अनुरोध किया जाता है, तो सूची में पहला वापस किया जा सकता है। (O(1) पुल टाइम )
   'सम्मिलित करें' (नोड)
   {
@@ Line 71: / Line 72: @@
 === सामान्य कार्यान्वयन ===
-प्रदर्शन में सुधार करने के लिए, प्राथमिकता कतारें आमतौर पर हीप (डेटा संरचना) पर आधारित होती हैं, जो सम्मिलन और निष्कासन के लिए ओ (लॉग एन) प्रदर्शन देती हैं, और शुरुआत में एन तत्वों के सेट से हीप (डेटा संरचना) बनाने के लिए ओ (एन) देती हैं। बुनियादी हीप डेटा संरचना के वेरिएंट जैसे [[ युग्मन ढेर |युग्मन ढेर]] ्स या फाइबोनैचि हीप्स कुछ ऑपरेशनों के लिए बेहतर सीमाएं प्रदान कर सकते हैं।<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(लॉग एन) समय लगता है, चूंकि  तत्वों के उपस्तिथ  अनुक्रम से ट्री   बनाने में ओ(एन लॉग एन) समय लगता है; यह विशिष्ट है जहां किसी के पास पहले से ही इन डेटा संरचनाओं तक पहुंच हो सकती है, जैसे कि तृतीय-पक्ष या मानक पुस्तकालयों के साथ। अंतरिक्ष-जटिलता के दृष्टिकोण से, लिंक की गई सूची के साथ स्व-संतुलन बाइनरी सर्च ट्री का उपयोग करने से अधिक भंडारण की आवश्यकता होती है, क्योंकि इसके लिए अन्य नोड्स के अतिरिक्त संदर्भों को संग्रहीत करने की आवश्यकता होती है।
 कम्प्यूटेशनल-जटिलता के दृष्टिकोण से, प्राथमिकता कतारें सॉर्टिंग एल्गोरिदम के अनुरूप हैं। नीचे प्राथमिकता कतारों और सॉर्टिंग एल्गोरिदम की #समानता पर अनुभाग बताता है कि कैसे कुशल सॉर्टिंग एल्गोरिदम कुशल प्राथमिकता कतारें बना सकते हैं।
 ===विशेषीकृत ढेर===
-कई विशिष्ट हीप (डेटा संरचना) [[डेटा संरचनाएं]] हैं जो या तो अतिरिक्त संचालन की आपूर्ति करती हैं या विशिष्ट प्रकार की कुंजियों, विशेष रूप से पूर्णांक कुंजियों के लिए हीप-आधारित कार्यान्वयन को बेहतर प्रदर्शन करती हैं। मान लीजिए कि संभावित कुंजियों का सेट {1, 2, ..., C} है।
+अनेक विशिष्ट हीप (डेटा संरचना) [[डेटा संरचनाएं]] हैं जो या तो अतिरिक्त संचालन की आपूर्ति करती हैं या विशिष्ट प्रकार की कुंजियों, विशेष रूप से पूर्णांक कुंजियों के लिए हीप-आधारित कार्यान्वयन को उत्तम  प्रदर्शन करती हैं। मान लीजिए कि संभावित कुंजियों का सेट {1, 2, ..., C} है।
-* जब केवल सम्मिलित करें, तो फाइंड-मिन और एक्सट्रैक्ट-मिन की आवश्यकता होती है और पूर्णांक प्राथमिकताओं के मामले में,  [[बाल्टी कतार]] का निर्माण  सरणी के रूप में किया जा सकता है {{mvar|C}} लिंक की गई सूचियाँ और  सूचक {{math|top}}, शुरू में {{mvar|C}}. कुंजी के साथ कोई वस्तु सम्मिलित करना {{mvar|k}} आइटम को इसमें जोड़ता है {{mvar|k}}'वीं सूची, और अद्यतन {{math|top ← min(top, ''k'')}}, दोनों निरंतर समय में। एक्स्ट्रैक्ट-मिन इंडेक्स वाली सूची से  आइटम को हटाता है और लौटाता है {{math|top}}, फिर वृद्धि {{math|top}} यदि आवश्यक हो, जब तक कि यह फिर से  गैर-रिक्त सूची की ओर इशारा न कर दे; यह लेता है {{math|''O''(''C'')}} सबसे खराब स्थिति में समय। ये कतारें ग्राफ़ के शीर्षों को उनकी डिग्री के आधार पर क्रमबद्ध करने के लिए उपयोगी हैं।<ref>{{cite book |last=Skiena |first=Steven |author-link=Steven Skiena |title = एल्गोरिथम डिज़ाइन मैनुअल|publisher=[[Springer Science+Business Media]] |edition=2nd |year = 2010 |isbn=978-1-849-96720-4}}</ref>{{rp|374}}
+* जब केवल सम्मिलित करें, तो फाइंड-मिन और एक्सट्रैक्ट-मिन की आवश्यकता होती है और पूर्णांक प्राथमिकताओं के स्तिथि  में,  [[बाल्टी कतार|बकेट  कतार]] का निर्माण {{mvar|C}}  सरणी   के रूप में किया जा सकता है  लिंक की गई सूचियाँ  और  सूचक {{math|top}}, प्रारंभ  में {{mvar|C}}. कुंजी के साथ कोई वस्तु सम्मिलित करना {{mvar|k}} वस्तु   को इसमें जोड़ता है k'th सूची, और अद्यतन {{math|top ← min(top, ''k'')}}, दोनों निरंतर समय में। एक्स्ट्रैक्ट-मिन इंडेक्स {{math|top}} वाली सूची से  वस्तु   को हटाता है और लौटाता है , फिर वृद्धि {{math|top}} यदि आवश्यक हो, जब तक कि यह फिर से  गैर-रिक्त सूची की ओर संकेत  न कर दे; इस प्रकार से  अधिक व्यर्थ  स्थिति में  {{math|''O''(''C'')}} टाइम  लगता है । ये कतारें ग्राफ़ के शीर्षों को उनकी डिग्री के आधार पर क्रमबद्ध करने के लिए उपयोगी होती  हैं।<ref>{{cite book |last=Skiena |first=Steven |author-link=Steven Skiena |title = एल्गोरिथम डिज़ाइन मैनुअल|publisher=[[Springer Science+Business Media]] |edition=2nd |year = 2010 |isbn=978-1-849-96720-4}}</ref>{{rp|374}}
-* [[वैन एम्डे बोस कदम]] ओ (लॉग लॉग सी) समय में न्यूनतम, अधिकतम, सम्मिलित करें, हटाएं, खोज, निकालने-मिनट, निकालने-अधिकतम, पूर्ववर्ती और उत्तराधिकारी] संचालन का समर्थन करता है, लेकिन इसमें लगभग छोटी कतारों के लिए स्थान लागत होती है ओ(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> हैशिंग से स्थान को काफी कम किया जा सकता है।
+* [[वैन एम्डे बोस कदम]] ओ (लॉग लॉग सी) समय में न्यूनतम, अधिकतम, सम्मिलित करें, हटाएं, खोज, निकालने-मिनट, निकालने-अधिकतम, पूर्ववर्ती और उत्तराधिकारी] संचालन का समर्थन करता है, किन्तु  इसमें लगभग लघु  कतारों के लिए स्थान निवेस  होती है ओ(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) समय में न्यूनतम ऑपरेशन और <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 94: / Line 95: @@
 === सॉर्ट करने के लिए प्राथमिकता कतार का उपयोग करना ===
-प्राथमिकता कतारों के [[परिचालन शब्दार्थ]] स्वाभाविक रूप से  छँटाई विधि का सुझाव देते हैं: क्रमबद्ध किए जाने वाले सभी तत्वों को प्राथमिकता कतार में डालें, और क्रमिक रूप से उन्हें हटा दें; वे क्रमबद्ध तरीके से सामने आएंगे। यह वास्तव में कई [[छँटाई एल्गोरिथ्म]] द्वारा उपयोग की जाने वाली प्रक्रिया है,  बार प्राथमिकता कतार द्वारा प्रदान की गई अमूर्तता (कंप्यूटर विज्ञान) की परत हटा दी जाती है। यह सॉर्टिंग विधि निम्नलिखित सॉर्टिंग एल्गोरिदम के बराबर है:
+इस प्रकार से प्राथमिकता कतारों के [[परिचालन शब्दार्थ]] स्वाभाविक रूप से  सोर्टिंग  विधि का सुझाव देते हैं: अर्थात क्रमबद्ध किए जाने वाले सभी तत्वों को प्राथमिकता कतार में रखे , और क्रमिक रूप से उन्हें रिमूव कर  दें; वे क्रमबद्ध विधि  से सामने आएंगे यह वास्तव में कई [[छँटाई एल्गोरिथ्म|सोर्टिंग  एल्गोरिथ्म]] द्वारा उपयोग की जाने वाली प्रक्रिया है,  इस प्रकार से  प्राथमिकता कतार द्वारा प्रदान की गई अमूर्तता (कंप्यूटर विज्ञान) की लेयर हटा दी जाती है। यह सॉर्टिंग विधि निम्नलिखित सॉर्टिंग एल्गोरिदम के समान  है:
 {|class="wikitable sortable"
-! Name !! Priority Queue Implementation !! Best !! Average !! Worst
+! नाम !! प्राथमिकता कतार कार्यान्वयन !! श्रेष्ठ !! औसत !! निकृष्टतम
 |- align="center"
-| [[Heapsort]]
+| [[Heapsort|हीपसॉर्ट]]
-| [[Heap (data structure)|Heap]]
+| [[Heap (data structure)|हीप]]
 |style="background:#dfd"| <math>n \log(n)</math>
 |style="background:#dfd"|<math>n \log(n)</math>
@@ Line 107: / Line 108: @@
 |- align="center"
-| [[Smoothsort]]
+| [[Smoothsort|स्मूथसॉर्ट]]
-| Leonardo Heap
+| लियोनार्डो हीप
 |style="background:#dfd"|<math>n</math>
 |style="background:#dfd"|<math>n \log(n)</math>
@@ Line 114: / Line 115: @@
 |- align="center"
-| [[Selection sort]]
+| [[Selection sort|चयन क्रम]]
-| Unordered [[Array#In computer science|Array]]
+| अव्यवस्थित सारणी
 |style="background:#fdd"|<math>n^2</math>
 |style="background:#fdd"|<math>n^2</math>
@@ Line 121: / Line 122: @@
 |- align="center"
-| [[Insertion sort]]
+| [[Insertion sort|सम्मिलन सॉर्ट]]
-| Ordered [[Array#In computer science|Array]]
+| क्रमबद्ध सारणी
 |style="background:#dfd"|<math>n </math>
 |style="background:#fdd"|<math>n^2 </math>
@@ Line 128: / Line 129: @@
 |- align="center"
-| [[Tree sort]]
+| [[Tree sort|ट्री]] [[Insertion sort|सॉर्ट]]
-| [[Self-balancing binary search tree]]
+| [[Self-balancing binary search tree|सेल्फ-बैलेंसिंग बाइनरी सर्च ट्री]]
 |style="background:#dfd"|<math>n \log(n)</math>
 |style="background:#dfd"|<math>n \log(n)</math>
@@ Line 138: / Line 139: @@
 === प्राथमिकता कतार बनाने के लिए सॉर्टिंग एल्गोरिदम का उपयोग करना ===
-प्राथमिकता कतार को लागू करने के लिए सॉर्टिंग एल्गोरिदम का भी उपयोग किया जा सकता है। विशेष रूप से, थोरुप कहते हैं:<ref>{{Cite journal | last1 = Thorup | first1 = Mikkel | author-link1 = Mikkel Thorup | year = 2007 | title = प्राथमिकता कतारों और छँटाई के बीच समानता| journal = [[Journal of the ACM]] | volume = 54 | issue = 6 | page = 28 | doi = 10.1145/1314690.1314692 | s2cid = 11494634 }}</ref>
+प्राथमिकता कतार को क्रियान्वित  करने के लिए सॉर्टिंग एल्गोरिदम का भी उपयोग किया जा सकता है। विशेष रूप से, थोरुप कहते हैं:<ref>{{Cite journal | last1 = Thorup | first1 = Mikkel | author-link1 = Mikkel Thorup | year = 2007 | title = प्राथमिकता कतारों और छँटाई के बीच समानता| journal = [[Journal of the ACM]] | volume = 54 | issue = 6 | page = 28 | doi = 10.1145/1314690.1314692 | s2cid = 11494634 }}</ref>
-<ब्लॉककोट>
+'''<ब्लॉककोट>'''
-हम प्राथमिकता कतारों से सॉर्टिंग तक  सामान्य नियतात्मक रैखिक स्थान में कमी प्रस्तुत करते हैं, जिसका अर्थ है कि यदि हम प्रति कुंजी एस (एन) समय में एन कुंजी को सॉर्ट कर सकते हैं, तो ओ (एस (एन)) में हटाने और डालने का समर्थन करने वाली  प्राथमिकता कतार है। निरंतर समय में समय और खोज-मिनट।
+हम प्राथमिकता कतारों से सॉर्टिंग तक  सामान्य नियतात्मक रैखिक स्थान में कमी प्रस्तुत करते हैं, जिसका अर्थ है कि यदि हम प्रति कुंजी एस (एन) समय में एन कुंजी को सॉर्ट कर सकते हैं, तो ओ (एस (एन)) में हटाने और डालने का समर्थन करने वाली  प्राथमिकता कतार है। निरंतर समय में समय और खोज-मिनट आदि ।
 अर्थात्, यदि कोई सॉर्टिंग एल्गोरिदम है जो प्रति कुंजी 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) पुलिंग और ओ(लॉग एन) सम्मिलन के साथ प्राथमिकता कतार बना सकता है।
@@ Line 146: / Line 148: @@
 == पुस्तकालय ==
-प्राथमिकता कतार को अक्सर  [[कंटेनर (सार डेटा प्रकार)]] माना जाता है।
+प्राथमिकता कतार को प्रायः   [[कंटेनर (सार डेटा प्रकार)|कंटेनर (सार डेटा संरचना)]] माना जाता है।
-[[मानक टेम्पलेट लाइब्रेरी]] (STL), और [[C++]] 1998 मानक, [https://en.cppreference.com/w/cpp/container/priority_queue std::priority_queue] को STL [[कंटेनर (प्रोग्रामिंग)]] [[एडाप्टर (प्रोग्रामिंग)]] में से  के रूप में निर्दिष्ट करता है ) [[टेम्पलेट (प्रोग्रामिंग)]]एस। हालाँकि, यह निर्दिष्ट नहीं करता है कि समान प्राथमिकता वाले दो तत्वों को कैसे परोसा जाना चाहिए, और वास्तव में, सामान्य कार्यान्वयन उन्हें कतार में उनके क्रम के अनुसार वापस नहीं करेगा। यह  अधिकतम-प्राथमिकता-कतार लागू करता है, और इसमें तीन पैरामीटर होते हैं: सॉर्टिंग के लिए  तुलनात्मक ऑब्जेक्ट जैसे कि फ़ंक्शन ऑब्जेक्ट (यदि अनिर्दिष्ट है तो कम<T> पर डिफ़ॉल्ट), डेटा संरचनाओं को संग्रहीत करने के लिए अंतर्निहित कंटेनर (std::vector पर डिफ़ॉल्ट) <T>), और अनुक्रम के आरंभ और अंत में दो पुनरावर्तक। वास्तविक एसटीएल कंटेनरों के विपरीत, यह [[इटरेटर]] को इसके तत्वों की अनुमति नहीं देता है (यह सख्ती से इसकी अमूर्त डेटा प्रकार परिभाषा का पालन करता है)। एसटीएल में बाइनरी मैक्स-हीप के रूप में  अन्य रैंडम-एक्सेस कंटेनर में हेरफेर करने के लिए उपयोगिता कार्य भी हैं। बूस्ट (C++ लाइब्रेरीज़) का लाइब्रेरी हीप में कार्यान्वयन भी है।
+[[मानक टेम्पलेट लाइब्रेरी]] (STL), और [[C++]] 1998 मानक, [https://en.cppreference.com/w/cpp/container/priority_queue std::priority_queue] को STL [[कंटेनर (प्रोग्रामिंग)]] [[एडाप्टर (प्रोग्रामिंग)]] में से  के रूप में निर्दिष्ट करता है ) [[टेम्पलेट (प्रोग्रामिंग)]]एस। चूंकि , यह निर्दिष्ट नहीं करता है कि समान प्राथमिकता वाले दो तत्वों को कैसे परोसा जाना चाहिए, और वास्तव में, सामान्य कार्यान्वयन उन्हें कतार में उनके क्रम के अनुसार वापस नहीं करेगा। यह  अधिकतम-प्राथमिकता-कतार क्रियान्वित  करता है, और इसमें तीन पैरामीटर होते हैं: सॉर्टिंग के लिए  तुलनात्मक ऑब्जेक्ट जैसे कि फ़ंक्शन ऑब्जेक्ट (यदि अनिर्दिष्ट है तो कम<T> पर डिफ़ॉल्ट), डेटा संरचनाओं को संग्रहीत करने के लिए अंतर्निहित कंटेनर (std::vector पर डिफ़ॉल्ट) <T>), और अनुक्रम के आरंभ और अंत में दो पुनरावर्तक। वास्तविक एसटीएल कंटेनरों के विपरीत, यह [[इटरेटर]] को इसके तत्वों की अनुमति नहीं देता है (यह सख्ती से इसकी अमूर्त डेटा संरचना परिभाषा का पालन करता है)। एसटीएल में बाइनरी मैक्स-हीप के रूप में  अन्य रैंडम-एक्सेस कंटेनर में हेरफेर करने के लिए उपयोगिता कार्य भी हैं। बूस्ट (C++ लाइब्रेरीज़) का लाइब्रेरी हीप में कार्यान्वयन भी है।
-पायथन का [https://docs.python.org/library/heapq.html heapq] मॉड्यूल  सूची के शीर्ष पर  बाइनरी मिन-हीप लागू करता है।
+पायथन का [https://docs.python.org/library/heapq.html heapq] मॉड्यूल  सूची के शीर्ष पर  बाइनरी मिन-हीप क्रियान्वित  करता है।
-[[जावा (प्रोग्रामिंग भाषा)]] की लाइब्रेरी में  शामिल है {{Javadoc:SE|java/util|PriorityQueue}} वर्ग, जो न्यूनतम-प्राथमिकता-कतार लागू करता है।
+[[जावा (प्रोग्रामिंग भाषा)]] की लाइब्रेरी में  सम्मिलित  है {{Javadoc:SE|java/util|PriorityQueue}} वर्ग, जो न्यूनतम-प्राथमिकता-कतार क्रियान्वित  करता है।
-.NET की लाइब्रेरी में  [https://docs.microsoft.com/en-us/dotnet/api/system.collections.generic.priorityqueue-2?view=net-6.0 प्राथमिकता क्यू] वर्ग शामिल है, जो  सरणी-समर्थित को लागू करता है, चतुर्धातुक न्यूनतम-ढेर।
+.NET की लाइब्रेरी में  [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 प्राथमिकता क्यू] वर्ग शामिल है, जो अधिकतम-प्राथमिकता-क्यू लागू करता है।
+[[स्काला (प्रोग्रामिंग भाषा)]] की लाइब्रेरी में  [https://www.scala-lang.org/api/current/scala/collection/mutable/PriorityQueue.html प्राथमिकता क्यू] वर्ग सम्मिलित  है, जो अधिकतम-प्राथमिकता-क्यू क्रियान्वित  करता है।
-गो (प्रोग्रामिंग भाषा) की लाइब्रेरी में  [http://golang.org/pkg/container/heap/container/heap] मॉड्यूल होता है, जो किसी भी संगत डेटा संरचना के शीर्ष पर  मिन-हीप लागू करता है।
+गो (प्रोग्रामिंग भाषा) की लाइब्रेरी में  [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] संरचना शामिल है, जो  मिन-हीप लागू करती है।
+Apple के [[कोर फाउंडेशन]] फ्रेमवर्क में  [https://developer.apple.com/library/mac/#documentation/CoreFoundation/Reference/CFBinaryHeapRef/Reference/reference.html CFBinaryHeap] संरचना सम्मिलित  है, जो  मिन-हीप क्रियान्वित  करती है।
 == अनुप्रयोग ==
@@ Line 170: / Line 172: @@
 [[ संगणक संजाल | संगणक संजाल]] [[राउटर (कंप्यूटिंग)]] से ट्रांसमिशन लाइन पर [[बैंडविड्थ (कंप्यूटिंग)]] जैसे सीमित संसाधनों को प्रबंधित करने के लिए प्राथमिकता कतार का उपयोग किया जा सकता है। अपर्याप्त बैंडविड्थ के कारण आउटगोइंग [[ट्रैफ़िक]] कतार में लगने की स्थिति में, आगमन पर ट्रैफ़िक को सर्वोच्च प्राथमिकता वाली कतार से भेजने के लिए अन्य सभी कतारों को रोका जा सकता है। यह सुनिश्चित करता है कि प्राथमिकता वाले ट्रैफ़िक (जैसे कि वास्तविक समय ट्रैफ़िक, उदाहरण के लिए [[ इंटरनेट प्रोटोकॉल पर आवाज़ |इंटरनेट प्रोटोकॉल पर आवाज़]] कनेक्शन की [[वास्तविक समय परिवहन प्रोटोकॉल]] स्ट्रीम) को कम से कम देरी के साथ अग्रेषित किया जाता है और कतार के अधिकतम तक पहुंचने के कारण अस्वीकार होने की कम से कम संभावना होती है। क्षमता। सर्वोच्च प्राथमिकता कतार खाली होने पर अन्य सभी ट्रैफ़िक को संभाला जा सकता है। उपयोग किया जाने वाला  अन्य तरीका उच्च प्राथमिकता वाली कतारों से असंगत रूप से अधिक ट्रैफ़िक भेजना है।
-स्थानीय क्षेत्र नेटवर्क के लिए कई आधुनिक प्रोटोकॉल में [[ मीडिया अभिगम नियंत्रण |मीडिया अभिगम नियंत्रण]] (मैक) उप-परत पर प्राथमिकता कतारों की अवधारणा भी शामिल है ताकि यह सुनिश्चित किया जा सके कि उच्च-प्राथमिकता वाले एप्लिकेशन (जैसे [[वीओआईपी]] या [[आईपीटीवी]]) अन्य अनुप्रयोगों की तुलना में कम विलंबता का अनुभव करते हैं जिन्हें इसके साथ परोसा जा सकता है। [[सर्वोत्तम प्रयास वाली सेवा]]. उदाहरणों में IEEE 802.11e (IEEE 802.11 में  संशोधन जो [[सेवा की गुणवत्ता]] प्रदान करता है) और [[ITU-T]] G.hn (मौजूदा होम वायरिंग (पावर लाइन संचार, फोन लाइन और कोएक्स पर ईथरनेट) का उपयोग करके हाई-स्पीड [[लोकल एरिया नेटवर्क]] के लिए  मानक) शामिल हैं। .
+स्थानीय क्षेत्र नेटवर्क के लिए कई आधुनिक प्रोटोकॉल में [[ मीडिया अभिगम नियंत्रण |मीडिया अभिगम नियंत्रण]] (मैक) उप-परत पर प्राथमिकता कतारों की अवधारणा भी सम्मिलित  है ताकि यह सुनिश्चित किया जा सके कि उच्च-प्राथमिकता वाले एप्लिकेशन (जैसे [[वीओआईपी]] या [[आईपीटीवी]]) अन्य अनुप्रयोगों की तुलना में कम विलंबता का अनुभव करते हैं जिन्हें इसके साथ परोसा जा सकता है। [[सर्वोत्तम प्रयास वाली सेवा]]. उदाहरणों में IEEE 802.11e (IEEE 802.11 में  संशोधन जो [[सेवा की गुणवत्ता]] प्रदान करता है) और [[ITU-T]] G.hn (उपस्तिथ  होम वायरिंग (पावर लाइन संचार, फोन लाइन और कोएक्स पर ईथरनेट) का उपयोग करके हाई-स्पीड [[लोकल एरिया नेटवर्क]] के लिए  मानक) सम्मिलित  हैं। .
-आम तौर पर  सीमा (पोलिसर) उस बैंडविड्थ को सीमित करने के लिए निर्धारित की जाती है जो उच्चतम प्राथमिकता कतार से ट्रैफ़िक ले सकता है, ताकि उच्च प्राथमिकता वाले पैकेटों को अन्य सभी ट्रैफ़िक को रोकने से रोका जा सके। यह सीमा आमतौर पर सिस्को सिस्टम्स, इंक. [[ प्रबंधक को कॉल करो |प्रबंधक को कॉल करो]] जैसे उच्च स्तरीय नियंत्रण उदाहरणों के कारण कभी नहीं पहुंचती है, जिसे प्रोग्राम की गई बैंडविड्थ सीमा से अधिक होने वाली कॉल को रोकने के लिए प्रोग्राम किया जा सकता है।
+सामान्यतः   सीमा (पोलिसर) उस बैंडविड्थ को सीमित करने के लिए निर्धारित की जाती है जो उच्चतम प्राथमिकता कतार से ट्रैफ़िक ले सकता है, ताकि उच्च प्राथमिकता वाले पैकेटों को अन्य सभी ट्रैफ़िक को रोकने से रोका जा सके। यह सीमासामान्यतः सिस्को सिस्टम्स, इंक. [[ प्रबंधक को कॉल करो |प्रबंधक को कॉल करो]] जैसे उच्च स्तरीय नियंत्रण उदाहरणों के कारण कभी नहीं पहुंचती है, जिसे प्रोग्राम की गई बैंडविड्थ सीमा से अधिक होने वाली कॉल को रोकने के लिए प्रोग्राम किया जा सकता है।
 === [[असतत घटना अनुकरण]] ===
@@ Line 181: / Line 183: @@
 === दिज्क्स्ट्रा का एल्गोरिथ्म ===
-जब ग्राफ़ को आसन्न सूची या मैट्रिक्स के रूप में संग्रहीत किया जाता है, तो दिज्क्स्ट्रा के एल्गोरिदम को कार्यान्वित करते समय न्यूनतम कुशलता से निकालने के लिए प्राथमिकता कतार का उपयोग किया जा सकता है, हालांकि किसी को प्राथमिकता कतार में किसी विशेष शीर्ष की प्राथमिकता को कुशलतापूर्वक बदलने की क्षमता की भी आवश्यकता होती है।
+जब ग्राफ़ को आसन्न सूची या मैट्रिक्स के रूप में संग्रहीत किया जाता है, तो दिज्क्स्ट्रा के एल्गोरिदम को कार्यान्वित करते समय न्यूनतम कुशलता से निकालने के लिए प्राथमिकता कतार का उपयोग किया जा सकता है, चूंकि  किसी को प्राथमिकता कतार में किसी विशेष शीर्ष की प्राथमिकता को कुशलतापूर्वक बदलने की क्षमता की भी आवश्यकता होती है।
 यदि इसके बजाय,  ग्राफ़ को नोड ऑब्जेक्ट के रूप में संग्रहीत किया जाता है, और प्राथमिकता-नोड जोड़े को ढेर में डाला जाता है, तो किसी विशेष शीर्ष की प्राथमिकता को बदलना आवश्यक नहीं है यदि कोई विज़िट किए गए नोड्स को ट्रैक करता है।  बार  नोड पर जाने के बाद, यदि यह दोबारा ढेर में आता है (पहले इसके साथ कम प्राथमिकता संख्या जुड़ी हुई थी), तो इसे पॉप-ऑफ कर दिया जाता है और अनदेखा कर दिया जाता है।
@@ Line 187: / Line 189: @@
 === [[हफ़मैन कोडिंग]] ===
-हफ़मैन कोडिंग के लिए व्यक्ति को दो सबसे कम आवृत्ति वाले पेड़ों को बार-बार प्राप्त करने की आवश्यकता होती है।  प्राथमिकता कतार हफ़मैन कोडिंग#संपीड़न है।
+हफ़मैन कोडिंग के लिए व्यक्ति को दो सबसे कम आवृत्ति वाले ट्री  ों को बार-बार प्राप्त करने की आवश्यकता होती है।  प्राथमिकता कतार हफ़मैन कोडिंग#संपीड़न है।
 === [[सर्वोत्तम-प्रथम खोज]] एल्गोरिदम ===
-सर्वश्रेष्ठ-प्रथम खोज एल्गोरिदम, ए * खोज एल्गोरिदम की तरह,  [[भारित ग्राफ]]़ के दो वर्टेक्स (ग्राफ़ सिद्धांत) या [[नोड (ग्राफ़ सिद्धांत)]] के बीच सबसे छोटा रास्ता ढूंढते हैं, सबसे आशाजनक मार्गों को पहले आज़माते हैं। अज्ञात मार्गों पर नज़र रखने के लिए प्राथमिकता कतार (जिसे फ्रिंज भी कहा जाता है) का उपयोग किया जाता है; जिसके लिए कुल पथ लंबाई का अनुमान (ए* के मामले में निचली सीमा) सबसे छोटा है, उसे सर्वोच्च प्राथमिकता दी जाती है। यदि मेमोरी सीमाएं सर्वोत्तम-प्रथम खोज को अव्यवहारिक बनाती हैं, तो कम-प्राथमिकता वाली वस्तुओं को हटाने की अनुमति देने के लिए [[डबल-एंडेड प्राथमिकता कतार]] के साथ [[एसएमए*]] एल्गोरिदम जैसे वेरिएंट का उपयोग किया जा सकता है।
+सर्वश्रेष्ठ-प्रथम खोज एल्गोरिदम, ए * खोज एल्गोरिदम की तरह,  [[भारित ग्राफ]]़ के दो वर्टेक्स (ग्राफ़ सिद्धांत) या [[नोड (ग्राफ़ सिद्धांत)]] के बीच सबसे छोटा रास्ता ढूंढते हैं, सबसे आशाजनक मार्गों को पहले आज़माते हैं। अज्ञात मार्गों पर नज़र रखने के लिए प्राथमिकता कतार (जिसे फ्रिंज भी कहा जाता है) का उपयोग किया जाता है; जिसके लिए कुल पथ लंबाई का अनुमान (ए* के स्तिथि  में निचली सीमा) सबसे छोटा है, उसे सर्वोच्च प्राथमिकता दी जाती है। यदि मेमोरी सीमाएं सर्वोत्तम-प्रथम खोज को अव्यवहारिक बनाती हैं, तो कम-प्राथमिकता वाली वस्तुओं को हटाने की अनुमति देने के लिए [[डबल-एंडेड प्राथमिकता कतार]] के साथ [[एसएमए*]] एल्गोरिदम जैसे वेरिएंट का उपयोग किया जा सकता है।
 === [[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 210: / Line 212: @@
 </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 अब पहुंच योग्य नहीं है।]]प्राथमिकता कतार तक समवर्ती पहुंच को समवर्ती पढ़ें, समवर्ती लिखें (सीआरसीडब्ल्यू) 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/
-}}</ref> इसके अलावा,  परमाणु तुल्यकालन आदिम, तुलना-और-स्वैप, का उपयोग स्किप सूची को [[लॉक (कंप्यूटर विज्ञान)]]-मुक्त बनाने के लिए किया जाता है। स्किप सूची के नोड्स में  अद्वितीय कुंजी,  प्राथमिकता, [[पॉइंटर (कंप्यूटर प्रोग्रामिंग)]] की  सरणी डेटा संरचना, प्रत्येक स्तर के लिए, अगले नोड्स और  डिलीट मार्क शामिल होते हैं। यदि नोड किसी प्रक्रिया द्वारा हटाया जाने वाला है तो डिलीट मार्क चिह्नित करता है। यह सुनिश्चित करता है कि अन्य प्रक्रियाएं विलोपन पर उचित रूप से प्रतिक्रिया कर सकती हैं।
+}}</ref> इसके अतिरिक्त ,  परमाणु तुल्यकालन आदिम, तुलना-और-स्वैप, का उपयोग स्किप सूची को [[लॉक (कंप्यूटर विज्ञान)]]-मुक्त बनाने के लिए किया जाता है। स्किप सूची के नोड्स में  अद्वितीय कुंजी,  प्राथमिकता, [[पॉइंटर (कंप्यूटर प्रोग्रामिंग)]] की  सरणी डेटा संरचना, प्रत्येक स्तर के लिए, अगले नोड्स और  डिलीट मार्क सम्मिलित  होते हैं। यदि नोड किसी प्रक्रिया द्वारा हटाया जाने वाला है तो डिलीट मार्क चिह्नित करता है। यह सुनिश्चित करता है कि अन्य प्रक्रियाएं विलोपन पर उचित रूप से प्रतिक्रिया कर सकती हैं।
-*इन्सर्ट(ई): सबसे पहले,  कुंजी और प्राथमिकता वाला  नया नोड बनाया जाता है। इसके अलावा, नोड को कई स्तर दिए गए हैं, जो पॉइंटर्स की सरणी के आकार को निर्धारित करते हैं। फिर नए नोड को सम्मिलित करने की सही स्थिति खोजने के लिए  खोज की जाती है। खोज पहले नोड से और उच्चतम स्तर से शुरू होती है। फिर स्किप सूची को निम्नतम स्तर तक ले जाया जाता है जब तक कि सही स्थिति नहीं मिल जाती। खोज के दौरान, प्रत्येक स्तर के लिए अंतिम ट्रैवर्स किए गए नोड को उस स्तर पर नए नोड के लिए मूल नोड के रूप में सहेजा जाएगा। इसके अलावा, मूल नोड का सूचक जिस नोड की ओर इशारा करता है, उस स्तर पर नए नोड के उत्तराधिकारी नोड के रूप में सहेजा जाएगा। बाद में, नए नोड के प्रत्येक स्तर के लिए, मूल नोड के पॉइंटर्स को नए नोड पर सेट किया जाएगा। अंत में, नए नोड के प्रत्येक स्तर के लिए पॉइंटर्स को संबंधित उत्तराधिकारी नोड्स पर सेट किया जाएगा।
+*इन्सर्ट(ई): सबसे पहले,  कुंजी और प्राथमिकता वाला  नया नोड बनाया जाता है। इसके अतिरिक्त , नोड को कई स्तर दिए गए हैं, जो पॉइंटर्स की सरणी के आकार को निर्धारित करते हैं। फिर नए नोड को सम्मिलित करने की सही स्थिति खोजने के लिए  खोज की जाती है। खोज पहले नोड से और उच्चतम स्तर से शुरू होती है। फिर स्किप सूची को निम्नतम स्तर तक ले जाया जाता है जब तक कि सही स्थिति नहीं मिल जाती। खोज के दौरान, प्रत्येक स्तर के लिए अंतिम ट्रैवर्स किए गए नोड को उस स्तर पर नए नोड के लिए मूल नोड के रूप में सहेजा जाएगा। इसके अतिरिक्त , मूल नोड का सूचक जिस नोड की ओर इशारा करता है, उस स्तर पर नए नोड के उत्तराधिकारी नोड के रूप में सहेजा जाएगा। बाद में, नए नोड के प्रत्येक स्तर के लिए, मूल नोड के पॉइंटर्स को नए नोड पर सेट किया जाएगा। अंत में, नए नोड के प्रत्येक स्तर के लिए पॉइंटर्स को संबंधित उत्तराधिकारी नोड्स पर सेट किया जाएगा।
 *एक्स्ट्रेक्ट-मिन: सबसे पहले, स्किप सूची को तब तक ट्रैवर्स किया जाता है जब तक कि  नोड नहीं पहुंच जाता है जिसका डिलीट मार्क सेट नहीं है। यह डिलीट मार्क उस नोड के लिए सत्य पर सेट है। अंत में हटाए गए नोड के मूल नोड्स के पॉइंटर्स अपडेट किए जाते हैं।
-यदि प्राथमिकता कतार तक समवर्ती पहुंच की अनुमति दी जाती है, तो दो प्रक्रियाओं के बीच टकराव उत्पन्न हो सकता है। उदाहरण के लिए, यदि  प्रक्रिया  नया नोड डालने का प्रयास कर रही है, लेकिन उसी समय  अन्य प्रक्रिया उस नोड के पूर्ववर्ती को हटाने वाली है तो  विरोध उत्पन्न होता है।<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|छवि देखें)
+यदि प्राथमिकता कतार तक समवर्ती पहुंच की अनुमति दी जाती है, तो दो प्रक्रियाओं के बीच टकराव उत्पन्न हो सकता है। उदाहरण के लिए, यदि  प्रक्रिया  नया नोड डालने का प्रयास कर रही है, किन्तु  उसी समय  अन्य प्रक्रिया उस नोड के पूर्ववर्ती को हटाने वाली है तो  विरोध उत्पन्न होता है।<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|छवि देखें)
 === के-तत्व संचालन ===
@@ Line 225: / Line 227: @@
 उदाहरण के लिए, 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 257: / Line 259: @@
 k_extract-min ऑपरेशन के बाद परिणाम सेट के शेष तत्वों को सीधे स्थानीय कतार में वापस न ले जाकर प्राथमिकता कतार में और सुधार किया जा सकता है। यह परिणाम सेट और स्थानीय कतारों के बीच हर समय आगे और पीछे जाने वाले तत्वों को बचाता है।
-साथ कई तत्वों को हटाकर काफी तेजी लाई जा सकती है। लेकिन सभी एल्गोरिदम इस प्रकार की प्राथमिकता कतार का उपयोग नहीं कर सकते हैं। उदाहरण के लिए डिज्क्स्ट्रा का एल्गोरिदम  साथ कई नोड्स पर काम नहीं कर सकता है। एल्गोरिथ्म प्राथमिकता कतार से सबसे छोटी दूरी वाले नोड को लेता है और उसके सभी पड़ोसी नोड्स के लिए नई दूरी की गणना करता है। अगर आप निकालेंगे <math display="inline">k</math> नोड्स,  नोड पर काम करने से दूसरे नोड की दूरी बदल सकती है <math display="inline">k</math> नोड्स. इसलिए के-एलिमेंट ऑपरेशंस का उपयोग करने से डिज्क्स्ट्रा के एल्गोरिदम की लेबल सेटिंग संपत्ति नष्ट हो जाती है।
+साथ कई तत्वों को हटाकर काफी तेजी लाई जा सकती है। किन्तु  सभी एल्गोरिदम इस प्रकार की प्राथमिकता कतार का उपयोग नहीं कर सकते हैं। उदाहरण के लिए डिज्क्स्ट्रा का एल्गोरिदम  साथ कई नोड्स पर काम नहीं कर सकता है। एल्गोरिथ्म प्राथमिकता कतार से सबसे छोटी दूरी वाले नोड को लेता है और उसके सभी पड़ोसी नोड्स के लिए नई दूरी की गणना करता है। अगर आप निकालेंगे <math display="inline">k</math> नोड्स,  नोड पर काम करने से दूसरे नोड की दूरी बदल सकती है <math display="inline">k</math> नोड्स. इसलिए के-एलिमेंट ऑपरेशंस का उपयोग करने से डिज्क्स्ट्रा के एल्गोरिदम की लेबल सेटिंग संपत्ति नष्ट हो जाती है।
 == यह भी देखें ==

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 16:34, 15 July 2023

Contents

संचालन

कार्यान्वयन

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

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

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

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

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

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

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

पुस्तकालय

अनुप्रयोग

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

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

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

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

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

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

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

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

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

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

यह भी देखें

संदर्भ

अग्रिम पठन

बाहरी संबंध

Navigation

Navigation

Wiki tools

Wiki tools

Anonymous

Search

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

Revision as of 16:34, 15 July 2023

संचालन

कार्यान्वयन

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

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

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

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

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

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

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

पुस्तकालय

अनुप्रयोग

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

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

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

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

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

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

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

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

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

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

यह भी देखें

संदर्भ

अग्रिम पठन

बाहरी संबंध

Navigation

Wiki tools

Page tools

Other projects

Categories