Tri des tas faibles

Cet article a été écrit avec le soutien d'EDISON.

Nous sommes engagés dans la création de logiciels embarqués ainsi que dans le développement d'applications et de sites Web .

Nous aimons la théorie des algorithmes! ;-)

Pile faible

Minimiser le nombre de comparaisons

Descendants jongleurs

Construisez une pile faible

1. Si le descendant a ses descendants, échangez alors ses sous-arbres gauche et droit (c'est-à-dire basculez 0/1 dans le tableau BIT pour cet élément).
2. Échangez les valeurs du nœud descendant et du nœud progéniteur.

Analyser une pile faible

Tri par tas faible :: Tri par tas faible

• 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. Nous échangeons (gauche ⇔ droite) les sous-arbres avec les descendants pour le nœud dans lequel se trouve le descendant gauche actuel.
      • II.3.c.2. Nous changeons la racine du tas et le nœud avec l'enfant gauche actuel.
  • II.4. À la racine du tas faible se trouve à nouveau l'élément maximum pour la partie non triée restante du tableau. Nous revenons au paragraphe II.1 et répétons le processus jusqu'à ce que tous les éléments soient triés.

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

Complexité de mémoire supplémentaire

Complexité temporelle

Tamisage complet

Pile binomiale

Algorithme secret

1. Il n'y a pas de «faiblesse», c'est un arbre de tri à part entière (non binaire) dans lequel le principe «tout parent est supérieur à n'importe lequel de ses descendants» est atteint et maintenu.
2. À toutes les étapes, nous comparons les descendants non pas avec leurs ancêtres, mais avec leurs parents immédiats.
3. Ce qui ressemble à un échange de valeurs entre un descendant et un ancêtre + un échange de lieux de sous-arbres chez un descendant - il s'avère être l'échange du rapport lui-même (descendant / parent). Si le nœud parent est plus petit que le descendant par valeur, le parent lui-même devient le descendant et le descendant devient le parent.

Dans la prochaine série

Références

Articles de série:

• Application Excel AlgoLab.xlsm
• Exchange Sorts
• Tri d'insertion
• Trier par sélection
  • Classes de tas: N-Pyramides
  • Heap Sorts: Leonardo Numbers
  • Tri par tas: tas faible
  • Torts de bouquet: arbre cartésien
  • Autres tri de tas: tas miroir, mini tas, tamisage de bas en haut
  • Classes de tas: Jung Heap
• Fusionner les tris
• Trier par distribution
• Tri hybride