Implementation (Part 1)
Lección 5 de 9 del curso Heap Sort - Serie de DSA de Coddy.
Construiremos Heap Sort a partir de su operación fundamental.
Desafío
FácilEl corazón de Heap Sort es la operación sift-down. Vamos a construir eso primero.
Escribe una función llamada siftDown que reciba un arreglo arr (tratado como un montículo binario) y un índice i, y restaure la propiedad de max-heap en ese nodo empujándolo hacia abajo. Compara el nodo con sus dos hijos en 2*i + 1 y 2*i + 2; si el hijo más grande es mayor, intercámbialo con él y continúa desde la posición del hijo. Devuelve el arreglo.
Por ejemplo, siftDown([1, 10, 5, 3, 2], 0) devuelve [10, 3, 5, 1, 2].
Pruébalo tú mismo
#include <stdlib.h>
int* siftDown(int* arr, int arr_size, int i, int* returnSize) {
// Escribe el código aquí
*returnSize = arr_size;
return arr;
}
Ponte a pruebaEsta lección incluye un breve cuestionario. Empieza la lección para responderlo y registrar tu progreso.
Todas las lecciones de Heap Sort - Serie de DSA
2The Algorithm
How it works?Pseudo CodeImplementation (Part 1)Implementation (Part 2)
Time and Space Complexity