बाइनरी हीप

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)

File:Max-Heap.svg

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

Error creating thumbnail:

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

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

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

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

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

हीप परिचालन

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

निवेशन

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

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

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

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

बाइनरी हीप क्षेपण के उदाहरण के रूप में, मान लें कि हमारे गुण अधिकतम-हीप

File:Heap add step1.svg

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

File:Heap add step2.svg

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

File:Heap add step3.svg

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

निष्कर्षण

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

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

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

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

File:Heap delete step0.svg

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

File:Heap remove step1.svg

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

File:Heap remove step2.svg

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

// Perform a down-heap or heapify-down operation for a max-heap
// A: an array representing the heap, indexed starting at 1
// i: the index to start at when heapifying down

Max-Heapify(A, i):
    left ← 2×i

    right ← 2×i + 1

    largest ← i
    
    if left ≤ length(A) and A[left] > A[largest] then:

        largest ← left

    if right ≤ length(A) and A[right] > A[largest] then:

        largest ← right
    
    if largest ≠ i then:

        swap A[i] and A[largest]
        Max-Heapify(A, largest)

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

सबसे निकृष्ट स्थिति में, नवीन रूट को प्रत्येक स्तर पर अपने बच्चे के साथ तब तक स्वैप करना पड़ता है जब तक कि यह हीप के निम्न स्तर तक नहीं पहुंच जाता है, जिसका अर्थ है कि डिलीट परिचालन में ट्री की ऊंचाई के सापेक्ष समय जटिलता है, या O(log n)।

निवेशन फिर निष्कर्षण

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

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

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

// Push a new item to a (max) heap and then extract the root of the resulting heap. 
// heap: an array representing the heap, indexed at 1
// item: an element to insert
// Returns the greater of the two between item and the root of heap.

Push-Pop(heap: List<T>, item: T) -> T:
    if heap is not empty and heap[1] > item then:  // < if min heap

        swap heap[1] and item
        _downheap(heap starting from index 1)
    return item

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

// Extract the root of the heap, and push a new item 
// heap: an array representing the heap, indexed at 1
// item: an element to insert
// Returns the current root of heap

swap heap[1] and item
    _downheap(heap starting from index 1)
    return item

सर्च

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

विलोप

किसी यादृच्छिक अवयव को हटाना इस प्रकार किया जा सकता है:

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

न्यूनता या वृद्धि कुंजी

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

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

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

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

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

हीप बनाना

एन इनपुट अवयवों की एक सरणी से एक हीप का निर्माण एक रिक्त हीप से प्रारम्भ करके, फिर क्रमिक रूप से प्रत्येक अवयव को सम्मिलित करके किया जा सकता है। यह दृष्टिकोण, जिसे बाइनरी हीप के आविष्कारक के नाम पर विलियम्स विधि कहा जाता है, सरलता से O(n log n) समय में चलता हुआ देखा जाता है: यह प्रत्येक O(log n) लागत पर 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) तुलना से दिखाया जा सकता है।

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

Build-Max-Heap (A):
    for each index i from floor(length(A)/2) downto 1 do:

        Max-Heapify(A, i)

हीप कार्यान्वयन

File:Binary tree in array.svg

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

File:Binary Heap with Array Implementation.JPG

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

हीप को सामान्यतः सरणी डेटा संरचना के साथ कार्यान्वित किया जाता है। किसी भी बाइनरी ट्री को सरणी में संग्रहीत किया जा सकता है, परन्तु क्योंकि बाइनरी हीप सदैव पूर्ण बाइनरी ट्री होता है, इसे संहत रूप से संग्रहीत किया जा सकता है। सूचक (कंप्यूटर प्रोग्रामिंग) के लिए किसी स्थान की आवश्यकता नहीं है; इसके अतिरिक्त, प्रत्येक नोड के माता-पिता और बच्चों को सरणी सूचकांकों पर अंकगणित द्वारा पाया जा सकता है। ये गुण इस हीप कार्यान्वयन को अंतर्निहित डेटा संरचना या वंशावली सूची का सरल उदाहरण बनाते हैं। विवरण मूल स्थिति पर निर्भर करते हैं, जो इसके स्थान पर कार्यान्वयन के लिए उपयोग की जाने वाली प्रोग्रामिंग भाषा की बाधाओं या प्रोग्रामर की प्राथमिकता पर निर्भर हो सकते हैं। विशेष रूप से, कभी-कभी अंकगणित को सरल बनाने के लिए मूल को सूचकांक 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 संचालन को सरणी के संदर्भ में निम्नानुसार बताया जा सकता है: मान लीजिए कि हीप गुण सूचकांक b, b + 1, ..., e के लिए है। सिफ्ट-निम्न फलन हीप गुण को b−1, b, b+1, ..., e तक बढ़ाता है। मात्र सूचकांक i = b−1 हीप गुण का उल्लंघन कर सकता है।

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

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

बड़े हीप और आभासी मेमोरी का उपयोग करने के लिए, उपरोक्त योजना के अनुसार अवयवों को सरणी में संग्रहीत करना अक्षम है: (लगभग) हर स्तर अलग पृष्ठ (कंप्यूटर मेमोरी) में है। बी-हीप ्स बाइनरी हीप हैं जो सबट्रीज़ को पेज में रखते हैं, जिससे एक्सेस किए गए पेजों की संख्या दस गुना तक कम हो जाती है। दो बाइनरी ढेरों को मर्ज करने की प्रक्रिया समान आकार के ढेरों के लिए Θ(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