बाइनरी हीप

Binary (min) heap
Type	binary tree/heap
Invented	1964
Invented by	J. W. J. Williams
Time complexity in big O notation
Algorithm Average Worst case Space O(n) O(n) Search O(n) O(n) Insert O(1) O(log n) Find-min O(1) O(1) Delete-min O(log n) O(log n)

संपूर्ण बाइनरी मैक्स-हीप का उदाहरण

संपूर्ण बाइनरी मिन हीप का उदाहरण

बाइनरी हीप एक हीप (डेटा संरचना) डेटा संरचना है जो द्विआधारी वृक्ष का रूप लेती है। बाइनरी हीप्स प्राथमिकता कतारों को लागू करने का एक सामान्य तरीका है। बाइनरी हीप को 1964 में जे.डब्ल्यू.जे. विलियम्स द्वारा ढेर बनाएं और छांटें के लिए डेटा संरचना के रूप में पेश किया गया था।

एक बाइनरी हीप को दो अतिरिक्त बाधाओं के साथ एक बाइनरी ट्री के रूप में परिभाषित किया गया है:

• आकार गुण: एक बाइनरी हीप एक पूरा बाइनरी ट्री है; यानी, संभवतः अंतिम (सबसे गहरे) को छोड़कर, पेड़ के सभी स्तर पूरी तरह से भरे हुए हैं, और, यदि पेड़ का अंतिम स्तर पूरा नहीं हुआ है, तो उस स्तर के नोड्स बाएं से दाएं भरे हुए हैं।
• हीप संपत्ति: कुछ कुल क्रम के अनुसार, प्रत्येक नोड में संग्रहीत कुंजी या तो (≥) से अधिक या उसके बराबर है या नोड के बच्चों में कुंजी से कम या (≤) के बराबर है।

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

ढेर परिचालन

सम्मिलित करने और हटाने के दोनों ऑपरेशन पहले ढेर के अंत से जोड़कर या हटाकर, आकार संपत्ति के अनुरूप ढेर को संशोधित करते हैं। फिर ढेर की संपत्ति को ढेर के ऊपर या नीचे जाकर बहाल किया जाता है। दोनों ऑपरेशन लगते हैं O(log n) समय।

सम्मिलित करें

ढेर में एक तत्व जोड़ने के लिए, हम यह एल्गोरिदम निष्पादित कर सकते हैं:

1. तत्व को सबसे बाईं ओर खुले स्थान पर ढेर के निचले स्तर पर जोड़ें।
2. जोड़े गए तत्व की उसके मूल तत्व से तुलना करें; यदि वे सही क्रम में हैं, तो रुकें।
3. यदि नहीं, तो तत्व को उसके मूल तत्व से बदलें और पिछले चरण पर वापस लौटें।

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

आवश्यक संचालन की संख्या केवल उन स्तरों की संख्या पर निर्भर करती है जो नए तत्व को ढेर संपत्ति को संतुष्ट करने के लिए बढ़ाना चाहिए। इस प्रकार, सम्मिलन ऑपरेशन में सबसे खराब स्थिति वाली समय जटिलता होती है O(log n). यादृच्छिक ढेर के लिए, और बार-बार सम्मिलन के लिए, सम्मिलन ऑपरेशन में O(1) की औसत-केस जटिलता होती है। बाइनरी हीप इंसर्शन के उदाहरण के रूप में, मान लें कि हमारे पास एक अधिकतम-हीप है

और हम ढेर में संख्या 15 जोड़ना चाहते हैं। हम पहले 15 को एक्स द्वारा चिह्नित स्थान पर रखते हैं। हालाँकि, तब से ढेर संपत्ति का उल्लंघन होता है 15 > 8, इसलिए हमें 15 और 8 को स्वैप करने की आवश्यकता है। इसलिए, हमारे पास पहले स्वैप के बाद ढेर इस प्रकार दिखेगा:

हालाँकि ढेर संपत्ति का अभी भी उल्लंघन किया जा रहा है 15 > 11, इसलिए हमें फिर से स्वैप करने की आवश्यकता है:

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

निकालें

हीप संपत्ति को बनाए रखते हुए हीप से रूट को हटाने की प्रक्रिया (अधिकतम-हीप में अधिकतम तत्व या न्यूनतम-हीप में न्यूनतम तत्व को प्रभावी ढंग से निकालना) इस प्रकार है:

1. ढेर की जड़ को अंतिम स्तर पर अंतिम तत्व से बदलें।
2. नई जड़ की तुलना उसके बच्चों से करें; यदि वे सही क्रम में हैं, तो रुकें।
3. यदि नहीं, तो तत्व को उसके किसी एक बच्चे के साथ बदलें और पिछले चरण पर वापस लौटें। (मिन-हीप में इसके छोटे बच्चे और मैक्स-हीप में इसके बड़े बच्चे के साथ स्वैप करें।)

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

इसलिए, यदि हमारे पास पहले जैसा ही अधिकतम-ढेर है

हम 11 को हटाते हैं और इसे 4 से प्रतिस्थापित करते हैं।

अब हीप संपत्ति का उल्लंघन हो गया है क्योंकि 8, 4 से बड़ा है। इस मामले में, दो तत्वों, 4 और 8 की अदला-बदली, हीप संपत्ति को बहाल करने के लिए पर्याप्त है और हमें आगे तत्वों की अदला-बदली करने की आवश्यकता नहीं है:

नीचे की ओर बढ़ने वाले नोड को अधिकतम-हीप में अपने बड़े बच्चों के साथ स्वैप किया जाता है (मिन-हीप में इसे अपने छोटे बच्चे के साथ स्वैप किया जाएगा), जब तक कि यह अपनी नई स्थिति में हीप प्रॉपर्टी को संतुष्ट नहीं करता है। यह कार्यक्षमता 'मैक्स-हीपिफाई' फ़ंक्शन द्वारा प्राप्त की जाती है जैसा कि लंबाई लंबाई (ए) के ऐरे डेटा संरचना-समर्थित हीप ए के लिए छद्म कोड में नीचे परिभाषित किया गया है। A को 1 से शुरू करके अनुक्रमित किया गया है।

// मैक्स-हीप के लिए डाउन-हीप या हीपिफाई-डाउन ऑपरेशन करें
// ए: ढेर का प्रतिनिधित्व करने वाली एक सरणी, 1 से शुरू होकर अनुक्रमित
// i: नीचे ढेर लगाते समय शुरू होने वाला सूचकांक
'मैक्स-हीपिफाई'(ए, आई):
    बाएँ ← 2×i
    दाएं ← 2×i + 1
    सबसे बड़ा ← i
    
    'यदि' बायां ≤ लंबाई(ए) 'और' ए[बाएं] > ए[सबसे बड़ा] 'तब':
        सबसे बड़ा ← बायां

    'अगर' सही ≤ लंबाई(ए) 'और' ए[दाएं] > ए[सबसे बड़ा] 'तब':
        सबसे बड़ा ← सही
    
    'यदि' सबसे बड़ा ≠ मैं 'तब':
        'स्वैप' ए[i] और ए[सबसे बड़ा]
        'मैक्स-हीपिफाई' (ए, सबसे बड़ा)

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

सबसे खराब स्थिति में, नए रूट को प्रत्येक स्तर पर अपने बच्चे के साथ तब तक स्वैप करना पड़ता है जब तक कि यह ढेर के निचले स्तर तक नहीं पहुंच जाता है, जिसका अर्थ है कि डिलीट ऑपरेशन में पेड़ की ऊंचाई के सापेक्ष समय जटिलता है, या ओ (लॉग एन) ).

डालें फिर निकालें

किसी तत्व को सम्मिलित करना और फिर ढेर से निकालना ऊपर परिभाषित इन्सर्ट और एक्सट्रेक्ट फ़ंक्शंस को कॉल करने की तुलना में अधिक कुशलता से किया जा सकता है, जिसमें दोनों शामिल होंगे upheap और downheap कार्यवाही। इसके बजाय, हम बस एक कर सकते हैं downheap ऑपरेशन, इस प्रकार है:

1. तुलना करें कि क्या हम जिस वस्तु को आगे बढ़ा रहे हैं या ढेर के शीर्ष पर झांक रहा है वह बड़ा है (अधिकतम ढेर मानते हुए)
2. यदि ढेर की जड़ बड़ी हो:
   1. रूट को नए आइटम से बदलें
   2. जड़ से शुरू करके डाउन-हीपिफाई करना
3. अन्यथा, वह आइटम वापस कर दें जिसे हम आगे बढ़ा रहे हैं

पायथन (प्रोग्रामिंग भाषा) सम्मिलन और फिर निष्कर्षण के लिए हेप्पुशपॉप नामक एक ऐसा फ़ंक्शन प्रदान करता है, जिसे नीचे संक्षेप में प्रस्तुत किया गया है। माना जाता है कि हीप सरणी का पहला तत्व सूचकांक 1 पर है।

// एक नए आइटम को (अधिकतम) ढेर पर पुश करें और फिर परिणामी ढेर की जड़ निकालें।
// ढेर: ढेर का प्रतिनिधित्व करने वाली एक सरणी, 1 पर अनुक्रमित
// आइटम: सम्मिलित करने के लिए एक तत्व
// आइटम और ढेर की जड़ के बीच दोनों में से जो बड़ा है उसे लौटाता है।
'पुश-पॉप'(ढेर: सूची<टी>, आइटम: टी) -> टी:
    'यदि' ढेर खाली नहीं है 'और' ढेर[1] > आइटम 'तब': // < यदि न्यूनतम ढेर
        'स्वैप' ढेर[1] और आइटम
        _डाउनहीप (सूचकांक 1 से शुरू होने वाला ढेर)
    'वापसी के लिए वस्तु

एक समान फ़ंक्शन को पॉपिंग और फिर डालने के लिए परिभाषित किया जा सकता है, जिसे पायथन में heapreplace कहा जाता है:

// ढेर की जड़ निकालें, और एक नया आइटम पुश करें
// ढेर: ढेर का प्रतिनिधित्व करने वाली एक सरणी, 1 पर अनुक्रमित
// आइटम: सम्मिलित करने के लिए एक तत्व
// ढेर की वर्तमान जड़ लौटाता है
'बदलें'(ढेर: सूची<टी>, आइटम: टी) -> टी:
    'स्वैप' ढेर[1] और आइटम
    _डाउनहीप (सूचकांक 1 से शुरू होने वाला ढेर)
    'वापसी के लिए वस्तु

खोजें

एक मनमाना तत्व ढूँढने में O(n) समय लगता है।

हटाएं

किसी मनमाने तत्व को हटाना इस प्रकार किया जा सकता है:

1. सूचकांक खोजें $i$ जिस तत्व को हम हटाना चाहते हैं
2. इस तत्व को अंतिम तत्व से बदलें
3. ढेर संपत्ति को पुनर्स्थापित करने के लिए डाउन-हीपिफाई या अप-हीपिफाई करें। अधिकतम-हीप (न्यूनतम-हीप) में, अप-हीपिफ़ाइ की आवश्यकता केवल तब होती है जब तत्व की नई कुंजी होती है $i$ पिछले वाले से बड़ा (छोटा) है क्योंकि केवल मूल तत्व की ढेर-संपत्ति का उल्लंघन हो सकता है। यह मानते हुए कि ढेर-संपत्ति तत्व के बीच मान्य थी $i$ और तत्व स्वैप से पहले उसके बच्चे, अब बड़े (छोटे) कुंजी मान द्वारा इसका उल्लंघन नहीं किया जा सकता है। जब नई कुंजी पिछली कुंजी से कम (अधिक) होती है तो केवल डाउन-हीपिफाई की आवश्यकता होती है क्योंकि हीप-प्रॉपर्टी का उल्लंघन केवल चाइल्ड तत्वों में ही हो सकता है।

कुंजी घटाएँ या बढ़ाएँ

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

कमी कुंजी इस प्रकार की जा सकती है:

1. उस तत्व का सूचकांक ढूंढें जिसे हम संशोधित करना चाहते हैं
2. नोड का मान घटाएं
3. ढेर संपत्ति को पुनर्स्थापित करने के लिए डाउन-हीपिफाई (अधिकतम ढेर मानकर)।

कुंजी को इस प्रकार बढ़ाया जा सकता है:

1. उस तत्व का सूचकांक ढूंढें जिसे हम संशोधित करना चाहते हैं
2. नोड का मान बढ़ाएँ
3. ढेर संपत्ति को पुनर्स्थापित करने के लिए ऊपर-ढेरीकरण (अधिकतम ढेर मानकर)।

ढेर बनाना

की एक श्रृंखला से ढेर बनाना n इनपुट तत्वों को एक खाली ढेर से शुरू करके, फिर क्रमिक रूप से प्रत्येक तत्व को सम्मिलित करके किया जा सकता है। यह दृष्टिकोण, जिसे बाइनरी हीप्स के आविष्कारक के नाम पर विलियम्स विधि कहा जाता है, आसानी से चलता हुआ देखा जाता है O(n log n) समय: यह कार्यान्वित होता है n पर सम्मिलन O(log n)प्रत्येक की लागत।

हालाँकि, विलियम्स की विधि इष्टतम नहीं है। एक तेज़ विधि (रॉबर्ट डब्ल्यू फ़्लॉइड के कारण) आकृति गुण का सम्मान करते हुए मनमाने ढंग से तत्वों को बाइनरी ट्री पर रखकर शुरू होता है (पेड़ को एक सरणी द्वारा दर्शाया जा सकता है, नीचे देखें)। फिर सबसे निचले स्तर से शुरू करके ऊपर की ओर बढ़ते हुए, प्रत्येक उपवृक्ष की जड़ को विलोपन एल्गोरिथ्म के अनुसार नीचे की ओर तब तक छानें जब तक कि ढेर गुण बहाल न हो जाए। अधिक विशेष रूप से यदि सभी उपवृक्ष कुछ ऊंचाई से शुरू होते हैं $h$ पहले ही ढेर लगा दिया गया है (सबसे निचले स्तर के अनुरूप)। $h=0$), ऊंचाई पर पेड़ $h+1$ अधिकतम-ढेर बनाते समय, या न्यूनतम-ढेर बनाते समय न्यूनतम मूल्यवान बच्चों के पथ पर उनकी जड़ों को नीचे भेजकर ढेर किया जा सकता है। इस प्रक्रिया में लगता है $O(h)$ प्रति नोड संचालन (स्वैप)। इस विधि में अधिकांश ढेरीकरण निचले स्तरों पर होता है। चूंकि ढेर की ऊंचाई है $\lfloor \log n\rfloor$, ऊंचाई पर नोड्स की संख्या $h$ है $\leq {\frac {2^{\lfloor \log n\rfloor }}{2^{h}}}\leq {\frac {n}{2^{h}}}$. इसलिए, सभी उपवृक्षों को ढेर करने की लागत है:

${\begin{aligned}\sum _{h=0}^{\lfloor \log n\rfloor }{\frac {n}{2^{h}}}O(h)&=O\left(n\sum _{h=0}^{\lfloor \log n\rfloor }{\frac {h}{2^{h}}}\right)\\&=O\left(n\sum _{h=0}^{\infty }{\frac {h}{2^{h}}}\right)\\&=O(n)\end{aligned}}$

यह इस तथ्य का उपयोग करता है कि दी गई अनंत श्रृंखला (गणित) ${\textstyle \sum _{i=0}^{\infty }i/2^{i}}$ अभिसरण श्रृंखला.

उपरोक्त का सटीक मान (ढेर निर्माण के दौरान तुलना की सबसे खराब स्थिति वाली संख्या) इसके बराबर माना जाता है:

$2n-2s_{2}(n)-e_{2}(n)$,

कहाँ s₂(n) हथौड़ा चलाना वजन है n और e₂(n) का प्रतिपादक है 2 के अभाज्य गुणनखंडन में n.

औसत मामले का विश्लेषण करना अधिक जटिल है, लेकिन इसे स्पर्शोन्मुख दृष्टिकोण से दिखाया जा सकता है 1.8814 n − 2 log₂n + O(1) तुलना. बिल्ड-मैक्स-हीप फ़ंक्शन जो इसके बाद आता है, एक सरणी ए को परिवर्तित करता है जो संपूर्ण को संग्रहीत करता है बार-बार बॉटम-अप तरीके से मैक्स-हीपिफ़ाई (अधिकतम-हीप के लिए डाउन-हीपिफ़ाई) का उपयोग करके अधिकतम-हीप में एन नोड्स के साथ बाइनरी ट्री। सरणी तत्वों को अनुक्रमित किया गया floor(n/2) + 1, floor(n/2) + 2, ..., एन सभी पत्तियाँ पेड़ के लिए हैं (यह मानते हुए कि सूचकांक 1 से शुरू होते हैं) - इस प्रकार प्रत्येक एक-तत्व का ढेर है, और इसे नीचे-ढेर करने की आवश्यकता नहीं है। 'बिल्ड-मैक्स-हीप' चलता है शेष वृक्ष नोड्स में से प्रत्येक पर 'मैक्स-हीपिफाई'।

'बिल्ड-मैक्स-हीप' (ए):
    'प्रत्येक सूचकांक के लिए' मैं 'से' मंजिल (लंबाई (ए)/2) 'नीचे' 1 'करें:'
        'मैक्स-हीपिफाई'(ए, आई)

ढेर कार्यान्वयन

एक सरणी में संग्रहीत एक छोटा पूर्ण बाइनरी ट्री

बाइनरी हीप और सरणी कार्यान्वयन के बीच तुलना।

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

मान लीजिए n ढेर में तत्वों की संख्या है और i ढेर को संग्रहीत करने वाले सरणी का एक मनमाना वैध सूचकांक है। यदि पेड़ की जड़ सूचकांक 0 पर है, वैध सूचकांक 0 से एन - 1 के साथ, तो सूचकांक i पर प्रत्येक तत्व a है

• सूचकांक 2i + 1 और 2i + 2 पर बच्चे
• इंडेक्स फर्श समारोह पर इसका मूल ((i - 1) / 2)।

वैकल्पिक रूप से, यदि पेड़ की जड़ सूचकांक 1 पर है, वैध सूचकांक 1 से एन के साथ, तो सूचकांक i पर प्रत्येक तत्व a है

• सूचकांक 2i और 2i +1 पर बच्चे
• इंडेक्स फ़्लोर फ़ंक्शन (i/2) पर इसका मूल।

इस कार्यान्वयन का उपयोग हीप्सॉर्ट एल्गोरिदम में किया जाता है जो हीप को संग्रहीत करने के लिए इनपुट सरणी को आवंटित स्थान का पुन: उपयोग करता है (यानी एल्गोरिदम इन-प्लेस एल्गोरिदम|इन-प्लेस किया जाता है)। यह कार्यान्वयन प्राथमिकता कतार के रूप में भी उपयोगी है। जब एक गतिशील सरणी का उपयोग किया जाता है, तो असीमित संख्या में आइटमों का सम्मिलन संभव है। upheap ई>या downheap संचालन को एक सरणी के संदर्भ में निम्नानुसार बताया जा सकता है: मान लीजिए कि ढेर संपत्ति सूचकांक बी, बी + 1, ..., ई के लिए है। सिफ्ट-डाउन फ़ंक्शन हीप प्रॉपर्टी को b−1, b, b+1, ..., e तक बढ़ाता है। केवल सूचकांक i = b−1 हीप संपत्ति का उल्लंघन कर सकता है। मान लें कि j श्रेणी b, ..., e के भीतर a[i] (अधिकतम-ढेर के लिए, या न्यूनतम-ढेर के लिए सबसे छोटे बच्चे) के सबसे बड़े बच्चे का सूचकांक है। (यदि ऐसा कोई सूचकांक मौजूद नहीं है क्योंकि 2i > e तो ढेर संपत्ति नई विस्तारित सीमा के लिए बनी रहती है और कुछ भी करने की आवश्यकता नहीं होती है।) a[i] और a[j] मानों की अदला-बदली करके स्थिति i के लिए हीप प्रॉपर्टी स्थापित की जाती है। इस बिंदु पर, एकमात्र समस्या यह है कि ढेर संपत्ति सूचकांक जे के लिए मान्य नहीं हो सकती है। सिफ्ट-डाउन फ़ंक्शन को पूँछ प्रत्यावर्तन |टेल-रिकर्सिव रूप से इंडेक्स जे पर तब तक लागू किया जाता है जब तक कि सभी तत्वों के लिए हीप प्रॉपर्टी स्थापित नहीं हो जाती।

सिफ्ट-डाउन फ़ंक्शन तेज़ है। प्रत्येक चरण में इसे केवल दो तुलनाओं और एक स्वैप की आवश्यकता होती है। सूचकांक मान जहां यह काम कर रहा है प्रत्येक पुनरावृत्ति में दोगुना हो जाता है, ताकि अधिकतम लॉग में₂ ई कदम आवश्यक हैं.

बड़े ढेर और आभासी मेमोरी का उपयोग करने के लिए, उपरोक्त योजना के अनुसार तत्वों को एक सरणी में संग्रहीत करना अक्षम है: (लगभग) हर स्तर एक अलग पृष्ठ (कंप्यूटर मेमोरी) में है। बी-ढेर ्स बाइनरी हीप्स हैं जो सबट्रीज़ को एक पेज में रखते हैं, जिससे एक्सेस किए गए पेजों की संख्या दस गुना तक कम हो जाती है। दो बाइनरी ढेरों को मर्ज करने की प्रक्रिया समान आकार के ढेरों के लिए Θ(n) लेती है। सबसे अच्छा आप जो कर सकते हैं वह है (सरणी कार्यान्वयन के मामले में) बस दो ढेर सारणियों को जोड़ना और परिणाम का ढेर बनाना। एन तत्वों पर एक ढेर को ओ (लॉग एन लॉग के) कुंजी तुलनाओं का उपयोग करके, या पॉइंटर-आधारित कार्यान्वयन के मामले में, ओ (लॉग एन लॉग के) समय में, के तत्वों पर ढेर के साथ विलय किया जा सकता है। एक नए दृश्य के आधार पर, n तत्वों पर एक ढेर को क्रमशः k और n-k तत्वों पर दो ढेरों में विभाजित करने के लिए एक एल्गोरिदम उप-ढेरों के एक क्रमबद्ध संग्रह के रूप में ढेरों को प्रस्तुत किया गया था। एल्गोरिथम को O(log n * log n) तुलना की आवश्यकता होती है। यह दृश्य ढेरों के विलय के लिए एक नया और वैचारिक रूप से सरल एल्गोरिदम भी प्रस्तुत करता है। जब विलय एक सामान्य कार्य है, तो एक अलग ढेर कार्यान्वयन की सिफारिश की जाती है, जैसे द्विपद ढेर, जिसे ओ (लॉग एन) में विलय किया जा सकता है।

इसके अतिरिक्त, एक बाइनरी हीप को पारंपरिक बाइनरी ट्री डेटा संरचना के साथ कार्यान्वित किया जा सकता है, लेकिन तत्व जोड़ते समय बाइनरी हीप पर अंतिम स्तर पर आसन्न तत्व को खोजने में एक समस्या होती है। इस तत्व को एल्गोरिदमिक रूप से या नोड्स में अतिरिक्त डेटा जोड़कर निर्धारित किया जा सकता है, जिसे ट्री थ्रेडिंग कहा जाता है - केवल बच्चों के संदर्भों को संग्रहीत करने के बजाय, हम नोड के क्रम में उत्तराधिकारी को भी संग्रहीत करते हैं।

बिग ओ नोटेशन में सबसे छोटे और सबसे बड़े दोनों तत्वों के निष्कर्षण को संभव बनाने के लिए ढेर संरचना को संशोधित करना संभव है|$O$$(\log n)$ समय। ऐसा करने के लिए, पंक्तियाँ न्यूनतम ढेर और अधिकतम ढेर के बीच वैकल्पिक होती हैं। एल्गोरिदम लगभग समान हैं, लेकिन, प्रत्येक चरण में, वैकल्पिक तुलनाओं के साथ वैकल्पिक पंक्तियों पर विचार करना चाहिए। प्रदर्शन लगभग सामान्य एकल दिशा ढेर के समान है। इस विचार को न्यूनतम-अधिकतम-मध्यम ढेर तक सामान्यीकृत किया जा सकता है।

सूचकांक समीकरणों की व्युत्पत्ति

एक सरणी-आधारित ढेर में, नोड के बच्चों और माता-पिता को नोड के सूचकांक पर सरल अंकगणित के माध्यम से स्थित किया जा सकता है। यह खंड सूचकांक 0 पर जड़ वाले ढेरों के लिए प्रासंगिक समीकरण प्राप्त करता है, सूचकांक 1 पर जड़ वाले ढेरों पर अतिरिक्त नोट्स के साथ।

भ्रम से बचने के लिए, हम नोड के स्तर को जड़ से उसकी दूरी के रूप में परिभाषित करेंगे, जैसे कि जड़ स्वयं स्तर 0 पर हो।

चाइल्ड नोड्स

सूचकांक पर स्थित एक सामान्य नोड के लिए i (0 से शुरू करके), हम पहले इसके सही बच्चे का सूचकांक प्राप्त करेंगे, ${\text{right}}=2i+2$.

चलो नोड i स्तर पर स्थित हो L, और ध्यान दें कि कोई भी स्तर l बिल्कुल शामिल है $2^{l}$ नोड्स. इसके अलावा, बिल्कुल हैं $2^{l+1}-1$ परतों तक और परत सहित परतों में निहित नोड्स l (बाइनरी अंकगणित के बारे में सोचें; 0111...111 = 1000...000 - 1)। क्योंकि रूट 0 पर संग्रहित है kवें नोड को इंडेक्स पर संग्रहीत किया जाएगा $(k-1)$. इन अवलोकनों को एक साथ रखने पर परत में अंतिम नोड के सूचकांक के लिए निम्नलिखित अभिव्यक्ति प्राप्त होती है l.

${\text{last}}(l)=(2^{l+1}-1)-1=2^{l+1}-2$

उसको रहनो दो j नोड के बाद नोड i परत L में, ऐसा कि

${\begin{alignedat}{2}i=&\quad {\text{last}}(L)-j\\=&\quad (2^{L+1}-2)-j\\\end{alignedat}}$

इनमें से प्रत्येक j नोड्स में बिल्कुल 2 बच्चे होने चाहिए, इसलिए होना ही चाहिए $2j$ नोड्स को अलग करना i इसकी परत के अंत से दायाँ बच्चा ($L+1$).

${\begin{alignedat}{2}{\text{right}}=&\quad {\text{last(L + 1)}}-2j\\=&\quad (2^{L+2}-2)-2j\\=&\quad 2(2^{L+1}-2-j)+2\\=&\quad 2i+2\end{alignedat}}$

आवश्यकता अनुसार।

यह देखते हुए कि किसी भी नोड का बायां बच्चा हमेशा उसके दाएं बच्चे से 1 स्थान पहले होता है, हमें मिलता है ${\text{left}}=2i+1$.

यदि रूट 0 के बजाय इंडेक्स 1 पर स्थित है, तो प्रत्येक स्तर में अंतिम नोड इंडेक्स पर है $2^{l+1}-1$. इसका प्रयोग सम्पूर्ण पैदावार में करें ${\text{left}}=2i$ और ${\text{right}}=2i+1$ उन ढेरों के लिए जिनकी जड़ 1 है।

मूल नोड

प्रत्येक नोड या तो अपने माता-पिता का बायाँ या दायाँ बच्चा है, इसलिए हम जानते हैं कि निम्नलिखित में से कोई भी सत्य है।

1. $i=2\times ({\text{parent}})+1$
2. $i=2\times ({\text{parent}})+2$

इस तरह,

${\text{parent}}={\frac {i-1}{2}}\;{\textrm {or}}\;{\frac {i-2}{2}}$

अब अभिव्यक्ति पर विचार करें $\left\lfloor {\dfrac {i-1}{2}}\right\rfloor$.

यदि नोड $i$ यदि कोई बायाँ बच्चा है, तो यह तुरंत परिणाम देता है, हालाँकि, यदि नोड है तो यह सही परिणाम भी देता है $i$ एक सही बच्चा है. इस मामले में, $(i-2)$ सम होना चाहिए, और इसलिए $(i-1)$ अजीब होना चाहिए.

${\begin{alignedat}{2}\left\lfloor {\dfrac {i-1}{2}}\right\rfloor =&\quad \left\lfloor {\dfrac {i-2}{2}}+{\dfrac {1}{2}}\right\rfloor \\=&\quad {\frac {i-2}{2}}\\=&\quad {\text{parent}}\end{alignedat}}$

इसलिए, चाहे कोई नोड बायां या दायां बच्चा हो, उसके माता-पिता को अभिव्यक्ति द्वारा पाया जा सकता है:

${\text{parent}}=\left\lfloor {\dfrac {i-1}{2}}\right\rfloor$

संबंधित संरचनाएं

चूँकि ढेर में भाई-बहनों का क्रम ढेर संपत्ति द्वारा निर्दिष्ट नहीं किया जाता है, एक एकल नोड के दो बच्चों को स्वतंत्र रूप से तब तक बदला जा सकता है जब तक कि ऐसा करने से आकार संपत्ति का उल्लंघन न हो (फँसाना के साथ तुलना करें)। हालाँकि, ध्यान दें कि सामान्य सरणी-आधारित हीप में, केवल बच्चों की अदला-बदली करने से हीप संपत्ति को बनाए रखने के लिए बच्चों के उप-वृक्ष नोड्स को स्थानांतरित करने की भी आवश्यकता हो सकती है।

बाइनरी हीप डी-एरी ढेर का एक विशेष मामला है जिसमें डी = 2 है।

चलने के समय का सारांश

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

Operation	find-min	delete-min	insert	decrease-key	meld
Binary	Θ(1)	Θ(log n)	O(log n)	O(log n)	Θ(n)
Leftist	Θ(1)	Θ(log n)	Θ(log n)	O(log n)	Θ(log n)
Binomial	Θ(1)	Θ(log n)	Θ(1)	Θ(log n)	O(log n)
Fibonacci	Θ(1)	O(log n)	Θ(1)	Θ(1)	Θ(1)
Pairing	Θ(1)	O(log n)	Θ(1)	o(log n)	Θ(1)
Brodal	Θ(1)	O(log n)	Θ(1)	Θ(1)	Θ(1)
Rank-pairing	Θ(1)	O(log n)	Θ(1)	Θ(1)	Θ(1)
Strict Fibonacci	Θ(1)	O(log n)	Θ(1)	Θ(1)	Θ(1)
2–3 heap	O(log n)	O(log n)	O(log n)	Θ(1)	?

यह भी देखें

• ढेर (डेटा संरचना)
• ढेर बनाएं और छांटें

बाहरी संबंध

• Open Data Structures - Section 10.1 - BinaryHeap: An Implicit Binary Tree, Pat Morin
• Implementation of binary max heap in C by Robin Thomas
• Implementation of binary min heap in C by Robin Thomas