हीप
कंप्यूटर विज्ञान में, एक हीप एक विशेष ट्री-आधारित आंकड़ा संरचना है, जो अनिवार्य रूप से एक लगभग पूर्ण ट्री है जो हीप संपत्ति को संतुष्ट करता है: एक "मक्स-हीप" में, किसी भी दिए गए नोड C के लिए, यदि P C का एक मूल नोड है, P की कुंजी (मान) C की कुंजी से अधिक या बराबर है। एक मिन-हीप में, P की कुंजी C की कुंजी से कम या बराबर है । हीप के "शीर्ष" पर (बिना पेरेन्त के) नोड को "रूट" नोड कहा जाता है।
हीप एक सार डेटा प्रकार का अधिकतम कुशल कार्यान्वयन है जिसे प्रिओरिति क्यु कहा जाता है, और वास्तव में, प्रिओरिति क्यु को अक्सर "हीप्स" के रूप में संदर्भित किया जाता है, भले ही वे कैसे लागू हो। हीप में, उच्चतम (या निम्नतम) प्राथमिकता तत्व हमेशा रूट पर संग्रहीत होता है। हालांकि, एक हीप एक सॉर्ट की गई संरचना नहीं है; इसे आंशिक रूप से आदेश दिया जा सकता है। एक हीप एक उपयोगी डेटा संरचना है जब वस्तु को उच्चतम (या निम्नतम) प्राथमिकता के साथ बार-बार निकालना आवश्यक होता है।
हीप का एक सामान्य कार्यान्वयन बाइनरी हीप है, जिसमें पेड़ एक द्विआधारी पेड़ है (आंकड़ा देखें)। हीप डेटा संरचना, विशेष रूप से बाइनरी हीप, 1964 में जे डब्ल्यू जे विलियम्स द्वारा शुरू किया गया था, जो कि हीपसॉर्ट सॉर्टिंग एल्गोरिदम के लिए डेटा संरचना के रूप में था। हीप्स कई कुशल ग्राफ एल्गोरिदम जैसे कि दिज्क्स्ट्रा एल्गोरिथ्म में भी महत्वपूर्ण हैं। जब एक हीप एक पूर्ण बाइनरी ट्री होता है, तो इसकी सबसे छोटी संभव ऊंचाई होती है - N नोड्स के साथ एक हीप और प्रत्येक नोड के लिए a शाखा में हमेशा log "N" ऊंचाई होती है।
ध्यान दें, जैसा कि ग्राफिक में दिखाया गया है, भाई-बहन के बीच कोई निहित आदेश नहीं है और इन-ऑर्डर ट्रैवर्सल के लिए कोई निहित अनुक्रम नहीं है । ऊपर उल्लिखित हीप संबंध केवल नोड्स और उनके पेरेन्त, पेरेन्त के पेरेन्त, आदि के बीच लागू होता है। प्रत्येक नोड में अधिकतम बच्चों की संख्या हीप के प्रकार पर निर्भर हो सकती है।
हीप से जुड़े आम संचालन हैं:
आमतौर पर हीप्स को एक निहित हीप डेटा संरचना के साथ लागू किया जाता है, जो कि एक अंतर्निहित डेटा संरचना है जिसमें एक सरणी (निश्चित आकार या गतिशील सरणी) होती है, जहां प्रत्येक तत्व एक पेड़ के नोड का प्रतिनिधित्व करता है, जिनके पेरेन्त / बच्चों के संबंध उनके सूचकांक द्वारा स्पष्ट रूप से परिभाषित होते हैं। एक तत्व को एक हीप से डाला या हटाए जाने के बाद, ढेर संपत्ति का उल्लंघन हो सकता है और सरणी के भीतर तत्वों को स्वैप करके हीप को संतुलित किया जाना चाहिए। एक अंतर्निहित हीप डेटा संरचना में, पहले (या अंतिम) तत्व में रूट होगा। सरणी के अगले दो तत्वों में इसके बच्चे शामिल हैं। अगले चार में दो बाल नोड्स के चार बच्चे शामिल हैं| इस प्रकार शून्य-आधारित सरणी में "n" नोड के बच्चे होंगे 2n और 2n + 1 और एक-आधारित सरणी में, 2n + 1 और 2n + 2। एक-आधारित सरणियों के लिए तत्व "n" के जनक स्थिति n / 2 पर स्थित है। इसी तरह, शून्य-आधारित सरणियों के लिए, पेरेन्त स्थिति (n-1) / 2 (फ्लोटिंग) पर स्थित होते हैं। यह सरल सूचकांक संगणना करके पेड़ को ऊपर या नीचे ले जाने की अनुमति देता है। हीप को संतुलित करना, ऊपर-ऊपर या ऊपर-नीचे संचालन (स्वैपिंग तत्व जो ऑर्डर से बाहर हैं) द्वारा किया जाता है। जैसा कि हम अतिरिक्त मेमोरी की आवश्यकता के बिना एक सरणी से एक हीप का निर्माण कर सकते हैं (उदाहरण के लिए नोड्स के लिए), हीप सॉर्ट का उपयोग सरणी में जगह को सॉर्ट करने के लिए किया जा सकता है।
विभिन्न प्रकार के हीप विभिन्न तरीकों से संचालन को लागू करते हैं, लेकिन विशेष रूप से, पहले उपलब्ध खाली स्थान में हीप के अंत में नए तत्व को जोड़कर अक्सर सम्मिलन किया जाता है। यह आमतौर पर हीप संपत्ति का उल्लंघन करेगा, और इसलिए तत्वों को तब तक स्थानांतरित कर दिया जाता है जब तक कि हीप संपत्ति को फिर से स्थापित नहीं किया गया हो। इसी प्रकार, रूट को हटाने से रूट को हटा दिया जाता है और फिर आखिरी तत्व को रूट में डाल दिया जाता है और पुनः असंतुलन के लिए नीचे स्थानांतरित किया जाता है। इस प्रकार जड़ को हटाने और नए तत्व को रूट में डालने और नीचे की ओर ले जाने के द्वारा किया जाता है, पॉप की तुलना में एक कदम ऊपर उठाने से बचा जाता है (अंतिम तत्व की निचोड़) के बाद पुश (नए तत्व का झारना)।
तत्वों की दी गई सरणी से बाहर बाइनरी (या डी-अरी) हीप का निर्माण किया जा सकता है, जिसमें क्लासिक फ्लॉयड एल्गोरिथ्म का उपयोग किया जा सकता है, जिसमें 2"N" − 2"s"("N") − "e"("N") के बराबर तुलनात्मक स्थिति सबसे खराब है (एक बाइनरी हीप के लिए), जहां "s"("N") और "e"("N") के द्विआधारी प्रतिनिधित्व के सभी अंकों का योग है। "N" के मुख्य गुणनखंड में 2 का घातांक है| यह मूल रूप से खाली हीप में लगातार सम्मिलन के अनुक्रम से तेज है, जो लॉग-लिनेअर है। यहां विभिन्न हीप डेटा संरचनाओं की समय जटिलताएं हैं। फ़ंक्शन नाम एक मिन-हीप मानता है। "O(f)" और "Θ(f)" के अर्थ के लिए बड़ा ओ संकेतन देखें।
हीप डेटा संरचना में कई अनुप्रयोग हैं।