Implementacja (część 2)

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

Teraz łączymy budowanie kopca z wielokrotnym wyodrębnianiem maksimum.

Wyzwanie

Średni

Teraz połącz wszystko w pełny algorytm.

Napisz funkcję o nazwie heapSort, która przyjmuje tablicę liczb całkowitych i zwraca ją posortowaną w rosnącej kolejności.

Najpierw zbuduj kopiec maksymalny, przesiewając w dół każdy węzeł niebędący liściem, od indeksu n/2 - 1 do 0. Następnie wielokrotnie zamieniaj korzeń (największą wartość) z ostatnim elementem kopca, zmniejszaj kopiec o jeden element i przesiewaj nowy korzeń w dół.

Użyj funkcji pomocniczej przesiewającej w dół, która przyjmuje bieżący size kopca, aby można było stopniowo zmniejszać kopiec.

Spróbuj swoich sił

#include <stdlib.h>

int* heapSort(int* arr, int arr_size, int* returnSize) {
    // Wpisz kod tutaj
    *returnSize = arr_size;
    return arr;
}

Sprawdź się

Ta lekcja zawiera krótki quiz. Zacznij lekcję, żeby na niego odpowiedzieć i śledzić swoje postępy.

Wszystkie lekcje w sekcji Sortowanie przez kopcowanie — seria DSA

1Wprowadzenie

Wprowadzenie Motywacja

2Algorytm

Jak to działa?Pseudokod Implementacja (część 1)Implementacja (część 2) Lekcja projektowa

Złożoność czasowa i pamięciowa

3Końcowe wyzwania

Końcowe wyzwanie nr 1 Końcowe wyzwanie nr 2

Poćwicz samodzielnie: Kompilator C online