Sortowanie przez kopcowanie

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)).

Dzięki za wizytę,
Mateusz Mazurek
Podziel się na:
    Facebook email PDF Wykop Twitter

Dodaj komentarz

avatar

This site uses Akismet to reduce spam. Learn how your comment data is processed.

  Subskrybuj  
Powiadom o