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

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

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

संचालन

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

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 वर्ग, जो न्यूनतम-प्राथमिकता-क्रम क्रियान्वित करता है।

.नेट की लाइब्रेरी में प�

[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]

[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]

Anonymous

Search