Implementazione (Parte 1)

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

Costruiremo Heap Sort partendo dalla sua operazione fondamentale.

Sfida

Facile

Il cuore di Heap Sort è l'operazione sift-down. Costruiamola per prima.

Scrivi una funzione chiamata siftDown che accetta un array arr (considerato un heap binario) e un indice i, e ripristina la proprietà di max-heap in quel nodo spingendolo verso il basso. Confronta il nodo con i suoi due figli agli indici 2*i + 1 e 2*i + 2; se il figlio più grande è maggiore, scambialo con il nodo e continua dalla posizione del figlio. Restituisci l'array.

Per esempio, siftDown([1, 10, 5, 3, 2], 0) restituisce [10, 3, 5, 1, 2].

Provalo tu

#include <stdlib.h>

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