Sortowanie przez kopcowanie

Cześć! Cieszę się, że mnie odwiedziłeś/aś. Zanim przejdziesz do artykułu chciałbym zwrocić Ci uwagę na to, że ten artykuł był pisany kilka lat temu (2012-07-01) miej więc proszę na uwadzę że rozwiązania i przemyślenia które tu znajdziesz nie muszą być aktualne. Niemniej jednak zachęcam do przeczytania.

Kolejna rzecz z algorytmiki.

Kopce :)

Kopiec to takie drzewo binarne w którym:

• Wartość klucza (czyli wartość po prostu) w każdym węźle jest nie mniejsza/nie większa niż u jego potomków.
• Wszystkie liście leżą na co najwyżej dwóch sąsiednich poziomach.
• Liście na ostatnim poziomie szczelnie wypełniają lewą część drzewa.

Kopiec to taka struktura której implementacją może byc zwykły wektor (tablica jednowymiarowa). Przykład kopca i jego implementacja tablicowa:

Kliknij aby powiększyć.

Ok, to w miare przybliżyłem istotę kopca. Warto pamiętać że kopiec jest drzewem binarnym. Nazwaliśmy najważniejsze węzły w kopcu, to teraz, aby w pełni zrozumieć istotę sortowania przez kopcowanie omówię przywracanie własności kopca.

Czasem, w skutek jakis operacji, kopiec traci własności kopca. Najczęściej jest to własność mówiąca o wartościach, że muszą one się sukcesywnie, poziomami, zmniejszać.

Zaczynamy rekurencyjnie przeglądać kopiec, od korzenia w dół. Szukamy większego z potomków korzenia i w tę drogę się kierujemy. Jeśli syn korzenia jest większy niż korzeń to zamieniamy go. Z węzłem na drugim poziomie również robimy to samo, wybieramy większego z synów i jesli jest wiekszy od ojca to zamieniamy :) Popatrz na przykład:

Kliknij aby powiększyć.

No dobra, to przejdźmy do sedna…

Sortowanie przez kopcowanie polega na cyklicznej wymianie liścia z korzniem, odcinaniu liścia i przywróceniu własności kopca. Odcinane liście umieszkane są w kolejce. Pokażę jak to wygląda na jakimś kopcu:

Koniecznie kliknij aby powiększyć. 

Sortowanie to, ma złożoność obliczeniową O(nlg(n)). Wynika to z tego, że czas przywracania własności kopca jest O(lg(n)).