हीप
कंप्यूटर विज्ञान में, एक हीप एक विशेष ट्री-आधारित आंकड़ा संरचना है, जो अनिवार्य रूप से एक लगभग पूर्ण [1] ट्री है जो हीप संपत्ति को संतुष्ट करता है: एक मक्स-हीप में, किसी भी दिए गए नोड C के लिए, यदि P C का एक मूल नोड है, P की कुंजी (मान) C की कुंजी से अधिक या बराबर है। एक मिन-हीप में, P की कुंजी C की कुंजी से कम या बराबर है [2]। हीप के "शीर्ष" पर (बिना पेरेन्त के) नोड को रूट नोड कहा जाता है।
हीप एक सार डेटा प्रकार का अधिकतम कुशल कार्यान्वयन है जिसे प्रिओरिति क्यु कहा जाता है, और वास्तव में, प्रिओरिति क्यु को अक्सर "हीप्स" के रूप में संदर्भित किया जाता है, भले ही वे कैसे लागू हो। हीप में, उच्चतम (या निम्नतम) प्राथमिकता तत्व हमेशा रूट पर संग्रहीत होता है। हालांकि, एक हीप एक सॉर्ट की गई संरचना नहीं है; इसे आंशिक रूप से आदेश दिया जा सकता है। एक हीप एक उपयोगी डेटा संरचना है जब वस्तु को उच्चतम (या निम्नतम) प्राथमिकता के साथ बार-बार निकालना आवश्यक होता है।
हीप का एक सामान्य कार्यान्वयन बाइनरी हीप है, जिसमें पेड़ एक द्विआधारी पेड़ है (आंकड़ा देखें)। हीप डेटा संरचना, विशेष रूप से बाइनरी हीप, 1964 में जे डब्ल्यू जे विलियम्स द्वारा शुरू किया गया था, जो कि हीपसॉर्ट सॉर्टिंग एल्गोरिदम के लिए डेटा संरचना के रूप में था। [3] हीप्स कई कुशल ग्राफ एल्गोरिदम जैसे कि दिज्क्स्ट्रा एल्गोरिथ्म में भी महत्वपूर्ण हैं। जब एक हीप एक पूर्ण बाइनरी ट्री होता है, तो इसकी सबसे छोटी संभव ऊंचाई होती है - N नोड्स के साथ एक हीप और प्रत्येक नोड के लिए a शाखा में हमेशा loga N ऊंचाई होती है।
ध्यान दें, जैसा कि ग्राफिक में दिखाया गया है, भाई-बहन के बीच कोई निहित आदेश नहीं है और इन-ऑर्डर ट्रैवर्सल के लिए कोई निहित अनुक्रम नहीं है । ऊपर उल्लिखित हीप संबंध केवल नोड्स और उनके पेरेन्त, पेरेन्त के पेरेन्त, आदि के बीच लागू होता है। प्रत्येक नोड में अधिकतम बच्चों की संख्या हीप के प्रकार पर निर्भर हो सकती है।
संचालन
हीप से जुड़े आम संचालन हैं:
- मूलभूत
- फ़ैन्द-मक्स (या फ़ैन्द-मिन): अधिकतम-हीप का एक अधिकतम आइटम या न्यूनतम-हीप का न्यूनतम आइटम खोजें ()।
- इन्सेर्त: हीप में एक नई कुंजी जोड़ना (पुश [4])|
- एक्स्त्रक्त: यह हीप से एक अधिकतम हीप (या न्यूनतम मूल्य का न्यूनतम मान) के हीप को वापस करता है इसे हीप से हटाने के बाद (पॉप [5])|
- डिलीट-मैक्स (या डिलीट-मिन): एक मक्स-हीप (या मिन-हीप) के रूट नोड को क्रमशः हटाते हुए|
- रिप्ल्स: पॉप रूट और एक नई कुंजी धक्का। पुश के बाद पॉप से अधिक कुशल, चूंकि केवल एक बार संतुलन की आवश्यकता होती है, दो बार नहीं, और निश्चित आकार के ढेर के लिए उपयुक्त। [6]
- निर्माण
- क्रिएत-हीप: एक खाली हीप बनाएँ|
- हीपीफ़ै: तत्वों के दिए गए सरणी से एक हीप बनाएं|
- मर्ज (संघ): दो हीप को जोड़कर एक वैध नया हीप बनाने के लिए दोनों के सभी तत्वों को मिलाकर, मूल हीप को संरक्षित करना।
- मेल्ड: दो हीप को मिलाकर एक नया हीप बनाना जिसमें सभी तत्व होते हैं, मूल हीप को नष्ट करते हुए।
- निरीक्षण
- साइज : हीप में आइटम की संख्या लौटाएं।
- इज-एम्प्ती: अगर हीप खाली है, तो सच है, अन्यथा झूठ।
कार्यान्वयन
आमतौर पर हीप्स को एक निहित हीप डेटा संरचना के साथ लागू किया जाता है, जो कि एक अंतर्निहित डेटा संरचना है जिसमें एक सरणी (निश्चित आकार या गतिशील सरणी) होती है, जहां प्रत्येक तत्व एक पेड़ के नोड का प्रतिनिधित्व करता है, जिनके पेरेन्त / बच्चों के संबंध उनके सूचकांक द्वारा स्पष्ट रूप से परिभाषित होते हैं। एक तत्व को एक हीप से डाला या हटाए जाने के बाद, ढेर संपत्ति का उल्लंघन हो सकता है और सरणी के भीतर तत्वों को स्वैप करके हीप को संतुलित किया जाना चाहिए।
एक अंतर्निहित हीप डेटा संरचना में, पहले (या अंतिम) तत्व में रूट होगा। सरणी के अगले दो तत्वों में इसके बच्चे शामिल हैं। अगले चार में दो बाल नोड्स के चार बच्चे शामिल हैं| इस प्रकार शून्य-आधारित सरणी में n नोड के बच्चे होंगे 2n और 2n + 1 और एक-आधारित सरणी में, 2n + 1 और 2n + 2। एक-आधारित सरणियों के लिए तत्व n के जनक स्थिति n / 2 पर स्थित है। इसी तरह, शून्य-आधारित सरणियों के लिए, पेरेन्त स्थिति (n-1) / 2 (फ्लोटिंग) पर स्थित होते हैं। यह सरल सूचकांक संगणना करके पेड़ को ऊपर या नीचे ले जाने की अनुमति देता है। हीप को संतुलित करना, ऊपर-ऊपर या ऊपर-नीचे संचालन (स्वैपिंग तत्व जो ऑर्डर से बाहर हैं) द्वारा किया जाता है। जैसा कि हम अतिरिक्त मेमोरी की आवश्यकता के बिना एक सरणी से एक हीप का निर्माण कर सकते हैं (उदाहरण के लिए नोड्स के लिए), हीप सॉर्ट का उपयोग सरणी में जगह को सॉर्ट करने के लिए किया जा सकता है।
विभिन्न प्रकार के हीप विभिन्न तरीकों से संचालन को लागू करते हैं, लेकिन विशेष रूप से, पहले उपलब्ध खाली स्थान में हीप के अंत में नए तत्व को जोड़कर अक्सर सम्मिलन किया जाता है। यह आमतौर पर हीप संपत्ति का उल्लंघन करेगा, और इसलिए तत्वों को तब तक स्थानांतरित कर दिया जाता है जब तक कि हीप संपत्ति को फिर से स्थापित नहीं किया गया हो। इसी प्रकार, रूट को हटाने से रूट को हटा दिया जाता है और फिर आखिरी तत्व को रूट में डाल दिया जाता है और पुनः असंतुलन के लिए नीचे स्थानांतरित किया जाता है। इस प्रकार जड़ को हटाने और नए तत्व को रूट में डालने और नीचे की ओर ले जाने के द्वारा किया जाता है, पॉप की तुलना में एक कदम ऊपर उठाने से बचा जाता है (अंतिम तत्व की निचोड़) के बाद पुश (नए तत्व का झारना)।
तत्वों की दी गई सरणी से बाहर बाइनरी (या डी-अरी) हीप का निर्माण किया जा सकता है, जिसमें क्लासिक फ्लॉयड एल्गोरिथ्म का उपयोग किया जा सकता है, जिसमें 2N − 2s2(N) − e2(N) के बराबर तुलनात्मक स्थिति सबसे खराब है (एक बाइनरी हीप के लिए), जहां s2(N) और e2(N) के द्विआधारी प्रतिनिधित्व के सभी अंकों का योग है। N के मुख्य गुणनखंड में 2 का घातांक है| [7] यह मूल रूप से खाली हीप में लगातार सम्मिलन के अनुक्रम से तेज है, जो लॉग-लिनेअर है।
वेरिएंट के लिए सिद्धांतिक सीमा की तुलना
यहां विभिन्न हीप डेटा संरचनाओं की समय जटिलताएं हैं। फ़ंक्शन नाम एक मिन-हीप मानता है। "O(f)" और "Θ(f)" के अर्थ के लिए बड़ा ओ संकेतन देखें।
| संचालन | फ़ैन्द-मिन | दिलिट-मिन | इन्सेर्त | डिक्रिज-की | मेल्ड |
|---|---|---|---|---|---|
| बाइनरी | Θ(1) | Θ(log n) | O(log n) | O(log n) | Θ(n) |
| लेफ़्टिस्ट | Θ(1) | Θ(log n) | Θ(log n) | O(log n) | Θ(log n) |
| बैनोमिअल | Θ(1) | Θ(log n) | Θ(1) | Θ(log n) | O(log n) |
| फ़िबोनकि | Θ(1) | O(log n) | Θ(1) | Θ(1) | Θ(1) |
| पेरिन्ग | Θ(1) | O(log n) | Θ(1) | O(log n) | Θ(1) |
| ब्रोडल | Θ(1) | O(log n) | Θ(1) | Θ(1) | Θ(1) |
| रैन्क-पेरिन्ग | Θ(1) | O(log n) | Θ(1) | Θ(1) | Θ(1) |
| 2-3 हीप | Θ(log n) | O(log n) | O(log n) | Θ(1) | ? |
अनुप्रयोग
हीप डेटा संरचना में कई अनुप्रयोग हैं।
- हीप सॉर्ट: सबसे अच्छे सॉर्टिंग तरीकों में से एक है जिसमें कोई द्विघात सबसे खराब स्थिति नहीं है।
- चयन एल्गोरिदम: एक हीप निरंतर समय में न्यूनतम या अधिकतम तत्व तक पहुंच की अनुमति देता है, और अन्य चयन (जैसे कि माध्य या kth तत्त्व) उप-रैखिक समय में डेटा पर एक ढेर में किया जा सकता है।
- ग्राफ एल्गोरिदम: आंतरिक ट्रैवर्सल डेटा संरचनाओं के रूप में ढेर का उपयोग करके, बहुपद क्रम से रन टाइम कम हो जाएगा। इस तरह की समस्याओं के उदाहरण हैं प्राइम का न्यूनतम-फैले हुए पेड़ का एल्गोरिथ्म और दिज्क्स्ट्रा का सबसे छोटा पथ एल्गोरिथम।
- प्राथमिकता कतार: एक प्राथमिकता कतार एक सार अवधारणा है जैसे "एक सूची" या "एक नक्शा"; जिस तरह एक सूची को एक लिंक्ड सूची या एक सरणी के साथ कार्यान्वित किया जा सकता है, एक प्राथमिकता कतार ढेर या अन्य तरीकों से लागू की जा सकती है।
- के-वे मर्ज: एक ढेर डेटा संरचना एकल सॉर्ट किए गए आउटपुट स्ट्रीम में पहले से ही सॉर्ट किए गए इनपुट स्ट्रीम को मर्ज करने के लिए उपयोगी है। विलय की आवश्यकता के उदाहरणों में वितरित डेटा से बाहरी सॉर्टिंग और स्ट्रीमिंग परिणाम शामिल हैं जैसे लॉग संरचित मर्ज ट्री। आंतरिक लूप न्यूनतम तत्व प्राप्त कर रहा है, इसी इनपुट स्ट्रीम के लिए अगले तत्व के साथ बदल रहा है, फिर एक झारना-डाउन ढेर ऑपरेशन कर रहा है। (वैकल्पिक रूप से प्रतिस्थापित कार्य।) (प्राथमिकता कतार के एक्सट्रेक्ट-मैक्स और इंसर्ट फ़ंक्शंस का उपयोग करना बहुत कम कुशल है।)
- आदेश के आँकड़े: ढेर डेटा संरचना का उपयोग कुशलता से एक सरणी में केथ सबसे छोटे (या सबसे बड़े) तत्व को खोजने के लिए किया जा सकता है।
सन्दर्भ
- ↑ CORMEN, THOMAS H. (2009). INTRODUCTION TO ALGORITHMS. United States of America: The MIT Press Cambridge, Massachusetts London, England. पपृ॰ 151–152. आई॰ऍस॰बी॰ऍन॰ 978-0-262-03384-8.
- ↑ 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
- ↑ Williams, J. W. J. (1964), "Algorithm 232 - Heapsort", Communications of the ACM, 7 (6): 347–348, डीओआइ: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, डीओआइ:10.3233/FI-2012-751.