Penyortiran tumpukan lemah

Artikel ini ditulis dengan dukungan EDISON.

Kami terlibat dalam pembuatan perangkat lunak tertanam serta pengembangan aplikasi dan situs web .

Kami menyukai teori algoritma! ;-)

Tumpukan lemah

Meminimalkan jumlah perbandingan

Keturunan juggling

Bangunlah tumpukan yang lemah

1. Jika keturunan memiliki keturunannya, maka tukar subpohon kiri dan kanannya (mis. Ubah 0/1 dalam array BIT untuk elemen ini).
2. Tukarkan nilai-nilai dari node turunan dan progenitor.

Parsing tumpukan lemah

Sortir heap lemah :: Sortir heap lemah

• 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. Kami bertukar (kiri ⇔ kanan) sub pohon dengan keturunan untuk simpul di mana keturunan kiri saat ini berada.
      • II.3.c.2. Kami mengubah root tumpukan dan simpul dengan anak kiri saat ini.
  • II.4. Pada akar tumpukan lemah sekali lagi adalah elemen maksimum untuk bagian array yang belum disortir yang tersisa. Kami kembali ke paragraf II.1 dan ulangi proses sampai semua elemen diurutkan.

Kode 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;
  }
}

Kompleksitas memori ekstra

Kompleksitas waktu

Penyaringan penuh

Tumpukan binomial

Algoritma rahasia

1. Tidak ada "pelemahan", itu adalah penyortiran penuh (non-binary) pohon di mana prinsip "setiap orang tua lebih besar daripada keturunan" dicapai dan dipelihara.
2. Pada semua tahap, kita membandingkan keturunan bukan dengan kakek-nenek mereka, tetapi dengan orang tua langsung mereka.
3. Apa yang tampak seperti pertukaran nilai antara keturunan dan leluhur + pertukaran tempat subtree dalam keturunan - ternyata merupakan pertukaran rasio itu sendiri (keturunan / orang tua). Jika node induk lebih kecil dari turunan berdasarkan nilai, maka induk itu sendiri menjadi turunan, dan turunan menjadi induk.

Di seri selanjutnya

Referensi

Artikel Seri:

• Aplikasi Excel AlgoLab.xlsm
• Pertukaran macam
• Urutan Penyisipan
• Sortir berdasarkan pilihan
  • Heap Sorts: N-Piramida
  • Heap Sorts: Leonardo Numbers
  • Heap sort: heap lemah
  • Bunch Sorts: Cartesian Tree
  • Penyortiran tumpukan lainnya: tumpukan cermin, tumpukan mini, pengayakan bottom-up
  • Heap Sorts: Jung Heap
• Gabungkan Urusan
• Urutkan berdasarkan distribusi
• Sortasi Hibrid