Implementazione (Parte 2)

Lezione 6 di 9 del corso Heap Sort - Serie DSA di Coddy.

Ora combiniamo la costruzione dell'heap e l'estrazione ripetuta del massimo.

Sfida

Medio

Ora metti tutto insieme nell'algoritmo completo.

Scrivi una funzione chiamata heapSort che accetta un array di interi e lo restituisce ordinato in ordine crescente.

Per prima cosa costruisci un max-heap facendo scendere ogni nodo non foglia, dall'indice n/2 - 1 fino a 0. Poi scambia ripetutamente la radice (il valore più grande) con l'ultimo elemento dell'heap, riduci l'heap di uno e fai scendere nuovamente la nuova radice.

Usa una funzione helper sift-down che accetta la size corrente dell'heap, così puoi ridurre l'heap man mano.

Provalo tu

#include <stdlib.h>

int* heapSort(int* arr, int arr_size, int* returnSize) {
    // Scrivi il codice qui
    *returnSize = arr_size;
    return arr;
}