कमजोर ढेर छँटाई

यह लेख EDISON के समर्थन से लिखा गया था।

हम एम्बेडेड सॉफ़्टवेयर के निर्माण के साथ-साथ वेब एप्लिकेशन और साइटों के विकास में लगे हुए हैं ।

हम एल्गोरिदम के सिद्धांत से प्यार करते हैं! ;-)

कमजोर ढेर

तुलनाओं की संख्या कम से कम करना

बाजीगर के वंशज

एक कमजोर ढेर का निर्माण

1. यदि वंशज के अपने वंशज हैं, तो उसके बाएं और दाएं उपप्रकारों को स्वैप करें (यानी इस तत्व के लिए बीआईटी सरणी में 0/1 स्विच करें)।
2. वंशज नोड और पूर्वज नोड के मूल्यों का आदान-प्रदान करें।

एक कमजोर ढेर को पार्स करना

कमजोर ढेर सॉर्टिंग :: कमजोर ढेर सॉर्ट

• I. :
  • I.1. -.
  • I.2. «» .
  • I.3. .
  • I.4. , :
    • I.4.. ( ⇔ ) , .
    • I.4.. «» .
• II. , :
  • II.1. .
  • II.2. . .
  • II.3. , . :
    • II.3.. .
    • II.3.. , .
    • II.3.. , , :
      • II.3.c. 1। हम स्वैप (बाएं) दाएं) नोड के लिए वंशज के साथ जोड़ते हैं, जिसमें वर्तमान बाएं वंशज स्थित है।
      • II.3.c.2। हम वर्तमान बाएं बच्चे के साथ ढेर जड़ और नोड को बदलते हैं।
  • II.4। कमजोर ढेर की जड़ में फिर से सरणी के शेष भाग के लिए अधिकतम तत्व है। हम पैराग्राफ II.1 पर वापस लौटते हैं और प्रक्रिया को तब तक दोहराते हैं जब तक कि सभी तत्व हल न हो जाएं।

C ++ कोड

#define GETFLAG(r, x) ((r[(x) >> 3] >> ((x) & 7)) & 1)
#define TOGGLEFLAG(r, x) (r[(x) >> 3] ^= 1 << ((x) & 7))

void WeakHeap::WeakHeapMerge(unsigned char *r, int i, int j) {
  if (wheap[i] < wheap[j]) {//""  ?
    //  ,   
    //( "",   "")
    TOGGLEFLAG(r, j);
    //  ""  
    swap(wheap[i], wheap[j]);
  }
}

void WeakHeap::WeakHeapSort() {
  int n = Size();
  if(n > 1) {
		
    int i, j, x, y, Gparent;
    int s = (n + 7) / 8;
    unsigned char * r = new unsigned char [s];
		
    //  ,    
    // "",   ""
    for(i = 0; i < n / 8; ++i) r[i] = 0;
		
    //   
    for(i = n - 1; i > 0; --i) {
      j = i;
      //    , 
      //   ""  
      while ((j & 1) == GETFLAG(r, j >> 1)) j >>= 1;
      //       ""  
      Gparent = j >> 1;
      //  ,   
      //   ""
      WeakHeapMerge(r, Gparent, i);
    }
		
    //      -->
    //  -->    
    for(i = n - 1; i >= 2; --i) {
      //      
      //       
      swap(wheap[0], wheap[i]);
      x = 1;
      //    "" 
      while((y = 2 * x + GETFLAG(r, x)) < i) x = y;
      //  ""     
      //        
      while(x > 0) {
        WeakHeapMerge(r, 0, x);
        x >>= 1;
      }
    }
    //  -   
    //    
    swap(wheap[0], wheap[1]);
    delete[] r;
  }
}

अतिरिक्त स्मृति जटिलता

समय की जटिलता

पूरी शिफ्टिंग

द्विपद ढेर

गुप्त एल्गोरिथ्म

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

अगली श्रृंखला में

संदर्भ

श्रृंखला लेख:

• एक्सेल आवेदन AlgoLab.xlsm
• एक्सचेंज सॉर्ट
• निवेशन शॉर्ट्स
• चयन के आधार पर छाँटें
  • हीप शॉर्ट्स: एन-पिरामिड
  • हीप सॉर्ट्स: लियोनार्डो नंबर
  • ढेर की तरह: कमजोर ढेर
  • बंच सॉर्ट्स: कार्टेशियन ट्री
  • अन्य ढेर छँटाई: दर्पण ढेर, मिनी-ढेर, नीचे-ऊपर स्थानांतरण
  • हीप सॉर्ट्स: जंग हीप
• मर्ज करना
• वितरण के आधार पर छाँटें
• हाइब्रिड सॉर्टिंग