हीप (डेटा संरचना)

एक बाइनरी ट्री मैक्स-हीप का उदाहरण जिसमें नोड कुंजियाँ 1 और 100 के बीच पूर्णांक हैं

कंप्यूटर विज्ञान में, हीप एक विशेष ट्री-आधारित डेटा संरचना है जो हीप गुण को संतुष्ट करती है: अधिकतम हीप में, किसी दिए गए नोड (कंप्यूटर विज्ञान) C के लिए, यदि P C का मूल नोड है, तो P की कुंजी (मान) C की कुंजी से अधिक या उसके समान है। एक मिनट के हीप में, P की कुंजी C की कुंजी से कम या उसके समान है।^[1] हीप के "शीर्ष" पर स्थित नोड (बिना पैरेंट्स के) को रूट नोड कहा जाता है।

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

हीप का सामान्य कार्यान्वयन बाइनरी हीप है, जिसमें ट्री लगभग पूर्ण^[2] बाइनरी ट्री (आंकड़ा देखें) है। हीप डेटा संरचना, विशेष रूप से बाइनरी हीप, 1964 में जे.डब्ल्यू.जे विलियम्स द्वारा हीप्सॉर्ट सॉर्टिंग एल्गोरिदम के लिए डेटा संरचना के रूप में प्रस्तुत की गई थी।^[3] दिज्क्स्ट्रा के एल्गोरिदम जैसे कई कुशल ग्राफ एल्गोरिदम में भी हीप्स महत्वपूर्ण हैं। जब हीप पूर्ण बाइनरी ट्री होता है, तो इसकी ऊंचाई सबसे छोटी होती है - N नोड्स वाले हीप और प्रत्येक नोड के लिए शाखाओं में सदैव log_a N ऊंचाई होती है।

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

संचालन

हीप से जुड़े सामान्य ऑपरेशन हैं:

मूलभूत

फाइंड-मैक्स (या फाइंड-मिन): क्रमशः अधिकतम-हीप का अधिकतम आइटम, या मिन-हीप का न्यूनतम आइटम ढूंढें (उर्फ पीक (डेटा प्रकार ऑपरेशन))
सम्मिलित करें: हीप में नई कुंजी जोड़ना (उर्फ, पुश)।^[4])
एक्स्ट्रैक्ट-मैक्स (या एक्स्ट्रैक्ट-मिन): इसे हीप (उर्फ पॉप) से हटाने के बाद अधिकतम हीप [या मिन हीप से न्यूनतम मान] से अधिकतम मूल्य का नोड लौटाता है^[5])
डिलीट-मैक्स (या डिलीट-मिन): क्रमशः अधिकतम हीप (या मिन हीप) के रूट नोड को हटाना
बदलें: रूट पॉप करें और नई कुंजी दबाएं। पॉप के बाद पुश की तुलना में अधिक कुशल, क्योंकि केवल बार संतुलन की आवश्यकता होती है, दो बार नहीं, और निश्चित आकार के हीप के लिए उपयुक्त है।^[6]

निर्माण

क्रिएट-हीप: खाली हीप बनाएं
हीप बनाना: तत्वों की दी गई श्रृंखला से हीप बनाएं
मर्ज (संघ): दो हीप्स को जोड़कर वैध नया हीप बनाना जिसमें दोनों के सभी तत्व सम्मिलित हों, मूल हीप को संरक्षित करना।
मेल्ड: दो हीप्स को जोड़कर वैध नया हीप बनाना जिसमें दोनों के सभी तत्व सम्मिलित हों, जिससे मूल हीप नष्ट हो जाए।

निरीक्षण

आकार: हीप में वस्तुओं की संख्या लौटाएँ।
खाली है: यदि हीप खाली है तो सही लौटाएं, अन्यथा गलत लौटाएं।

आंतरिक

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

कार्यान्वयन

हीप्स को सामान्यतः पर सरणी डेटा संरचना के साथ कार्यान्वित किया जाता है, जो इस प्रकार है:

सरणी में प्रत्येक तत्व हीप के नोड का प्रतिनिधित्व करता है, और
पैरेंट्स/चाइल्ड का संबंध सरणी में तत्वों के सूचकांकों द्वारा अंतर्निहित डेटा संरचना है।

पूर्ण बाइनरी मैक्स-हीप का उदाहरण जिसमें नोड कुंजियाँ 1 से 100 तक पूर्णांक हैं और इसे सरणी में कैसे संग्रहीत किया जाएगा।

बाइनरी हीप के लिए, सरणी में, पहले इंडेक्स में मूल तत्व होता है। सरणी के अगले दो सूचकांकों में रूट के बच्चे सम्मिलित हैं। अगले चार सूचकांकों में रूट के दो चाइल्ड नोड्स के चार बच्चे सम्मिलित हैं, इत्यादि। इसलिए, सूचकांक $i$ पर नोड दिया गया है, इसके बच्चे सूचकांकों $2i+1$ और $2i+2$ पर हैं, और इसका पेरेंट इंडेक् $⌊(i -1)/2⌋$ पर है। यह सरल अनुक्रमण योजना ट्री को ऊपर या नीचे ले जाने को कुशल बनाती है।

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

किसी तत्व को हीप में डालने या हटाने के बाद, हीप की गुण का उल्लंघन हो सकता है, और सरणी के अन्दर तत्वों को स्वैप करके हीप को फिर से संतुलित किया जाना चाहिए।

चूँकि विभिन्न प्रकार के हीप परिचालन को अलग-अलग तरीके से लागू करते हैं, सबसे आम तरीका इस प्रकार है:

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

तत्वों की दी गई सारणी से एक बाइनरी (या डी-एरी) हीप का निर्माण क्लासिक फ़्लॉइड एल्गोरिदम का उपयोग करके रैखिक समय में किया जा सकता है, जिसमें तुलना की सबसे खराब स्थिति संख्या 2N − 2s₂(N) − e₂(N) (एक बाइनरी हीप के लिए) के बराबर है, जहां s₂(N) N के बाइनरी प्रतिनिधित्व के सभी अंकों का योग है और e₂(N) N के अभाज्य गुणनखंड में 2 का घातांक है।^[7] यह मूल रूप से खाली हीप में लगातार सम्मिलन के अनुक्रम से तेज़ है, जो लॉग-लीनियर है।^{[lower-alpha 1]}

वेरिएंट

विकल्पों के लिए सैद्धांतिक सीमाओं की तुलना

Here are time complexities^[8] of various heap data structures. Function names assume a max-heap. For the meaning of "O(f)" and "Θ(f)" see Big O notation.

Operation	find-max	delete-max	insert	increase-key	meld
Binary^[8]	Θ(1)	Θ(log n)	O(log n)	O(log n)	Θ(n)
Leftist	Θ(1)	Θ(log n)	Θ(log n)	O(log n)	Θ(log n)
Binomial^[8]^[9]	Θ(1)	Θ(log n)	Θ(1)^{[lower-alpha 2]}	Θ(log n)	O(log n)^{[lower-alpha 3]}
Fibonacci^[8]^[10]	Θ(1)	O(log n)^{[lower-alpha 2]}	Θ(1)	Θ(1)^{[lower-alpha 2]}	Θ(1)
Pairing^[11]	Θ(1)	O(log n)^{[lower-alpha 2]}	Θ(1)	o(log n)^{[lower-alpha 2]}^{[lower-alpha 4]}	Θ(1)
Brodal^[14]^{[lower-alpha 5]}	Θ(1)	O(log n)	Θ(1)	Θ(1)	Θ(1)
Rank-pairing^[16]	Θ(1)	O(log n)^{[lower-alpha 2]}	Θ(1)	Θ(1)^{[lower-alpha 2]}	Θ(1)
Strict Fibonacci^[17]	Θ(1)	O(log n)	Θ(1)	Θ(1)	Θ(1)
2–3 heap^[18]	O(log n)	O(log n)^{[lower-alpha 2]}	O(log n)^{[lower-alpha 2]}	Θ(1)	?

↑ Each insertion takes O(log(k)) in the existing size of the heap, thus $\sum _{k=1}^{n}O(\log k)$ . Since $\log n/2=(\log n)-1$ , a constant factor (half) of these insertions are within a constant factor of the maximum, so asymptotically we can assume $k=n$ ; formally the time is $nO(\log n)-O(n)=O(n\log n)$ . This can also be readily seen from Stirling's approximation.
↑ ^2.0 ^2.1 ^2.2 ^2.3 ^2.4 ^2.5 ^2.6 ^2.7 ^2.8 Amortized time.
↑ n is the size of the larger heap.
↑ Lower bound of $\Omega (\log \log n),$ ^[12] upper bound of $O(2^{2{\sqrt {\log \log n}}}).$ ^[13]
↑ 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).^[15]

अनुप्रयोग

हीप डेटा संरचना में कई अनुप्रयोग हैं।

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

प्रोग्रामिंग भाषा कार्यान्वयन

C++ मानक लाइब्रेरी हीप्स के लिए make_heap, push_heap और pop_heap एल्गोरिदम (सामान्यतः पर बाइनरी हीप्स के रूप में लागू किया जाता है) प्रदान करती है, जो स्वैच्छिक रूप से यादृच्छिक एक्सेस इटरेटर पर काम करते हैं। यह पुनरावृत्तियों को किसी सरणी के संदर्भ के रूप में मानता है, और सरणी-से-हीप रूपांतरण का उपयोग करता है। यह कंटेनर एडाप्टर priority_queue भी प्रदान करता है, जो इन सुविधाओं को कंटेनर-जैसी कक्षा में लपेटता है। चूँकि, रिप्लेस, सिफ्ट-अप/सिफ्ट-डाउन, या कमी/वृद्धि-कुंजी संचालन के लिए कोई मानक समर्थन नहीं है।
बूस्ट सी++ लाइब्रेरीज़ में हीप्स लाइब्रेरी सम्मिलित है। एसटीएल के विपरीत, यह कमी और वृद्धि के संचालन का समर्थन करता है, और अतिरिक्त प्रकार के हीप का समर्थन करता है: विशेष रूप से, यह डी-एरी, द्विपद, फाइबोनैचि, युग्मन और स्कू हीप का समर्थन करता है।
डी-एरी हीप और बी-हीप समर्थन के साथ C (प्रोग्रामिंग भाषा) और C++ के लिए जेनेरिक हीप कार्यान्वयन है। यह एसटीएल जैसी एपीआई प्रदान करता है।
डी (प्रोग्रामिंग भाषा) की मानक लाइब्रेरी में std.container.BinaryHeap सम्मिलित है, जिसे डी के श्रेणियों के संदर्भ में लागू किया गया है। इंस्टेंस का निर्माण किसी भी रैंडम-एक्सेस रेंज से किया जा सकता है। BinaryHeap एक इनपुट रेंज इंटरफ़ेस को प्रकाशित करता है जो डी के अंतर्निहित foreach स्टेटमेंट के साथ पुनरावृत्ति और std.algorithm पैकेट के रेंज-आधारित एपीआई के साथ एकीकरण की अनुमति देता है।
हास्केल (प्रोग्रामिंग भाषा) के लिए Data.Heap मापांक है।
जावा (प्रोग्रामिंग भाषा) प्लेटफ़ॉर्म (संस्करण 1.5 से) जावा कलेक्शन फ्रेमवर्क में क्लास java.util.PriorityQueue के साथ एक बाइनरी हीप कार्यान्वयन प्रदान करता है। यह वर्ग डिफ़ॉल्ट रूप से न्यूनतम-हीप लागू करता है; मैक्स-हीप को लागू करने के लिए, प्रोग्रामर को कस्टम तुलनित्र लिखना चाहिए। प्रतिस्थापन, सिफ्ट-अप/सिफ्ट-डाउन, या कमी/वृद्धि-कुंजी संचालन के लिए कोई समर्थन नहीं है।
पायथन (प्रोग्रामिंग भाषा) में एक heapq मॉड्यूल है जो बाइनरी हीप का उपयोग करके प्राथमिकता क्रम लागू करता है। लाइब्रेरी के-वे मर्जिंग का समर्थन करने के लिए हीप्रप्लेस फ़ंक्शन को प्रकाशित करती है।
मानक पीएचपी लाइब्रेरी में संस्करण 5.3 के अनुसार पीएचपी में मैक्स-हीप (SplMaxHeap) और न्यूनतम-हीप (SplMinHeap) दोनों हैं।
पर्ल के पास सीपीएएन पर उपलब्ध हीप वितरण में बाइनरी, बाइनोमियल और फाइबोनैचि हीप्स Heap का कार्यान्वयन किया हैं।
गो (प्रोग्रामिंग भाषा) भाषा में heap सम्मिलित है हीप एल्गोरिदम वाला पैकेज जो स्वैच्छिक प्रकार पर काम करता है जो किसी दिए गए इंटरफ़ेस को संतुष्ट करता है। वह पैकेज रिप्लेस, सिफ्ट-अप/सिफ्ट-डाउन, या कमी/वृद्धि-कुंजी संचालन का समर्थन नहीं करता है।
Apple की कोर फाउंडेशन लाइब्रेरी में CFBinaryHeap संरचना सम्मिलित है।
फिरौन के पास परीक्षण मामलों के सेट के साथ संग्रह-अनुक्रमणीय पैकेज में हीप का कार्यान्वयन है। टाइमर इवेंट लूप के कार्यान्वयन में हीप का उपयोग किया जाता है।
रस्ट प्रोग्रामिंग भाषा में इसके मानक लाइब्रेरी के collections मॉड्यूल में एक बाइनरी मैक्स-हीप कार्यान्वयन, BinaryHeap है।
.NET में प्राथमिकता क्यू वर्ग है जो क्वाटरनरी (डी-आरी) मिन-हीप कार्यान्वयन का उपयोग करता है। यह .NET 6 से उपलब्ध है।

यह भी देखें

छँटाई एल्गोरिथ्म
डेटा संरचना खोजें
स्टैक (सार डेटा प्रकार)
क्रम (सार डेटा प्रकार)
ट्री (डेटा संरचना)
ट्रैप, हीप-आदेशित पेड़ों पर आधारित बाइनरी सर्च ट्री का रूप

संदर्भ

↑ Black (ed.), Paul E. (2004-12-14). Entry for heap in Dictionary of Algorithms and Data Structures. Online version. U.S. National Institute of Standards and Technology, 14 December 2004. Retrieved on 2017-10-08 from https://xlinux.nist.gov/dads/HTML/heap.html.
↑ CORMEN, THOMAS H. (2009). एल्गोरिदम का परिचय. United States of America: The MIT Press Cambridge, Massachusetts London, England. pp. 151–152. ISBN 978-0-262-03384-8.
↑ Williams, J. W. J. (1964), "Algorithm 232 - Heapsort", Communications of the ACM, 7 (6): 347–348, doi:10.1145/512274.512284
↑ The Python Standard Library, 8.4. heapq — Heap queue algorithm, heapq.heappush
↑ The Python Standard Library, 8.4. heapq — Heap queue algorithm, heapq.heappop
↑ The Python Standard Library, 8.4. heapq — Heap queue algorithm, heapq.heapreplace
↑ Suchenek, Marek A. (2012), "Elementary Yet Precise Worst-Case Analysis of Floyd's Heap-Construction Program", Fundamenta Informaticae, IOS Press, 120 (1): 75–92, doi:10.3233/FI-2012-751

[8] Each insertion takes O(log(k)) in the existing size of the heap, thus $\sum _{k=1}^{n}O(\log k)$ . Since $\log n/2=(\log n)-1$ , a constant factor (half) of these insertions are within a constant factor of the maximum, so asymptotically we can assume $k=n$ ; formally the time is $nO(\log n)-O(n)=O(n\log n)$ . This can also be readily seen from Stirling's approximation.

[amortized-11] 2.0 ^2.1 ^2.2 ^2.3 ^2.4 ^2.5 ^2.6 ^2.7 ^2.8 Amortized time.

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

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

[brodal-20] 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).^[15]

[1] Black (ed.), Paul E. (2004-12-14). Entry for heap in Dictionary of Algorithms and Data Structures. Online version. U.S. National Institute of Standards and Technology, 14 December 2004. Retrieved on 2017-10-08 from https://xlinux.nist.gov/dads/HTML/heap.html.

[2] CORMEN, THOMAS H. (2009). एल्गोरिदम का परिचय. United States of America: The MIT Press Cambridge, Massachusetts London, England. pp. 151–152. ISBN 978-0-262-03384-8.

[3] Williams, J. W. J. (1964), "Algorithm 232 - Heapsort", Communications of the ACM, 7 (6): 347–348, doi:10.1145/512274.512284

[4] The Python Standard Library, 8.4. heapq — Heap queue algorithm, heapq.heappush

[5] The Python Standard Library, 8.4. heapq — Heap queue algorithm, heapq.heappop

[6] The Python Standard Library, 8.4. heapq — Heap queue algorithm, heapq.heapreplace

[7] Suchenek, Marek A. (2012), "Elementary Yet Precise Worst-Case Analysis of Floyd's Heap-Construction Program", Fundamenta Informaticae, IOS Press, 120 (1): 75–92, doi:10.3233/FI-2012-751

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[lower-alpha 1]

[8]

[9]

[lower-alpha 2]

[lower-alpha 3]

[10]

[11]

[lower-alpha 4]

[14]

[lower-alpha 5]

[16]

[17]

[18]

[12]

[13]

[15]

[19]

Anonymous

Search

हीप (डेटा संरचना)

Namespaces

More

Page actions

Contents