डेटा संरचनाएं: बाइनरी हीप

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



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

परिचय

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







बाइनरी हीप को वन-डायमेंशनल ऐरे के रूप में स्टोर करना सुविधाजनक है, इंडेक्स के साथ वर्टेक्स के बाएं वंशज के साथ इंडेक्स 2*i+1



, और राइट वन 2*i+2



। पेड़ की जड़ इंडेक्स 0. के साथ एक तत्व है। बाइनरी हीप की ऊंचाई पेड़ की ऊंचाई के बराबर है, अर्थात ₂ एन लॉग करें, जहां N



सरणी में तत्वों की संख्या है।



मैं C # में एक क्लास खाली दूंगा:

 public class BinaryHeap { private List<int> list; public int heapSize { get { return this.list.Count(); } } }
      
      

        
        
        
      

    
        
        
        
      
      

        
        
        
      

    
     

आइटम जोड़ें

नए तत्व को सरणी में अंतिम स्थान पर जोड़ा गया है, heapSize



, heapSize



इंडेक्स के साथ स्थिति:







यह संभव है कि यह ढेर की मुख्य संपत्ति का उल्लंघन करेगा, क्योंकि नया तत्व माता-पिता से बड़ा हो सकता है। इस मामले में, आपको नए तत्व एक स्तर (माता-पिता के साथ बदलाव) को "ऊपर" उठाना चाहिए जब तक कि ढेर की मुख्य संपत्ति नहीं देखी जाती है:











दूसरे शब्दों में, एक नया तत्व "पॉप अप", "ऊपर" धकेलता है, जब तक कि यह अपनी जगह नहीं लेता है। एल्गोरिथ्म की जटिलता बाइनरी हीप की ऊंचाई से अधिक नहीं है (चूंकि "लिफ्ट" की संख्या पेड़ की ऊंचाई से अधिक नहीं है), अर्थात यह ओ (लॉग ₂ एन) के बराबर है।

 public void add(int value) { list.Add(value); int i = heapSize - 1; int parent = (i - 1) / 2; while (i > 0 && list[parent] < list[i]) { int temp = list[i]; list[i] = list[parent]; list[parent] = temp; i = parent; parent = (i - 1) / 2; } }
      
      

        
        
        
      

    
        
        
        
      
      

        
        
        
      

    
     

बाइनरी हीप ऑर्डरिंग

पहले से ही निर्मित बाइनरी हीप के साथ अन्य संचालन के दौरान, ढेर की मुख्य संपत्ति का भी उल्लंघन हो सकता है: शीर्ष अपने वंश से छोटा हो सकता है।







heapify



विधि एक पेड़ के लिए मूल ढेर संपत्ति को i-th शीर्ष पर एक जड़ के साथ पुनर्स्थापित करती है, बशर्ते कि दोनों उपप्रकार उसे संतुष्ट कर सकें। इसके लिए, जब तक मुख्य संपत्ति को बहाल नहीं किया जाता है (तब तक प्रक्रिया समाप्त हो जाती है (जब कोई वंशज नहीं है, तो उसके बड़े माता-पिता)। यह देखना आसान है कि इस एल्गोरिथ्म की जटिलता भी ओ (लॉग ₂ एन) के बराबर है।

 public void heapify(int i) { int leftChild; int rightChild; int largestChild; for (; ; ) { leftChild = 2 * i + 1; rightChild = 2 * i + 2; largestChild = i; if (leftChild < heapSize && list[leftChild] > list[largestChild]) { largestChild = leftChild; } if (rightChild < heapSize && list[rightChild] > list[largestChild]) { largestChild = rightChild; } if (largestChild == i) { break; } int temp = list[i]; list[i] = list[largestChild]; list[largestChild] = temp; i = largestChild; } }
      
      

        
        
        
      

    
        
        
        
      
      

        
        
        
      

    
     

एक बाइनरी हीप का निर्माण

अव्यवस्थित सरणी से एक गुच्छा बनाने का सबसे स्पष्ट तरीका बदले में अपने सभी तत्वों को जोड़ना है। इस तरह के एल्गोरिदम का समय अनुमान हे (एन लॉग ₂ एन) है। हालांकि, आप तेजी से एक गुच्छा का निर्माण कर सकते हैं - ओ (एन) के लिए। पहले आपको सरणी के सभी तत्वों से एक पेड़ बनाने की जरूरत है, न कि ढेर की मुख्य संपत्ति का निरीक्षण करने के बारे में, और फिर सभी heapify



लिए heapify



विधि को कॉल करें, heapify



कम से कम एक वंशज हो (चूंकि एक वंश के बिना एक शीर्ष से मिलकर उप-क्रम पहले से ही ऑर्डर किए गए हैं)। पहले heapSize/2



वंशज होने की गारंटी दी जाती है।

 public void buildHeap(int[] sourceArray) { list = sourceArray.ToList(); for (int i = heapSize / 2; i >= 0; i--) { heapify(i); } }
      
      

        
        
        
      

    
        
        
        
      
      

        
        
        
      

    
     

अधिकतम तत्व का निष्कर्षण (निष्कासन)

आदेशित max-heap



अधिकतम तत्व हमेशा रूट में संग्रहीत होता है। आप अंतिम तत्व को उसके स्थान पर heapify



और पूरे पेड़ को ऑर्डर करने वाले रूट के लिए heapify



कहकर अधिकतम तत्व को हटाने के बाद बाइनरी हीप के ऑर्डर को पुनर्स्थापित कर सकते हैं।

 public int getMax() { int result = list[0]; list[0] = list[heapSize - 1]; list.RemoveAt(heapSize - 1); return result; }
      
      

        
        
        
      

    
        
        
        
      
      

        
        
        
      

    
     

बाइनरी हीप सॉर्ट

ध्यान दें कि आप पहले से एक बाइनरी हीप का निर्माण करके एक सरणी को सॉर्ट कर सकते हैं, और फिर क्रमिक रूप से अधिकतम तत्वों को निकाल सकते हैं। आइए ऐसे तत्व की समय जटिलता का मूल्यांकन करें: ढेर निर्माण - ओ (एन), N



तत्वों का निष्कर्षण - ओ (एन लॉग ₂ ए)। इसलिए, अंतिम स्कोर ओ (एन लॉग ₂ एन) है। इस स्थिति में, सरणी के लिए अतिरिक्त मेमोरी का उपयोग नहीं किया जाता है।

 public void heapSort(int[] array) { buildHeap(array); for (int i = array.Length - 1; i >= 0; i--) { array[i] = getMax(); heapify(0); } }
      
      

        
        
        
      

    
        
        
        
      
      

        
        
        
      

    
     

निष्कर्ष

इस प्रकार, बाइनरी हीप में एक लॉगरिदमिक ऊंचाई (वर्टीकल की संख्या के सापेक्ष) की एक पेड़ संरचना होती है, जिससे आप लॉगरिदमिक समय में तत्वों को जोड़ सकते हैं और निरंतर समय में अधिकतम प्राथमिकता के साथ एक तत्व निकाल सकते हैं। उसी समय, बाइनरी हीप को लागू करना आसान होता है और अतिरिक्त मेमोरी की आवश्यकता नहीं होती है।