हीप
कंप्यूटर विज्ञान में, एक हीप एक विशेष ट्री-आधारित आंकड़ा संरचना है, जो अनिवार्य रूप से एक लगभग पूर्ण ट्री है जो हीप संपत्ति को संतुष्ट करता है: एक मक्स-हीप में, किसी भी दिए गए नोड C के लिए, यदि P C का एक मूल नोड है, P की कुंजी (मान) C की कुंजी से अधिक या बराबर है। एक मिन-हीप में, P की कुंजी C की कुंजी से कम या बराबर है । हीप के "शीर्ष" पर (बिना पेरेन्त के) नोड को रूट नोड कहा जाता है। हीप एक सार डेटा प्रकार का अधिकतम कुशल कार्यान्वयन है जिसे प्रिओरिति क्यु कहा जाता है, और वास्तव में, प्रिओरिति क्यु को अक्सर "हीप्स" के रूप में संदर्भित किया जाता है, भले ही वे कैसे लागू हो। हीप में, उच्चतम (या निम्नतम) प्राथमिकता तत्व हमेशा रूट पर संग्रहीत होता है। हालांकि, एक हीप एक सॉर्ट की गई संरचना नहीं है; इसे आंशिक रूप से आदेश दिया जा सकता है। एक हीप एक उपयोगी डेटा संरचना है जब वस्तु को उच्चतम (या निम्नतम) प्राथमिकता के साथ बार-बार निकालना आवश्यक होता है। हीप का एक सामान्य कार्यान्वयन बाइनरी हीप है, जिसमें पेड़ एक द्विआधारी पेड़ है (आंकड़ा देखें)। हीप डेटा संरचना, विशेष रूप से बाइनरी हीप, 1964 में जे डब्ल्यू जे विलियम्स द्वारा शुरू किया गया था, जो कि हीपसॉर्ट सॉर्टिंग एल्गोरिदम के लिए डेटा संरचना के रूप में था। हीप्स कई कुशल ग्राफ एल्गोरिदम जैसे कि दिज्क्स्ट्रा एल्गोरिथ्म में भी महत्वपूर्ण हैं। जब एक हीप एक पूर्ण बाइनरी ट्री होता है, तो इसकी सबसे छोटी संभव ऊंचाई होती है - N नोड्स के साथ एक हीप और प्रत्येक नोड के लिए a शाखा में हमेशा loga N ऊंचाई होती है। ध्यान दें, जैसा कि ग्राफिक में दिखाया गया है, भाई-बहन के बीच कोई निहित आदेश नहीं है और इन-ऑर्डर ट्रैवर्सल के लिए कोई निहित अनुक्रम नहीं है । ऊपर उल्लिखित हीप संबंध केवल नोड्स और उनके पेरेन्त, पेरेन्त के पेरेन्त, आदि के बीच लागू होता है। प्रत्येक नोड में अधिकतम बच्चों की संख्या हीप के प्रकार पर निर्भर हो सकती है।