Implementacja (część 1)

Lekcja 5 z 9 w kursie Sortowanie przez kopcowanie — seria DSA w Coddy.

Zbudujemy sortowanie przez kopcowanie, zaczynając od jego podstawowej operacji.

Wyzwanie

Łatwy

Sercem Heap Sort jest operacja sift-down. Najpierw ją zaimplementujmy.

Napisz funkcję o nazwie siftDown, która przyjmuje tablicę arr (traktowaną jako kopiec binarny) oraz indeks i i przywraca własność kopca maksymalnego w tym węźle, przesuwając go w dół. Porównaj węzeł z jego dwójką dzieci o indeksach 2*i + 1 i 2*i + 2; jeśli większe dziecko ma większą wartość, zamień je miejscami i kontynuuj od pozycji dziecka. Zwróć tablicę.

Na przykład siftDown([1, 10, 5, 3, 2], 0) zwraca [10, 3, 5, 1, 2].

Spróbuj swoich sił

#include <stdlib.h>

int* siftDown(int* arr, int arr_size, int i, int* returnSize) {
    // Napisz kod tutaj
    *returnSize = arr_size;
    return arr;
}