बाइनरी हीप

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 में जे.डब्ल्यू.जे. विलियम्स द्वारा 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) के सरणी डेटा संरचना-समर्थित हीप 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. हीप गुण को पुनर्स्थापित करने के लिए अप-हीपिफाइ (अधिकतम हीप मानकर)।

हीप बनाना

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

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

        Max-Heapify(A, i)

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

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

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

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

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

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

इस प्रकार से वैकल्पिक रूप से, यदि ट्री की रूट सूचकांक 1 पर है, वैध सूचकांक 1 से n के साथ, तो सूचकांक 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 पर तब तक लागू किया जाता है जब तक कि सभी अवयवों के लिए हीप गुण स्थापित नहीं हो जाती है।

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

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

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

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

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

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

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

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

चाइल्ड नोड

अतः सूचकांक पर स्थित सामान्य नोड i के लिए (0 से प्रारम्भ करके), हम पहले इसके दाएं चाइल्ड, ${\text{right}}=2i+2$ का सूचकांक प्राप्त करेंगे।

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

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

मान लीजिए कि परत L में नोड i के बाद j नोड हैं, जैसे कि

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

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

${\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$

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

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

इस प्रकार से बाइनरी हीप डी-एरी हीप का विशेष स्थिति है जिसमें d = 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