Tri par ordre décroissant Tri par tas

Question

J'ai essayé d'apprendre à implémenter un heaport.

En particulier, j'ai un algorithme de heapsort qui trie l'entrée dans l'ordre d'acception, mais je ne peux pas comprendre ce qui doit être changé pour le rendre ordre décroissant.

Voici le code: (Une partie de ce manuel est du)

void heapSort(int numbers[], int array_size) 
{ 
    int i, temp; 

    for (i = (array_size/2); i >= 0; i--) 
    siftDown(numbers, i, array_size - 1); 

    for (i = array_size-1; i >= 1; i--) 
    { 
    temp = numbers[0]; 
    numbers[0] = numbers[i]; 
    numbers[i] = temp; 
    siftDown(numbers, 0, i-1); 
    } 
} 


void siftDown(int numbers[], int root, int bottom) 
{ 
    int done, maxChild, temp; 

    done = 0; 
    while ((root*2 <= bottom) && (!done)) 
    { 
    if (root*2 == bottom) 
     maxChild = root * 2; 
    else if (numbers[root * 2] > numbers[root * 2 + 1]) 
     maxChild = root * 2; 
    else 
     maxChild = root * 2 + 1; 

    if (numbers[root] < numbers[maxChild]) 
    { 
     temp = numbers[root]; 
     numbers[root] = numbers[maxChild]; 
     numbers[maxChild] = temp; 
     root = maxChild; 
    } 
    else 
     done = 1; 
    } 
} 

Si quelqu'un pouvait indiquer quelle partie du code doit être modifié, ce serait extrêmement utile :).

Answer 1

Ce que vous avez implémenté est un "tas maximum" (c'est-à-dire que les valeurs des enfants de chaque noeud sont inférieures à la valeur du noeud parent). Vous devez simplement modifier la fonction siftDown afin que le parent soit toujours le plus petit que les enfants. Ceci en fait un min-tas et sert les valeurs dans l'ordre inverse (puisque les plus petits éléments arrivent en haut du tas d'abord), vous donnant ainsi un tri décroissant.