Implementation (Part 2)
Lección 6 de 9 del curso Heap Sort - Serie de DSA de Coddy.
Ahora combinamos la construcción del montículo y la extracción repetida del máximo.
Desafío
IntermedioAhora ponlo todo junto en el algoritmo completo.
Escribe una función llamada heapSort que reciba un arreglo de enteros y lo devuelva ordenado en orden ascendente.
Primero construye un max-heap realizando un sift-down en cada nodo que no sea hoja, desde el índice n/2 - 1 hasta el 0. Luego, intercambia repetidamente la raíz (el valor más grande) con el último elemento del heap, reduce el tamaño del heap en uno y realiza un sift-down de la nueva raíz.
Utiliza un ayudante sift-down que reciba el
sizeactual del heap, para que puedas reducir el heap a medida que avanzas.
Pruébalo tú mismo
#include <stdlib.h>
int* heapSort(int* arr, int arr_size, 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