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

Latest revision as of 10:48, 24 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) पुल टाइम),

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

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

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

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

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

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

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

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

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

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

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

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

पुस्तकालय

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

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

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

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

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

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

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

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

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

अनुप्रयोग

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

इस संपत्ति का उपयोग तब किया जाता है जब k_अर्क-मिन निष्पादित किया जाता है, क्योंकि प्रत्येक स्थानीय कतार के सबसे छोटे ${\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_अर्क-मिन ऑपरेशन के बाद परिणाम सेट के शेष अवयव को सीधे स्थानीय क्रम में वापस न ले जाकर प्राथमिकता क्रम में और सुधार किया जा सकता है। यह परिणाम सेट और स्थानीय क्रम के मध्य हर समय आगे और पीछे जाने वाले अवयव को बचाता है।

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

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

Latest revision as of 10:48, 24 July 2023

Contents

संचालन

कार्यान्वयन

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

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

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

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

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

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

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

पुस्तकालय

अनुप्रयोग

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

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

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

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

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

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

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

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

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

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

यह भी देखें

संदर्भ

अग्रिम पठन

बाहरी संबंध

Navigation

Navigation

Wiki tools

Wiki tools

@@ Line 1: / Line 1: @@
 {{short description|Abstract data type in computer science}}
+[[कंप्यूटर विज्ञान]] में, '''प्राथमिकता''' क्रम एक नियमित क्रम या [[स्टैक (सार डेटा प्रकार)|स्टैक]] [[स्टैक (सार डेटा प्रकार)|डेटा]] संरचना के समान एक अमूर्त डेटा-प्रकार है। प्राथमिकता क्रम में प्रत्येक अवयव की एक संबद्ध प्राथमिकता होती है। प्राथमिकता क्रम में, उच्च प्राथमिकता वाले अवयव को लघु प्राथमिकता वाले अवयव से पहले रखा जाता है।और कुछ कार्यान्वयन में, यदि दो अवयव की प्राथमिकता समान है, तो उन्हें उसी क्रम में रखा जाता है जिसमें वे पंक्तिबद्ध थे। अन्य कार्यान्वयन में, समान प्राथमिकता वाले अवयव का क्रम अपरिभाषित है।
+जबकि प्राथमिकता कतारें प्रायः हीप (डेटा संरचना) का उपयोग करके कार्यान्वित की जाती हैं, इस प्रकार से यह अवधारणात्मक रूप से हीप से अलग होती हैं। किन्तु प्राथमिकता क्रम अमूर्त डेटा संरचना है जैसे सूची (अमूर्त डेटा संरचना) या [[सहयोगी सरणी]]; जिस तरह सूची को लिंक की गई सूची के साथ या ऐरे डेटा संरचना के साथ क्रियान्वित किया जा सकता है, प्राथमिकता क्रम के रूप में या किसी अन्य विधि जैसे कि अनियंत्रित सरणी के साथ क्रियान्वित किया जा सकता है।
+==संचालन                                                                                                 ==
-[[कंप्यूटर विज्ञान]] में, '''प्राथमिकता''' क्रम एक नियमित क्रम या [[स्टैक (सार डेटा प्रकार)|स्टैक]] [[स्टैक (सार डेटा प्रकार)|डेटा]] संरचना के समान एक अमूर्त डेटा-प्रकार है। प्राथमिकता क्रम में प्रत्येक अवयव  की एक संबद्ध प्राथमिकता होती है। प्राथमिकता क्रम में, उच्च प्राथमिकता वाले अवयव  को लघु  प्राथमिकता वाले अवयव ों से पहले रखा  जाता है।और  कुछ कार्यान्वयन में, यदि दो अवयव  की प्राथमिकता समान है, तो उन्हें उसी क्रम में रखा  जाता है जिसमें वे पंक्तिबद्ध थे। अन्य कार्यान्वयन में, समान प्राथमिकता वाले अवयव  का क्रम अपरिभाषित है।
-जबकि प्राथमिकता कतारें प्रायः  हीप (डेटा संरचना) का उपयोग करके कार्यान्वित की जाती हैं, इस प्रकार से यह अवधारणात्मक रूप से हीप से अलग होती हैं। किन्तु प्राथमिकता क्रम  अमूर्त डेटा संरचना है जैसे सूची (अमूर्त डेटा संरचना) या [[सहयोगी सरणी]]; जिस तरह  सूची को  लिंक की गई सूची के साथ या  ऐरे डेटा संरचना के साथ क्रियान्वित  किया जा सकता है,  प्राथमिकता क्रम के रूप में  या किसी अन्य विधि जैसे कि  अनियंत्रित सरणी के साथ क्रियान्वित  किया जा सकता है।
-==संचालन ==
 प्राथमिकता क्रम को कम से कम निम्नलिखित परिचालनों का समर्थन करना चाहिए:
-* 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 के रूप में जाना जाता है।
+*: कुछ परंपराएं कम मूल्यों को उच्च प्राथमिकता मानते हुए प्राथमिकताओं के क्रम को प्रतिलोम कर देती हैं, इसलिए इसे 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 30: / Line 26: @@
 === अनुभवहीन कार्यान्वयन ===
-प्राथमिकता क्रम को क्रियान्वित  करने के अनेक  सरल,सामान्यतः अप्रभावी विधि  हैं। वे यह समझने में सहायता  करने के लिए  सादृश्य प्रदान करते हैं कि प्राथमिकता क्रम क्या है।
+प्राथमिकता क्रम को क्रियान्वित करने के अनेक सरल,सामान्यतः अप्रभावी विधि हैं। वे यह समझने में सहायता करने के लिए सादृश्य प्रदान करते हैं कि प्राथमिकता क्रम क्या है।
-इस प्रकार से उदाहरण के लिए, कोई सभी अवयव ों को  अवर्गीकृत सूची (O(1) सम्मिलन टाइम ) में रख सकता है। जब भी सर्वोच्च-प्राथमिकता वाले अवयव  का अनुरोध किया जाए, तो सभी अवयव ों में से सर्वोच्च प्राथमिकता वाले अवयव  को खोजें। (O(n) पुल टाइम),
- 'सम्मिलित करें' (नोड)
- {
-  सूची.जोड़ें(नोड)
- }
- 'खींचना'()
+इस प्रकार से उदाहरण के लिए, कोई सभी अवयव को अवर्गीकृत सूची (O(1) सम्मिलन टाइम ) में रख सकता है। जब भी सर्वोच्च-प्राथमिकता वाले अवयव का अनुरोध किया जाए, तो सभी अवयव में से सर्वोच्च प्राथमिकता वाले अवयव को खोजें। (O(n) पुल टाइम),<syntaxhighlight>
- {
+insert(node)
-  उच्चतम = सूची.get_first_element()
+{
-  सूची में foreach नोड
+    list.append(node)
-  {
+}
-  यदि उच्चतम.प्राथमिकता <नोड.प्राथमिकता
+pull()
-  {
+{
-  उच्चतम = नोड
+    highest = list.get_first_element()
-  }
+    foreach node in list
-  }
+    {
-  सूची.निकालें(उच्चतम)
+        if highest.priority < node.priority
-  उच्चतम वापसी
+        {
-  }
+            highest = node
+        }
+    }
+    list.remove(highest)
+    return highest
+}
+</syntaxhighlight>
-दूसरे स्तिथि  में, अनेक सभी अवयव ों को प्राथमिकता क्रमबद्ध सूची (ओ (एन) प्रविष्टि सॉर्ट समय) में रख सकता है, जब भी उच्चतम प्राथमिकता वाले अवयव  का अनुरोध किया जाता है, तो सूची में पहला वापस किया जा सकता है। (O(1) पुल टाइम )
+दूसरे स्तिथि में, अनेक सभी अवयव को प्राथमिकता क्रमबद्ध सूची (''O''(n) प्रविष्टि सॉर्ट समय) में रख सकता है, जब भी उच्चतम प्राथमिकता वाले अवयव का अनुरोध किया जाता है, तो सूची में पहला वापस किया जा सकता है। (O(1) पुल टाइम )<syntaxhighlight>
- 'सम्मिलित करें' (नोड)
+insert(node)
- {
+{
-  सूची में foreach (सूचकांक, अवयव )।
+    foreach (index, element) in list
-  {
+    {
-  यदि नोड.प्राथमिकता <अवयव .प्राथमिकता
+        if node.priority < element.priority
-  {
+        {
-  list.insert_at_index(नोड,सूचकांक)
+            list.insert_at_index(node,index)
-  तोड़ना
+            break
-  }
+        }
-  }
+    }
- }
+}
+</syntaxhighlight>
-  'खींचना'()
- {
+<syntaxhighlight>
-  उच्चतम = list.get_at_index(list.length-1)
+pull()
-  सूची.निकालें(उच्चतम)
+{
-  उच्चतम वापसी
+    highest = list.get_at_index(list.length-1)
-  }
+    list.remove(highest)
+    return highest
+}
+</syntaxhighlight>
 === सामान्य कार्यान्वयन ===
-इस प्रकार से प्रदर्शन में सुधार करने के लिए, प्राथमिकता कतारें सामान्यतः हीप (डेटा संरचना) पर आधारित होती हैं, जो सम्मिलन और निष्कासन के लिए ओ (लॉग एन) प्रदर्शन देती हैं, और प्रारंभ  में एन अवयव ों के सेट से हीप (डेटा संरचना) बनाने के लिए ओ (एन) देती हैं। मूलभूत  हीप डेटा संरचना के वेरिएंट जैसे [[ युग्मन ढेर |पेयरिंग हीप्स]] या फाइबोनैचि हीप्स कुछ ऑपरेशनों के लिए उत्तम  सीमाएं प्रदान कर सकते हैं।<ref name="CLRS_priority_queue_pp476">{{Introduction to Algorithms|edition=2|chapter=Chapter 20: Fibonacci Heaps|pages=476–497}} तृतीय संस्करण, पृ. 518.</ref>
+इस प्रकार से प्रदर्शन में सुधार करने के लिए, प्राथमिकता कतारें सामान्यतः हीप (डेटा संरचना) पर आधारित होती हैं, जो सम्मिलन और निष्कासन के लिए ''O''(log ''n'') प्रदर्शन देती हैं, और प्रारंभ में एन अवयव के सेट से हीप (डेटा संरचना) बनाने के लिए ''O''(''n'') देती हैं। मूलभूत हीप डेटा संरचना के वेरिएंट जैसे [[ युग्मन ढेर |पेयरिंग हीप्स]] या फाइबोनैचि हीप्स कुछ ऑपरेशनों के लिए उत्तम सीमाएं प्रदान कर सकते हैं।<ref name="CLRS_priority_queue_pp476">{{Introduction to Algorithms|edition=2|chapter=Chapter 20: Fibonacci Heaps|pages=476–497}} तृतीय संस्करण, पृ. 518.</ref>
-किन्तु वैकल्पिक रूप से, जब  [[ स्व-संतुलन द्विआधारी खोज वृक्ष |सेल्फ-बैलेंसिंग बाइनरी सर्च ट्री]] का उपयोग किया जाता है, तब यह सम्मिलन और निष्कासन में भी O(लॉग एन) समय लगता है, चूंकि  अवयव ों के उपस्तिथ  अनुक्रम से ट्री   बनाने में ओ(एन लॉग एन) समय लगता है; यह विशिष्ट है जहां किसी के पास पहले से ही इन डेटा संरचनाओं तक पहुंच हो सकती है, जैसे कि तृतीय-पक्ष या मानक पुस्तकालयों के साथ। अंतरिक्ष-जटिलता के दृष्टिकोण से, लिंक की गई सूची के साथ स्व-संतुलन बाइनरी सर्च ट्री का उपयोग करने से अधिक भंडारण की आवश्यकता होती है, क्योंकि इसके लिए अन्य नोड्स के अतिरिक्त संदर्भों को संग्रहीत करने की आवश्यकता होती है।
+किन्तु वैकल्पिक रूप से, जब [[ स्व-संतुलन द्विआधारी खोज वृक्ष |सेल्फ-बैलेंसिंग बाइनरी सर्च ट्री]] का उपयोग किया जाता है, तब यह सम्मिलन और निष्कासन में भी ''O''(log ''n'') समय लगता है, चूंकि अवयव के उपस्तिथ अनुक्रम से ट्री बनाने में ''O''(''n'' log ''n'') समय लगता है; यह विशिष्ट है जहां किसी के पास पहले से ही इन डेटा संरचनाओं तक पहुंच हो सकती है, जैसे कि तृतीय-पक्ष या मानक पुस्तकालयों के साथ अंतरिक्ष-जटिलता के दृष्टिकोण से, लिंक की गई सूची के साथ स्व-संतुलन बाइनरी सर्च ट्री का उपयोग करने से अधिक संचयन की आवश्यकता होती है, क्योंकि इसके लिए अन्य नोड्स के अतिरिक्त संदर्भों को संग्रहीत करने की आवश्यकता होती है।
-कम्प्यूटेशनल-जटिलता के दृष्टिकोण से, प्राथमिकता कतारें सॉर्टिंग एल्गोरिदम के अनुरूप हैं। नीचे प्राथमिकता क्रम   और सॉर्टिंग एल्गोरिदम की #समानता पर अनुभाग बताता है कि कैसे कुशल सॉर्टिंग एल्गोरिदम कुशल प्राथमिकता कतारें बना सकते हैं।
+कम्प्यूटेशनल-जटिलता के दृष्टिकोण से, प्राथमिकता कतारें सॉर्टिंग एल्गोरिदम के अनुरूप हैं। नीचे प्राथमिकता क्रम और सॉर्टिंग एल्गोरिदम की या समानता पर अनुभाग बताता है कि कैसे कुशल सॉर्टिंग एल्गोरिदम कुशल प्राथमिकता कतारें बना सकते हैं।
 ===विशेषीकृत ढेर===
-अनेक विशिष्ट हीप (डेटा संरचना) [[डेटा संरचनाएं]] हैं जो या तो अतिरिक्त संचालन की आपूर्ति करती हैं या विशिष्ट प्रकार की कुंजियों, विशेष रूप से पूर्णांक कुंजियों के लिए हीप-आधारित कार्यान्वयन को उत्तम  प्रदर्शन करती हैं। मान लीजिए कि संभावित कुंजियों का सेट {1, 2, ..., C} है।
+अनेक विशिष्ट हीप (डेटा संरचना) [[डेटा संरचनाएं]] हैं जो या तो अतिरिक्त संचालन की आपूर्ति करती हैं या विशिष्ट प्रकार की कुंजियों, विशेष रूप से पूर्णांक कुंजियों के लिए हीप-आधारित कार्यान्वयन को उत्तम प्रदर्शन करती हैं। मान लीजिए कि संभावित कुंजियों का सेट {1, 2, ..., C} है।
-* जब केवल सम्मिलित करें, तो फाइंड-मिन और एक्सट्रैक्ट-मिन की आवश्यकता होती है और पूर्णांक प्राथमिकताओं के स्तिथि  में,  [[बाल्टी कतार|बकेट]]  क्रम का निर्माण {{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}}
+* जब केवल सम्मिलित करें, तो फाइंड-मिन और एक्सट्रैक्ट-मिन की आवश्यकता होती है और पूर्णांक प्राथमिकताओं के स्तिथि में, [[बाल्टी कतार|बकेट]] क्रम का निर्माण {{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> और हैशिंग से स्थान को अधिक  लघु  किया जा सकता है।
+* [[वैन एम्डे बोस कदम]] ''O''(log log ''C'') समय में न्यूनतम, अधिकतम, सम्मिलित करें, हटाएं, खोज, निकालने-मिनट, निकालने-अधिकतम, पूर्ववर्ती और उत्तराधिकारी] संचालन का समर्थन करता है, किन्तु इसमें लगभग लघु क्रम के लिए स्थान निवेस होती है ''O''(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) तक कम किया जा सकता है। और सम्मिलन के लिए, यह अधिकतम स्थिर निवेश जोड़ता है, क्योंकि नए सम्मिलित किये गए अवयव की तुलना केवल पहले कैश किए गए न्यूनतम अवयव से की जाती है। रिमूव करने के लिए, इसमें अधिक से अधिक अतिरिक्त झलक निवेस जोड़ी जाती है, जो सामान्यतः डीलीट किये गए निवेस से सस्ती होती है, इसलिए समग्र समय जटिलता महत्वपूर्ण रूप से प्रभावित नहीं होती है।
-[[मोनोटोन प्राथमिकता कतार|मोनोटोन प्राथमिकता]] क्रम विशेष कतारें होती हैं जिन्हें उस स्तिथि  के लिए अनुकूलित किया जाता है जहां कोई भी वस्तु   कभी नहीं इन्सर्ट किया  जाता है जिसकी प्राथमिकता पहले निकाले गए किसी भी वस्तु   की तुलना में कम हो (मिन-हीप के स्तिथि  में)। यह प्रतिबंध प्राथमिकता क्रम   के कई व्यावहारिक अनुप्रयोगों द्वारा पूर्ण  किया जाता है।
+[[मोनोटोन प्राथमिकता कतार|मोनोटोन प्राथमिकता]] क्रम विशेष कतारें होती हैं जिन्हें उस स्तिथि के लिए अनुकूलित किया जाता है जहां कोई भी वस्तु कभी नहीं इन्सर्ट किया जाता है जिसकी प्राथमिकता पहले निकाले गए किसी भी वस्तु की तुलना में कम हो (मिन-हीप के स्तिथि में)। यह प्रतिबंध प्राथमिकता क्रम के कई व्यावहारिक अनुप्रयोगों द्वारा पूर्ण किया जाता है।
 ===चलने के समय का सारांश===
 {{Heap Running Times}}
-== प्राथमिकता क्रम   और सॉर्टिंग एल्गोरिदम की समानता ==
+== प्राथमिकता क्रम और सॉर्टिंग एल्गोरिदम की समानता ==
 === सॉर्ट करने के लिए प्राथमिकता क्रम का उपयोग करना ===
-इस प्रकार से प्राथमिकता क्रम   के [[परिचालन शब्दार्थ]] स्वाभाविक रूप से  सोर्टिंग  विधि का सुझाव देते हैं: अर्थात क्रमबद्ध किए जाने वाले सभी अवयव  को प्राथमिकता क्रम में रखे , और क्रमिक रूप से उन्हें रिमूव कर  दें; वे क्रमबद्ध विधि  से सामने आएंगे यह वास्तव में कई [[छँटाई एल्गोरिथ्म|सोर्टिंग  एल्गोरिथ्म]] द्वारा उपयोग की जाने वाली प्रक्रिया है,  इस प्रकार से  प्राथमिकता क्रम द्वारा प्रदान की गई अमूर्तता (कंप्यूटर विज्ञान) की लेयर हटा दी जाती है। यह सॉर्टिंग विधि निम्नलिखित सॉर्टिंग एल्गोरिदम के समान  है:
+इस प्रकार से प्राथमिकता क्रम के [[परिचालन शब्दार्थ]] स्वाभाविक रूप से सोर्टिंग विधि का सुझाव देते हैं: अर्थात क्रमबद्ध किए जाने वाले सभी अवयव को प्राथमिकता क्रम में रखे, और क्रमिक रूप से उन्हें रिमूव कर दें; वे क्रमबद्ध विधि से सामने आएंगे यह वास्तव में कई [[छँटाई एल्गोरिथ्म|सोर्टिंग एल्गोरिथ्म]] द्वारा उपयोग की जाने वाली प्रक्रिया है, इस प्रकार से प्राथमिकता क्रम द्वारा प्रदान की गई अमूर्तता (कंप्यूटर विज्ञान) की लेयर हटा दी जाती है। यह सॉर्टिंग विधि निम्नलिखित सॉर्टिंग एल्गोरिदम के समान है:
 {|class="wikitable sortable"
@@ Line 142: / Line 142: @@
 === प्राथमिकता क्रम बनाने के लिए सॉर्टिंग एल्गोरिदम का उपयोग करना ===
-प्राथमिकता क्रम को क्रियान्वित  करने के लिए सॉर्टिंग एल्गोरिदम का भी उपयोग किया जा सकता है। विशेष रूप से, थोरुप कहते हैं:<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>
-हम प्राथमिकता क्रम   से सॉर्टिंग तक  सामान्य नियतात्मक रैखिक स्थान में कमी प्रस्तुत करते हैं, जिसका अर्थ है कि यदि हम प्रति कुंजी एस (एन) समय में एन कुंजी को सॉर्ट कर सकते हैं, तो ओ (एस (एन)) में हटाने और डालने का समर्थन करने वाली  प्राथमिकता क्रम है। निरंतर समय में समय और खोज-मिनट आदि ।
+हम प्राथमिकता क्रम से सॉर्टिंग तक सामान्य नियतात्मक रैखिक स्थान में कमी प्रस्तुत करते हैं, जिसका अर्थ है कि यदि हम प्रति कुंजी ''S''(''n'') समय में एन कुंजी को सॉर्ट कर सकते हैं, तो ''O''(''S''(''n'')) में हटाने और डालने का समर्थन करने वाली प्राथमिकता क्रम है। निरंतर समय में समय और खोज-मिनट आदि ।
-अर्थात्, यदि कोई सॉर्टिंग एल्गोरिदम है जो प्रति कुंजी ओ(एस) समय में सॉर्ट कर सकता है, जहां ''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) पुलिंग और ओ(लॉग एन) सम्मिलन के साथ प्राथमिकता क्रम बना सकता है।
+अर्थात्, यदि कोई सॉर्टिंग एल्गोरिदम है जो प्रति कुंजी ''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'') समय है। उदाहरण के लिए, यदि किसी के पास ''O''(''n'' log ''n'') सॉर्ट एल्गोरिदम है, तो वह ''O''(1) पुलिंग और ''O''( log ''n'') सम्मिलन के साथ प्राथमिकता क्रम बना सकता है।
 == पुस्तकालय ==
-प्राथमिकता क्रम को प्रायः   [[कंटेनर (सार डेटा प्रकार)|कंटेनर (सार डेटा संरचना)]] माना जाता है।
+प्राथमिकता क्रम को प्रायः [[कंटेनर (सार डेटा प्रकार)|कंटेनर (सार डेटा संरचना)]] माना जाता है।
-[[मानक टेम्पलेट लाइब्रेरी]] (एसटीएल), और [[C++|सी ++]] 1998 मानक, [https://en.cppreference.com/w/cpp/container/priority_queue std::priority_queue] को एसटीएल [[कंटेनर (प्रोग्रामिंग)]] [[एडाप्टर (प्रोग्रामिंग)]] में से  के रूप में निर्दिष्ट करता है ) [[टेम्पलेट (प्रोग्रामिंग)]]एस। चूंकि , यह निर्दिष्ट नहीं करता है कि समान प्राथमिकता वाले दो अवयव ों को कैसे सेवित करना  चाहिए, और वास्तव में, सामान्य कार्यान्वयन उन्हें क्रम में उनके क्रम के अनुसार वापस नहीं करता है । यह  अधिकतम-प्राथमिकता-क्रम क्रियान्वित  करता है, और इसमें तीन पैरामीटर होते हैं: सॉर्टिंग के लिए  तुलनात्मक ऑब्जेक्ट जैसे कि फ़ंक्शन ऑब्जेक्ट (यदि अनिर्दिष्ट है तो लघु <T> पर डिफ़ॉल्ट), डेटा संरचनाओं को संग्रहीत करने के लिए अंतर्निहित कंटेनर (एसटीडी::वेक्टर पर डिफ़ॉल्ट) <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] मॉड्यूल  सूची के शीर्ष पर  बाइनरी मिन-हीप क्रियान्वित  करता है।
+पायथन का [https://docs.python.org/library/heapq.html heapq] मॉड्यूल सूची के शीर्ष पर बाइनरी मिन-हीप क्रियान्वित करता है।
-[[जावा (प्रोग्रामिंग भाषा)]] की लाइब्रेरी में  सम्मिलित  है {{Javadoc:SE|java/util|PriorityQueue}} वर्ग, जो न्यूनतम-प्राथमिकता-क्रम क्रियान्वित  करता है।
+[[जावा (प्रोग्रामिंग भाषा)]] की लाइब्रेरी में सम्मिलित है {{Javadoc:SE|java/util|PriorityQueue}} वर्ग, जो न्यूनतम-प्राथमिकता-क्रम क्रियान्वित करता है।
-.नेट  की लाइब्रेरी में  [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 प्राथमिकता क्यू] वर्ग सम्मिलित  है, जो अधिकतम-प्राथमिकता-क्यू क्रियान्वित  करता है।
+[[स्काला (प्रोग्रामिंग भाषा)]] की लाइब्रेरी में [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] सम्मिलित है।
-एप्पल के [[कोर फाउंडेशन]] फ्रेमवर्क में  [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 172: / Line 172: @@
 === बैंडविड्थ प्रबंधन ===
-[[ संगणक संजाल | '''संगणक संजाल''']] '''[[राउटर (कंप्यूटिंग)]]''' से ट्रांसमिशन लाइन पर [[बैंडविड्थ (कंप्यूटिंग)]] जैसे सीमित संसाधनों को प्रबंधित करने के लिए प्राथमिकता क्रम का उपयोग किया जा सकता है। अपर्याप्त बैंडविड्थ के कारण आउटगोइंग [[ट्रैफ़िक]] क्रम में लगने की स्थिति में, आगमन पर ट्रैफ़िक को सर्वोच्च प्राथमिकता वाली क्रम से भेजने के लिए अन्य सभी क्रम   को रोका जा सकता है। यह सुनिश्चित करता है कि प्राथमिकता वाले ट्रैफ़िक (जैसे कि वास्तविक समय ट्रैफ़िक, उदाहरण के लिए [[ इंटरनेट प्रोटोकॉल पर आवाज़ |वीओआईपी]] कनेक्शन की [[वास्तविक समय परिवहन प्रोटोकॉल|आरटीपी]] स्ट्रीम) को लघु से ;लघु देरी के साथ अग्रेषित किया जाता है और क्रम के अधिकतम तक पहुंचने के कारण अस्वीकार होने की कम से कम संभावना होती है। इस प्रकार से  सर्वोच्च प्राथमिकता क्रम रिक्त  होने पर अन्य सभी ट्रैफ़िक को संभाला जा सकता है। उपयोग किया जाने वाले   अन्य  विधि से   उच्च प्राथमिकता वाली क्रम   के असंगत रूप से अधिक ट्रैफ़िक भेजना है।
+[[ संगणक संजाल | '''संगणक संजाल''']] '''[[राउटर (कंप्यूटिंग)]]''' से ट्रांसमिशन लाइन पर [[बैंडविड्थ (कंप्यूटिंग)]] जैसे सीमित संसाधनों को प्रबंधित करने के लिए प्राथमिकता क्रम का उपयोग किया जा सकता है। अपर्याप्त बैंडविड्थ के कारण आउटगोइंग [[ट्रैफ़िक]] क्रम में लगने की स्थिति में, आगमन पर ट्रैफ़िक को सर्वोच्च प्राथमिकता वाली क्रम से भेजने के लिए अन्य सभी क्रम को रोका जा सकता है। यह सुनिश्चित करता है कि प्राथमिकता वाले ट्रैफ़िक (जैसे कि वास्तविक समय ट्रैफ़िक, उदाहरण के लिए [[ इंटरनेट प्रोटोकॉल पर आवाज़ |वीओआईपी]] कनेक्शन की [[वास्तविक समय परिवहन प्रोटोकॉल|आरटीपी]] स्ट्रीम) को लघु से ;लघु देरी के साथ अग्रेषित किया जाता है और क्रम के अधिकतम तक पहुंचने के कारण अस्वीकार होने की कम से कम संभावना होती है। इस प्रकार से सर्वोच्च प्राथमिकता क्रम रिक्त होने पर अन्य सभी ट्रैफ़िक को संभाला जा सकता है। उपयोग किया जाने वाले अन्य विधि से उच्च प्राथमिकता वाली क्रम के असंगत रूप से अधिक ट्रैफ़िक भेजना है।
-इस प्रकार से स्थानीय क्षेत्र नेटवर्क के लिए कई आधुनिक प्रोटोकॉल में [[ मीडिया अभिगम नियंत्रण |मीडिया एक्सेस कंट्रोल  ]] (मैक) उप-परत पर प्राथमिकता क्रम   की अवधारणा भी सम्मिलित  है जिससे यह सुनिश्चित किया जा सके कि उच्च-प्राथमिकता वाले एप्लिकेशन (जैसे [[वीओआईपी]] या [[आईपीटीवी]]) अन्य अनुप्रयोगों की तुलना में कम विलंबता का अनुभव करते हैं जिन्हें इसके साथ सेवित  जा सकता है। [[सर्वोत्तम प्रयास वाली सेवा|बेस्ट-एफ्फ़ोर्ट सर्विस]] के अतिरिक्त  उदाहरणों में आईईईई 802.11ई  (आईईईई 802.11 में  संशोधन जो  [[सेवा की गुणवत्ता|क्वालिटी ऑफ  सर्विस]] प्रदान करता है) और आईटीयू-टी जी.एच.एन (उपस्तिथ  होम वायरिंग (पावर लाइन संचार, फोन लाइन और कोएक्स पर ईथरनेट) का उपयोग करके हाई-स्पीड [[लोकल एरिया नेटवर्क]] के लिए  मानक) सम्मिलित  हैं। .
+इस प्रकार से स्थानीय क्षेत्र नेटवर्क के लिए कई आधुनिक प्रोटोकॉल में [[ मीडिया अभिगम नियंत्रण |मीडिया एक्सेस कंट्रोल  ]] (मैक) उप-परत पर प्राथमिकता क्रम की अवधारणा भी सम्मिलित है जिससे यह सुनिश्चित किया जा सकता है कि उच्च-प्राथमिकता वाले एप्लिकेशन (जैसे [[वीओआईपी]] या [[आईपीटीवी]]) अन्य अनुप्रयोगों की तुलना में कम विलंबता का अनुभव करते हैं जिन्हें इसके साथ सेवित जा सकता है। [[सर्वोत्तम प्रयास वाली सेवा|बेस्ट-एफ्फ़ोर्ट सर्विस]] के अतिरिक्त उदाहरणों में आईईईई 802.11ई (आईईईई 802.11 में संशोधन जो [[सेवा की गुणवत्ता|क्वालिटी ऑफ  सर्विस]] प्रदान करता है) और आईटीयू-टी जी.एच.एन (उपस्तिथ होम वायरिंग (पावर लाइन संचार, फोन लाइन और कोएक्स पर ईथरनेट) का उपयोग करके हाई-स्पीड [[लोकल एरिया नेटवर्क]] के लिए मानक) सम्मिलित हैं। .
-सामान्यतः   सीमा (पोलिसर) उस बैंडविड्थ को सीमित करने के लिए निर्धारित की जाती है जो उच्चतम प्राथमिकता क्रम से ट्रैफ़िक ले सकता है, जिससे उच्च प्राथमिकता वाले पैकेटों को अन्य सभी ट्रैफ़िक को रोकने से रोका जा सकता है । यह सीमासामान्यतः सिस्को सिस्टम्स, इंक. [[ प्रबंधक को कॉल करो |प्रबंधक को कॉल करो]] जैसे उच्च स्तरीय नियंत्रण उदाहरणों के कारण कभी नहीं पहुंचती है, जिसे प्रोग्राम की गई बैंडविड्थ सीमा से अधिक होने वाली कॉल को रोकने के लिए प्रोग्राम किया जा सकता है।
+सामान्यतः सीमा (पोलिसर) उस बैंडविड्थ को सीमित करने के लिए निर्धारित की जाती है जो उच्चतम प्राथमिकता क्रम से ट्रैफ़िक ले सकता है, जिससे उच्च प्राथमिकता वाले पैकेटों को अन्य सभी ट्रैफ़िक को रोकने से रोका जा सकता है । यह सीमासामान्यतः सिस्को सिस्टम्स, इंक. [[ प्रबंधक को कॉल करो |प्रबंधक को कॉल करो]] जैसे उच्च स्तरीय नियंत्रण उदाहरणों के कारण कभी नहीं पहुंचती है, जिसे प्रोग्राम की गई बैंडविड्थ सीमा से अधिक होने वाली कॉल को रोकने के लिए प्रोग्राम किया जा सकता है।
 === [[असतत घटना अनुकरण]] ===
-प्राथमिकता क्रम का  अन्य उपयोग घटनाओं को  अलग घटना सिमुलेशन में प्रबंधित करना है। घटनाओं को प्राथमिकता के रूप में उपयोग किए गए उनके सिमुलेशन समय के साथ क्रम में जोड़ा जाता है। सिमुलेशन का निष्पादन बार-बार क्रम के शीर्ष को खींचकर और उस पर घटना को निष्पादित करके आगे बढ़ता है।
+प्राथमिकता क्रम का अन्य उपयोग घटनाओं को अलग घटना सिमुलेशन में प्रबंधित करना है। घटनाओं को प्राथमिकता के रूप में उपयोग किए गए उनके सिमुलेशन समय के साथ क्रम में जोड़ा जाता है। सिमुलेशन का निष्पादन बार-बार क्रम के शीर्ष को खींचकर और उस पर घटना को निष्पादित करके आगे बढ़ता है।
 यह भी देखें: [[शेड्यूलिंग (कंप्यूटिंग)]], [[कतारबद्ध सिद्धांत]]
@@ Line 185: / Line 185: @@
 === दिज्क्स्ट्रा का एल्गोरिथ्म ===
-जब ग्राफ़ को आसन्न सूची या मैट्रिक्स के रूप में संग्रहीत किया जाता है, तो दिज्क्स्ट्रा के एल्गोरिदम को कार्यान्वित करते समय न्यूनतम कुशलता से निकालने के लिए प्राथमिकता क्रम का उपयोग किया जा सकता है, चूंकि  किसी को प्राथमिकता क्रम में किसी विशेष शीर्ष की प्राथमिकता को कुशलतापूर्वक परिवर्तन  की क्षमता की आवश्यकता होती है।
+जब ग्राफ़ को आसन्न सूची या आव्यूह के रूप में संग्रहीत किया जाता है, तो दिज्क्स्ट्रा के एल्गोरिदम को कार्यान्वित करते समय न्यूनतम कुशलता से निकालने के लिए प्राथमिकता क्रम का उपयोग किया जा सकता है, चूंकि किसी को प्राथमिकता क्रम में किसी विशेष शीर्ष की प्राथमिकता को कुशलतापूर्वक परिवर्तन की क्षमता की आवश्यकता होती है।
-यदि इसके अतरिक्त , ग्राफ़ को नोड ऑब्जेक्ट के रूप में संग्रहीत किया जाता है, और प्राथमिकता-नोड जोड़े को हीप में डाला जाता है, तो किसी विशेष शीर्ष की प्राथमिकता को परिवर्तित करना  आवश्यक नहीं है यदि कोई विज़िट किए गए नोड्स को ट्रैक करता है। तत्पश्चात  बार नोड पर जाने के अतिरिक्त , यदि यह दोबारा हीप में आता है (पहले इसके साथ कम प्राथमिकता संख्या जुड़ी हुई थी), तो इसे पॉप-ऑफ कर दिया जाता है और अनदेखा कर दिया जाता है।
+यदि इसके अतरिक्त ग्राफ़ को नोड ऑब्जेक्ट के रूप में संग्रहीत किया जाता है, और प्राथमिकता-नोड जोड़े को हीप में डाला जाता है, तो किसी विशेष शीर्ष की प्राथमिकता को परिवर्तित करना आवश्यक नहीं है यदि कोई विज़िट किए गए नोड्स को ट्रैक करता है। तत्पश्चात बार नोड पर जाने के अतिरिक्त , यदि यह दोबारा हीप में आता है (पहले इसके साथ कम प्राथमिकता संख्या जुड़ी हुई थी), तो इसे पॉप-ऑफ कर दिया जाता है और अनदेखा कर दिया जाता है।
 === [[हफ़मैन कोडिंग]] ===
-इस प्रकार से हफ़मैन कोडिंग के लिए व्यक्ति को दो सामान्य  लघु  आवृत्ति वाले ट्री  को बार-बार प्राप्त करने की आवश्यकता होती है।  प्राथमिकता क्रम हफ़मैन कोडिंग की विधि  है।
+इस प्रकार से हफ़मैन कोडिंग के लिए व्यक्ति को दो सामान्य लघु आवृत्ति वाले ट्री को बार-बार प्राप्त करने की आवश्यकता होती है। प्राथमिकता क्रम हफ़मैन कोडिंग की विधि है।
 === [[सर्वोत्तम-प्रथम खोज]] एल्गोरिदम ===
-सर्वश्रेष्ठ-प्रथम खोज एल्गोरिदम, ए * खोज एल्गोरिदम की तरह,  [[भारित ग्राफ]] के दो वर्टेक्स (ग्राफ़ सिद्धांत) या [[नोड (ग्राफ़ सिद्धांत)]] के मध्य  अधिक  लघु  रास्ता ढूंढते हैं, इस प्रकार से  आशाजनक मार्गों को पहले जांचते  हैं। अज्ञात मार्गों पर द्रष्टि  रखने के लिए प्राथमिकता क्रम (जिसे फ्रिंज भी कहा जाता है) का उपयोग किया जाता है; जिसके लिए कुल पथ लंबाई का अनुमान (ए* के स्तिथि  में निचली सीमा) अधिक लघु  है, उसे सर्वोच्च प्राथमिकता दी जाती है। यदि मेमोरी सीमाएं सर्वोत्तम-प्रथम खोज को अव्यवहारिक बनाती हैं, तो कम-प्राथमिकता वाली वस्तुओं को हटाने की अनुमति देने के लिए [[डबल-एंडेड प्राथमिकता कतार|डबल-एंडेड प्राथमिकता]] क्रम के साथ [[एसएमए*]] एल्गोरिदम जैसे वेरिएंट का उपयोग किया जा सकता है।
+सर्वश्रेष्ठ-प्रथम खोज एल्गोरिदम, A* खोज एल्गोरिदम की तरह, [[भारित ग्राफ]] के दो वर्टेक्स (ग्राफ़ सिद्धांत) या [[नोड (ग्राफ़ सिद्धांत)]] के मध्य अधिक लघु रास्ता खोजते हैं, इस प्रकार से आशाजनक मार्गों को पहले जांचते हैं। अज्ञात मार्गों पर द्रष्टि रखने के लिए प्राथमिकता क्रम (जिसे फ्रिंज भी कहा जाता है) का उपयोग किया जाता है; जिसके लिए कुल पथ लंबाई का अनुमान (A* के स्तिथि में निचली सीमा) अधिक लघु है, उसे सर्वोच्च प्राथमिकता दी जाती है। यदि मेमोरी सीमाएं सर्वोत्तम-प्रथम खोज को अव्यवहारिक बनाती हैं, तो कम-प्राथमिकता वाली वस्तुओं को हटाने की अनुमति देने के लिए [[डबल-एंडेड प्राथमिकता कतार|डबल-एंडेड प्राथमिकता]] क्रम के साथ [[एसएमए*]] एल्गोरिदम जैसे वेरिएंट का उपयोग किया जा सकता है।
 === [[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 214: / Line 214: @@
 </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 अब पहुंच योग्य नहीं है।]]प्राथमिकता क्रम तक समवर्ती पहुंच को समवर्ती पढ़ें, समवर्ती लिखें (सीआरसीडब्ल्यू) पीआरएएम  मॉडल पर क्रियान्वित  किया जा सकता है। निम्नलिखित में प्राथमिकता क्रम को  स्किप सूची के रूप में क्रियान्वित  किया गया है।<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/> यह संकटजनक  है कि नया नोड स्किप सूची में जोड़ा गया है, फिर भी यह अब पहुंच योग्य नहीं है.
+यदि प्राथमिकता क्रम तक समवर्ती पहुंच की अनुमति दी जाती है, तो दो प्रक्रियाओं के मध्य टकराव उत्पन्न हो सकता है। उदाहरण के लिए, यदि प्रक्रिया नया नोड डालने का प्रयास कर रही है, किन्तु उसी समय अन्य प्रक्रिया उस नोड के पूर्ववर्ती को हटाने वाली है तो विरोध उत्पन्न होता है।<ref name = skiplist/> यह संकटजनक है कि नया नोड स्किप सूची में जोड़ा गया है, फिर भी यह अब पहुंच योग्य नहीं है.
-=== के-अवयव  संचालन ===
+=== के-अवयव संचालन ===
-इस सेटिंग में, प्राथमिकता क्रम पर संचालन को  बैच के लिए सामान्यीकृत किया जाता है <math display="inline">k</math> अवयव .
+इस सेटिंग में, प्राथमिकता क्रम पर संचालन को बैच के लिए सामान्यीकृत किया जाता है <math display="inline">k</math> अवयव .
-उदाहरण के लिए, k_अर्क-मिन  हटा देता है <math display="inline">k</math> प्राथमिकता क्रम के सबसे छोटे अवयव  और उन्हें लौटाता है।
+उदाहरण के लिए, k_अर्क-मिन हटा देता है <math display="inline">k</math> प्राथमिकता क्रम के सबसे छोटे अवयव और उन्हें लौटाता है।
-[[समानांतर प्रोग्रामिंग मॉडल]] | साझा-मेमोरी सेटिंग में, समानांतर प्राथमिकता क्रम को समानांतर [[बाइनरी खोज पेड़|बाइनरी खोज ट्री]]   और [[जॉइन-आधारित ट्री एल्गोरिदम]] का उपयोग करके आसानी से कार्यान्वित किया जा सकता है। विशेष रूप से, k _अर्क-न्यूनतम बाइनरी सर्च ट्री पर  विभाजन से मेल खाता है <math display="inline">O(\log n)</math> निवेस  और  ट्री   की उत्पाद जिसमें सम्मिलित  है <math display="inline">k</math> अधिक  छोटे अवयव . k_इन्सर्ट  करना मूल प्राथमिकता क्रम और सम्मिलन के बैच के संघ द्वारा क्रियान्वित  किया जा सकता है। यदि बैच पहले से ही कुंजी द्वारा क्रमबद्ध है, तो k इन्सर्ट  करना है <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_कमी-कुंजी को पहले अंतर और फिर यूनियन क्रियान्वित  करके किया जा सकता है, जो पहले अवयव   को हटाता है और फिर उन्हें अद्यतन कुंजी के साथ वापस सम्मिलित करता है। ये सभी ऑपरेशन अत्यधिक समानांतर हैं, और सैद्धांतिक और व्यावहारिक दक्षता संबंधित शोध पत्रों में पाई जा सकती है।<ref name="join-based">{{citation
+इस सेटिंग में, प्राथमिकता कतार पर संचालन को <math display="inline">k</math> तत्वों के एक बैच के लिए सामान्यीकृत किया जाता है। उदाहरण के लिए, k_एक्सट्रेक्ट-मिन प्राथमिकता कतार के <math display="inline">k</math> सबसे छोटे तत्वों को हटा देता है और उन्हें वापस कर देता है।
+[[समानांतर प्रोग्रामिंग मॉडल]] या साझा-मेमोरी सेटिंग में, समानांतर प्राथमिकता क्रम को समानांतर [[बाइनरी खोज पेड़|बाइनरी खोज ट्री]] और [[जॉइन-आधारित ट्री एल्गोरिदम]] का उपयोग करके आसानी से कार्यान्वित किया जा सकता है। विशेष रूप से, k _अर्क-न्यूनतम बाइनरी सर्च ट्री पर विभाजन से मेल खाता है <math display="inline">O(\log n)</math> निवेस और ट्री की उत्पाद जिसमें सम्मिलित है <math display="inline">k</math> अधिक छोटे अवयव . k_इन्सर्ट करना मूल प्राथमिकता क्रम और सम्मिलन के बैच के संघ द्वारा क्रियान्वित किया जा सकता है। यदि बैच पहले से ही कुंजी द्वारा क्रमबद्ध है, तो k इन्सर्ट करना है <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_कमी-कुंजी को पहले अंतर और फिर यूनियन क्रियान्वित करके किया जा सकता है, जो पहले अवयव को हटाता है और फिर उन्हें अद्यतन कुंजी के साथ वापस सम्मिलित करता है। ये सभी ऑपरेशन अत्यधिक समानांतर हैं, और सैद्धांतिक और व्यावहारिक दक्षता संबंधित शोध पत्रों में पाई जा सकती है।<ref name="join-based">{{citation
   | last1 = Blelloch | first1 = Guy E.
   | last2 = Ferizovic | first2 = Daniel
@@ Line 252: / Line 254: @@
   | year = 2018}}</ref>
-इस खंड का शेष भाग वितरित मेमोरी पर क्रम-आधारित एल्गोरिदम पर चर्चा करता है। हम मानते हैं कि प्रत्येक प्रोसेसर की अपनी स्थानीय मेमोरी और  स्थानीय (अनुक्रमिक) प्राथमिकता क्रम होती है। वैश्विक (समानांतर) प्राथमिकता क्रम के अवयव  सभी प्रोसेसरों में वितरित किए जाते हैं।
+इस खंड का शेष भाग वितरित मेमोरी पर क्रम-आधारित एल्गोरिदम पर चर्चा करता है। हम मानते हैं कि प्रत्येक प्रोसेसर की अपनी स्थानीय मेमोरी और स्थानीय (अनुक्रमिक) प्राथमिकता क्रम होती है। वैश्विक (समानांतर) प्राथमिकता क्रम के अवयव सभी प्रोसेसरों में वितरित किए जाते हैं।
-[[File:BulkDeletionPQ.svg|thumb|k_अर्क-मिन को तीन प्रोसेसर के साथ प्राथमिकता क्रम पर निष्पादित किया जाता है। हरे अवयव  लौटाए जाते हैं और प्राथमिकता क्रम से हटा दिए जाते हैं।]]k_इन्सर्ट ऑपरेशन प्रोसेसर को अवयव को समान रूप से यादृच्छिक रूप से निर्दिष्ट करता है जो अवयव  को उनकी स्थानीय क्रम   में सम्मिलित करता है। ध्यान दें कि एकल अवयव  अभी भी क्रम में डाले जा सकते हैं। इस रणनीति का उपयोग करते हुए वैश्विक सबसे छोटे अवयव  उच्च संभावना वाले प्रत्येक प्रोसेसर के स्थानीय सबसे छोटे अवयव के संघ में हैं। इस प्रकार प्रत्येक प्रोसेसर वैश्विक प्राथमिकता क्रम का  प्रतिनिधि हिस्सा रखता है।
+[[File:BulkDeletionPQ.svg|thumb|k_अर्क-मिन को तीन प्रोसेसर के साथ प्राथमिकता क्रम पर निष्पादित किया जाता है। हरे अवयव लौटाए जाते हैं और प्राथमिकता क्रम से हटा दिए जाते हैं।]]k_इन्सर्ट ऑपरेशन प्रोसेसर को अवयव को समान रूप से यादृच्छिक रूप से निर्दिष्ट करता है जो अवयव को उनकी स्थानीय क्रम में सम्मिलित करता है। ध्यान दें कि एकल अवयव अभी भी क्रम में डाले जा सकते हैं। इस रणनीति का उपयोग करते हुए वैश्विक सबसे छोटे अवयव उच्च संभावना वाले प्रत्येक प्रोसेसर के स्थानीय सबसे छोटे अवयव के संघ में हैं। इस प्रकार प्रत्येक प्रोसेसर वैश्विक प्राथमिकता क्रम का प्रतिनिधि भाग रखता है।
-इस संपत्ति का उपयोग तब किया जाता है जब k_अर्क-मिन को सबसे छोटे के रूप में निष्पादित किया जाता है <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_निकालें-मिनट का चलने का समय अपेक्षित है <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_अर्क-मिन निष्पादित किया जाता है, क्योंकि प्रत्येक स्थानीय कतार के सबसे छोटे <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_अर्क-मिन का चलने का समय अपेक्षित है <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_अर्क-मिन  ऑपरेशन के बाद परिणाम सेट के शेष अवयव  को सीधे स्थानीय क्रम में वापस न ले जाकर प्राथमिकता क्रम में और सुधार किया जा सकता है। यह परिणाम सेट और स्थानीय क्रम   के मध्य  हर समय आगे और पीछे जाने वाले अवयव को बचाता है।
+k_अर्क-मिन ऑपरेशन के बाद परिणाम सेट के शेष अवयव को सीधे स्थानीय क्रम में वापस न ले जाकर प्राथमिकता क्रम में और सुधार किया जा सकता है। यह परिणाम सेट और स्थानीय क्रम के मध्य हर समय आगे और पीछे जाने वाले अवयव को बचाता है।
-इसके अतिरिक्त  अवयव  को हटाकर अधिक  तीव्र लाई जा सकती है। किन्तु  सभी एल्गोरिदम इस प्रकार की प्राथमिकता क्रम का उपयोग नहीं कर सकते हैं। उदाहरण के लिए डिज्क्स्ट्रा का एल्गोरिदम  साथ कई नोड्स पर कार्य  नहीं कर सकता है। एल्गोरिथ्म प्राथमिकता क्रम से सबसे छोटी दूरी वाले नोड को लेता है और उसके सभी निकटतम  नोड्स के लिए नई दूरी की गणना करता है। यदि  आप निकालेंगे <math display="inline">k</math> नोड्स,  नोड पर कार्य  करने से दूसरे <math display="inline">k</math> नोड की दूरी परिवर्तित कर  सकती है  नोड्स. इसलिए के-एलिमेंट ऑपरेशंस का उपयोग करने से डिज्क्स्ट्रा के एल्गोरिदम की लेबल सेटिंग संपत्ति नष्ट हो जाती है।
+इसके अतिरिक्त अवयव को हटाकर अधिक तीव्र लाई जा सकती है। किन्तु सभी एल्गोरिदम इस प्रकार की प्राथमिकता क्रम का उपयोग नहीं कर सकते हैं। उदाहरण के लिए डिज्क्स्ट्रा का एल्गोरिदम साथ कई नोड्स पर कार्य नहीं कर सकता है। एल्गोरिथ्म प्राथमिकता क्रम से सबसे छोटी दूरी वाले नोड को लेता है और उसके सभी निकटतम नोड्स के लिए नई दूरी की गणना करता है। यदि आप निकालेंगे <math display="inline">k</math> नोड्स, नोड पर कार्य करने से दूसरे <math display="inline">k</math> नोड की दूरी परिवर्तित कर सकती है नोड्स. इसलिए के-एलिमेंट ऑपरेशंस का उपयोग करने से डिज्क्स्ट्रा के एल्गोरिदम की लेबल सेटिंग संपत्ति नष्ट हो जाती है।
 == यह भी देखें ==
@@ Line 268: / Line 269: @@
 * [[बैच कतार|बैच क्रम]]
 * कमांड [[बैच कतार|क्रम]]
-* [[कार्य अनुसूचक|जॉब  शेड्यूलर]]
+* [[कार्य अनुसूचक|जॉब शेड्यूलर]]
 == संदर्भ ==
@@ Line 287: / Line 288: @@
 {{Data structures}}
-[[Category: प्राथमिकता कतारें| प्राथमिकता कतारें]] [[Category: सार डेटा प्रकार]]
-[[Category: Machine Translated Page]]
+[[Category:CS1 Deutsch-language sources (de)]]
+[[Category:CS1 English-language sources (en)]]
+[[Category:Collapse templates]]
 [[Category:Created On 07/07/2023]]
+[[Category:Lua-based templates]]
+[[Category:Machine Translated Page]]
+[[Category:Navigational boxes| ]]
+[[Category:Navigational boxes without horizontal lists]]
+[[Category:Pages with script errors]]
+[[Category:Pages with syntax highlighting errors]]
+[[Category:Sidebars with styles needing conversion]]
+[[Category:Template documentation pages|Documentation/doc]]
+[[Category:Templates Vigyan Ready]]
+[[Category:Templates generating microformats]]
+[[Category:Templates that add a tracking category]]
+[[Category:Templates that are not mobile friendly]]
+[[Category:Templates that generate short descriptions]]
+[[Category:Templates using TemplateData]]
+[[Category:Wikipedia metatemplates]]
+[[Category:प्राथमिकता कतारें| प्राथमिकता कतारें]]
+[[Category:सार डेटा प्रकार]]

Anonymous

Search

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

Latest revision as of 10:48, 24 July 2023

संचालन

कार्यान्वयन

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

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

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

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

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

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

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

पुस्तकालय

अनुप्रयोग

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

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

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

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

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

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

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

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

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

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

यह भी देखें

संदर्भ

अग्रिम पठन

बाहरी संबंध

Navigation

Wiki tools

Page tools

Other projects

Categories