Implementation (Part 2)
Leçon 6 sur 9 du cours Tri par tas - Série DSA de Coddy.
Maintenant, nous combinons la construction du tas et l'extraction répétée du maximum.
Défi
MoyenMaintenant, rassemblez tout cela pour former l'algorithme complet.
Écrivez une fonction nommée heapSort qui prend un tableau d'entiers et le renvoie trié par ordre croissant.
Construisez d'abord un tas-max (max-heap) en faisant descendre (sifting down) chaque nœud non-feuille, de l'indice n/2 - 1 jusqu'à 0. Ensuite, échangez de manière répétée la racine (la plus grande valeur) avec le dernier élément du tas, réduisez la taille du tas de un, et faites redescendre la nouvelle racine.
Utilisez une fonction auxiliaire sift-down qui prend en paramètre la
sizeactuelle du tas, afin de pouvoir réduire le tas au fur et à mesure.
Essayez vous-même
#include <stdlib.h>
int* heapSort(int* arr, int arr_size, int* returnSize) {
// Écrivez le code ici
*returnSize = arr_size;
return arr;
}
Testez-vousCette leçon comprend un petit quiz. Commencez la leçon pour y répondre et suivre votre progression.
Toutes les leçons de Tri par tas - Série DSA
2The Algorithm
How it works?Pseudo CodeImplementation (Part 1)Implementation (Part 2)
Time and Space Complexity