हीप (डेटा संरचना): Difference between revisions

From Vigyanwiki
No edit summary
Line 1: Line 1:
{{short description|Computer science data structure}}
{{short description|Computer science data structure}}
{{For|the memory heap (in low-level computer programming), which bears no relation to the data structure|C dynamic memory allocation}}
{{For|मेमोरी हीप (निम्न-स्तरीय कंप्यूटर प्रोग्रामिंग में), जिसका डेटा संरचना से कोई संबंध नहीं है|C डायनामिक मेमोरी आवंटन}}
[[File:Max-Heap-new.svg|thumb|एक [[ बाइनरी वृक्ष ]] मैक्स-हीप का उदाहरण जिसमें नोड कुंजियाँ 1 और 100 के बीच पूर्णांक हैं]][[कंप्यूटर विज्ञान]] में, हीप एक विशेष [[वृक्ष ([[डेटा संरचना]])]]-आधारित डेटा संरचना है जो हीप संपत्ति को संतुष्ट करती है: ''अधिकतम हीप'' में, किसी दिए गए [[नोड (कंप्यूटर विज्ञान)]] सी के लिए, यदि पी मूल नोड है C, तो P की ''कुंजी'' ('मान'') C की कुंजी से अधिक या उसके बराबर है। एक ''न्यूनतम ढेर'' में, P की कुंजी, C की कुंजी से कम या उसके बराबर है सी की कुंजी<ref>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.</ref> ढेर के शीर्ष पर स्थित नोड (बिना माता-पिता के) को रूट नोड कहा जाता है।
[[File:Max-Heap-new.svg|thumb|एक [[ बाइनरी वृक्ष ]] मैक्स-हीप का उदाहरण जिसमें नोड कुंजियाँ 1 और 100 के बीच पूर्णांक हैं]][[कंप्यूटर विज्ञान]] में, हीप एक विशेष [[वृक्ष ([[डेटा संरचना]])]]-आधारित डेटा संरचना है जो हीप संपत्ति को संतुष्ट करती है: ''अधिकतम हीप'' में, किसी दिए गए [[नोड (कंप्यूटर विज्ञान)]] सी के लिए, यदि पी मूल नोड है C, तो P की ''कुंजी'' ('मान'') C की कुंजी से अधिक या उसके बराबर है। एक ''न्यूनतम ढेर'' में, P की कुंजी, C की कुंजी से कम या उसके बराबर है सी की कुंजी<ref>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.</ref> ढेर के शीर्ष पर स्थित नोड (बिना माता-पिता के) को रूट नोड कहा जाता है।


Revision as of 15:10, 23 July 2023

For मेमोरी हीप (निम्न-स्तरीय कंप्यूटर प्रोग्रामिंग में), जिसका डेटा संरचना से कोई संबंध नहीं है, see C डायनामिक मेमोरी आवंटन.
एक बाइनरी वृक्ष मैक्स-हीप का उदाहरण जिसमें नोड कुंजियाँ 1 और 100 के बीच पूर्णांक हैं

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

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

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

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

संचालन

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

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

कार्यान्वयन

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

  • सरणी में प्रत्येक तत्व ढेर के एक नोड का प्रतिनिधित्व करता है, और
  • माता-पिता/बच्चे का संबंध सरणी में तत्वों के सूचकांकों द्वारा अंतर्निहित डेटा संरचना है।
एक पूर्ण बाइनरी मैक्स-हीप का उदाहरण जिसमें नोड कुंजियाँ 1 से 100 तक पूर्णांक हैं और इसे एक सरणी में कैसे संग्रहीत किया जाएगा।

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

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

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

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

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

तत्वों की दी गई सारणी से एक बाइनरी (या डी-एरी) ढेर का निर्माण क्लासिक हीप्सोर्ट#वेरिएशन का उपयोग करके रैखिक समय में किया जा सकता है, जिसमें सबसे खराब स्थिति में तुलना की संख्या 2एन' के बराबर होती है। ' − 2''2(एन) - ई2(एन) (एक बाइनरी ढेर के लिए), जहां एस2(एन) एन और ई के द्विआधारी प्रतिनिधित्व के सभी अंकों का योग है2(एन) एन के अभाज्य गुणनखंडन में 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) ?
  1. ↑ Each insertion takes O(log(k)) in the existing size of the heap, thus . Since , a constant factor (half) of these insertions are within a constant factor of the maximum, so asymptotically we can assume ; formally the time is . This can also be readily seen from Stirling's approximation.
  2. ↑ 2.0 2.1 2.2 2.3 2.4 2.5 2.6 2.7 2.8 Amortized time.
  3. ↑ n is the size of the larger heap.
  4. ↑ Lower bound of [12] upper bound of [13]
  5. ↑ 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, जो इन सुविधाओं को एक कंटेनर-जैसी कक्षा में लपेटता है। हालाँकि, रिप्लेस, सिफ्ट-अप/सिफ्ट-डाउन, या कमी/वृद्धि-कुंजी संचालन के लिए कोई मानक समर्थन नहीं है।
  • बूस्ट (सी++ लाइब्रेरीज़)|बूस्ट सी++ लाइब्रेरीज़ में एक हीप्स लाइब्रेरी शामिल है। एसटीएल के विपरीत, यह कमी और वृद्धि के संचालन का समर्थन करता है, और अतिरिक्त प्रकार के ढेर का समर्थन करता है: विशेष रूप से, यह डी-एरी, द्विपद, फाइबोनैचि, युग्मन और तिरछा ढेर का समर्थन करता है।
  • D-ary हीप और B-हीप समर्थन के साथ C (प्रोग्रामिंग भाषा) और C++ के लिए जेनेरिक हीप कार्यान्वयन है। यह एसटीएल जैसी एपीआई प्रदान करता है।
  • डी (प्रोग्रामिंग भाषा) की मानक लाइब्रेरी में शामिल है std.container.BinaryHeap, जिसे डी के श्रेणियों के संदर्भ में लागू किया गया है। इंस्टेंस का निर्माण किसी भी रैंडम-एक्सेस रेंज से किया जा सकता है। BinaryHeap एक इनपुट रेंज इंटरफ़ेस को उजागर करता है जो डी के अंतर्निहित के साथ पुनरावृत्ति की अनुमति देता है foreach कथन और रेंज-आधारित एपीआई के साथ एकीकरण std.algorithm पैकेट।
  • हास्केल (प्रोग्रामिंग भाषा) के लिए है Data.Heap मापांक।
  • जावा (प्रोग्रामिंग भाषा) प्लेटफ़ॉर्म (संस्करण 1.5 से) क्लास के साथ बाइनरी हीप कार्यान्वयन प्रदान करता है java.util.PriorityQueue जावा संग्रह ढांचा में। यह वर्ग डिफ़ॉल्ट रूप से एक न्यूनतम-ढेर लागू करता है; मैक्स-हीप को लागू करने के लिए, प्रोग्रामर को एक कस्टम तुलनित्र लिखना चाहिए। प्रतिस्थापन, सिफ्ट-अप/सिफ्ट-डाउन, या कमी/वृद्धि-कुंजी संचालन के लिए कोई समर्थन नहीं है।
  • पायथन (प्रोग्रामिंग भाषा) में एक है heapq मॉड्यूल जो बाइनरी हीप का उपयोग करके प्राथमिकता कतार लागू करता है। लाइब्रेरी के-वे मर्जिंग का समर्थन करने के लिए एक हीप्रप्लेस फ़ंक्शन को उजागर करती है।
  • PHP में अधिकतम-ढेर दोनों हैं (SplMaxHeap) और न्यूनतम-ढेर (SplMinHeap) मानक PHP लाइब्रेरी में संस्करण 5.3 के अनुसार।
  • पर्ल ने में बाइनरी, बाइनोमियल और फाइबोनैचि हीप्स का कार्यान्वयन किया है Heap वितरण सीपीएएन पर उपलब्ध है।
  • गो (प्रोग्रामिंग भाषा) भाषा में एक शामिल है heap हीप एल्गोरिदम वाला पैकेज जो एक मनमाने प्रकार पर काम करता है जो किसी दिए गए इंटरफ़ेस को संतुष्ट करता है। वह पैकेज रिप्लेस, सिफ्ट-अप/सिफ्ट-डाउन, या कमी/वृद्धि-कुंजी संचालन का समर्थन नहीं करता है।
  • Apple की कोर फाउंडेशन लाइब्रेरी में एक शामिल है CFBinaryHeap संरचना।
  • फिरौन के पास परीक्षण मामलों के एक सेट के साथ संग्रह-अनुक्रमणीय पैकेज में ढेर का कार्यान्वयन है। टाइमर इवेंट लूप के कार्यान्वयन में एक ढेर का उपयोग किया जाता है।
  • रस्ट (प्रोग्रामिंग भाषा) प्रोग्रामिंग भाषा में बाइनरी मैक्स-हीप कार्यान्वयन है, BinaryHeap, में collections इसके मानक पुस्तकालय का मॉड्यूल।
  • .NET में प्राथमिकता क्यू वर्ग है जो क्वाटरनरी (डी-आरी) मिन-हीप कार्यान्वयन का उपयोग करता है। यह .NET 6 से उपलब्ध है।

यह भी देखें

संदर्भ

  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.
  8. ↑ 8.0 8.1 8.2 8.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.
  9. ↑ "Binomial Heap | Brilliant Math & Science Wiki". brilliant.org (in English). Retrieved 2019-09-30.
  10. ↑ 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.
  11. ↑ 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
  12. ↑ 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.
  13. ↑ 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.
  16. ↑ Haeupler, Bernhard; Sen, Siddhartha; Tarjan, Robert E. (November 2011). "Rank-pairing heaps" (PDF). SIAM J. Computing. 40 (6): 1463–1485. doi:10.1137/100785351.
  17. ↑ 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.
  18. ↑ Takaoka, Tadao (1999), Theory of 2–3 Heaps (PDF), p. 12
  19. ↑ Frederickson, Greg N. (1993), "An Optimal Algorithm for Selection in a Min-Heap", Information and Computation (PDF), vol. 104, Academic Press, pp. 197–214, doi:10.1006/inco.1993.1030, archived from the original (PDF) on 2012-12-03, retrieved 2010-10-31


बाहरी संबंध

Wikimedia Commons has media related to Heap data structures.
The Wikibook Data Structures has a page on the topic of: Min and Max Heaps
  • Heap at Wolfram MathWorld
  • Explanation of how the basic heap algorithms work
  • Bentley, Jon Louis (2000). Programming Pearls (2nd ed.). Addison Wesley. pp. 147–162. ISBN 0201657880.
Retrieved from ‘https://www.vigyanwiki.in/index.php?title=हीप_(डेटा_संरचना)&oldid=228636’