Lekcja: "Algorytmy sortujące - drzewa binarne, sortowanie przez kopcowanie"
Schemat blokowy
Przedstawiony algorytm ma klasę złożoności O(n). Kopiec jest tworzony w tym samym zbiorze wejściowym d[ ].
W pętli 1 kolejne elementy zbioru są wstawiane do kopca. Rozpoczynamy od elementu drugiego, ponieważ pierwszy i tak zostaje na swoim miejscu. Inicjujemy także następujące zmienne: j – pozycja wstawianego elementu (liścia), k – pozycja rodzica (elementu nadrzędnego), x –zapamiętująca wstawiany element.
Zadaniem pętli 2 jest znalezienie w kopcu miejsca do wstawienia zapamiętanego elementu w zmiennej x. Pętla jest wykonywana do momentu k = 0 – osiągnięcia korzenia lub znalezienia przodka większego od zapamiętanego elementu – złamania warunku kopca. W takim przypadku następuje zamiana miejsc elementów tak aby warunek kopca został spełniony. Po zakończeniu pętli w zmiennejj znajduje się numer pozycji w zbiorzed[ ], na której należy umieścić element w x.
Po zakończeniu pętli nr 1 wzbiorze zostaje utworzona struktura kopca.
