Implementation (Part 1)
Leçon 5 sur 9 du cours Tri par tas - Série DSA de Coddy.
Nous allons construire le Heap Sort à partir de son opération de base.
Défi
FacileLe cœur du tri par tas (Heap Sort) est l'opération sift-down (tamisage vers le bas). Commençons par construire cela.
Écrivez une fonction nommée siftDown qui prend un tableau arr (traité comme un tas binaire) et un indice i, et restaure la propriété de tas-max (max-heap) au niveau de ce nœud en le poussant vers le bas. Comparez le nœud avec ses deux enfants à 2*i + 1 et 2*i + 2 ; si l'enfant le plus grand est supérieur, échangez-le avec lui et continuez à partir de la position de l'enfant. Retournez le tableau.
Par exemple, siftDown([1, 10, 5, 3, 2], 0) renvoie [10, 3, 5, 1, 2].
Essayez vous-même
#include <stdlib.h>
int* siftDown(int* arr, int arr_size, int i, int* returnSize) {
// Écrire 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