Sortowanie przez kopcowanie

Sortowanie przez kopcowanie to sortowanie przez wybieranie z lepszym sposobem szukania największej wartości. Trzyma nieposortowane wartości w kopcu, czyli drzewie zapisanym w samej liście, gdzie największa wartość jest zawsze na szczycie. Zdjęcie jej i naprawa kopca zajmują około log n kroków zamiast przeglądania całości.

Kopiec narysowany jako drzewo binarne nad tymi samymi wartościami w postaci słupków; największa wartość w korzeniu przechodzi na koniec listy
Kopiec narysowany jako drzewo binarne nad tymi samymi wartościami w postaci słupków; największa wartość w korzeniu przechodzi na koniec listy

Drzewo w liście

Kopiec binarny to drzewo, które nie potrzebuje wskaźników. Pozycja 0 to korzeń, a dziećmi pozycji i są pozycje 2i + 1 oraz 2i + 2, więc pozycje 1 i 2 to dzieci korzenia, pozycje od 3 do 6 to następny poziom i tak dalej. Każdy poziom jest pełny oprócz ostatniego, który wypełnia się od lewej. W kopcu typu max każdy rodzic jest co najmniej tak duży jak jego dzieci, więc największa wartość jest zawsze w korzeniu.

Przesiewanie w dół

Całą pracę wykonuje jedna operacja. Aby przesiać wartość w dół, porównaj ją z jej dziećmi. Jeśli większe dziecko jest większe od wartości, zamieniają się miejscami, a wartość porównuje się z nowymi dziećmi. Kończy się, gdy żadne dziecko nie jest większe albo gdy wartość dotrze na dół. Drzewo ma tylko około log₂ n poziomów, więc przesiewanie w dół wymaga najwyżej około 2 log₂ n porównań.

Najpierw kopiec, potem sortowanie

Aby zbudować kopiec, przesiej w dół każdego rodzica, od ostatniego aż do korzenia. Każde poddrzewo jest już kopcem, zanim jego rodzic zostanie w nie przesiany. Potem sortuj: zamień korzeń, czyli największą wartość, z ostatnią wartością kopca. Ta wartość jest już na swoim ostatecznym miejscu. Kopiec jest o jeden krótszy, a wartość, która trafiła do korzenia, jest przesiewana w dół, aby go naprawić. Powtarzaj, aż zostanie jedna wartość.

Przykład

Weź 5, 1, 4, 2, 8. Budowa kopca przesiewa 1 w dół pod 8, potem 5 w dół pod 8, co daje 8, 5, 4, 2, 1. Teraz 8 idzie na koniec; 1 trafia do korzenia i schodzi w dół, mijając 5 i 2: 5, 2, 4, 1 | 8. Potem 5 idzie na koniec, a 1 schodzi w dół, mijając 4: 4, 2, 1 | 5, 8. Jeszcze dwie rundy kończą listę: 1, 2, 4, 5, 8, po 12 porównaniach i 10 zamianach.

Mocne i słabe strony

Sortowanie przez kopcowanie zajmuje czas proporcjonalny do n log n nawet w najgorszym przypadku i nie potrzebuje dodatkowej pamięci. Sortowanie szybkie może zwolnić do n², a sortowanie przez scalanie potrzebuje bufora długości listy, więc kopcowanie to bezpieczne wyjście awaryjne: introsort, używany w bibliotece standardowej C++, przełącza się na nie, gdy podziały sortowania szybkiego idą źle. Na prawdziwych komputerach jest zwykle wolniejsze od obu, bo skacze między odległymi miejscami listy, i nie jest stabilne. J. W. J. Williams opublikował sortowanie przez kopcowanie razem z kopcem binarnym w 1964 roku.

Wypróbuj

Otwórz aplikację i naciśnij Krok. Drzewo nad słupkami pokazuje kopiec: przesiewana wartość ma własny kolor, dziecko, z którym jest porównywana, jest podświetlone, a każdą zamianę widać zarówno w drzewie, jak i na słupkach. Gdy kopiec jest gotowy, zobacz, jak korzeń przechodzi na koniec, zmienia kolor na zielony i znika z drzewa.

Często zadawane pytania

Jaka jest złożoność czasowa sortowania przez kopcowanie?

O(n log n) w przypadku najlepszym, średnim i najgorszym. Budowa kopca zajmuje O(n), a każde z n − 1 wyjęć O(log n). Sortuje w miejscu, z O(1) dodatkowej pamięci.

Czym różni się sortowanie przez kopcowanie od sortowania przez wybieranie?

Oba raz za razem biorą największą (lub najmniejszą) pozostałą wartość. Sortowanie przez wybieranie znajduje ją, przeglądając całą nieposortowaną część, za każdym razem n porównań. Sortowanie przez kopcowanie trzyma nieposortowaną część w kopcu, gdzie największa wartość jest już na szczycie, a naprawa kopca kosztuje tylko około log n porównań.

Do czego jeszcze służy kopiec?

Do kolejek priorytetowych: kopiec od razu daje największy (lub najmniejszy) element i pozwala dodawać lub usuwać elementy w około log n krokach. Korzystają z niego systemy szeregowania zadań, algorytm Dijkstry szukający najkrótszej ścieżki i symulacje zdarzeń.

Czy sortowanie przez kopcowanie jest stabilne?

Nie. Przenoszenie korzenia na koniec przesuwa wartości na duże odległości, więc równe wartości mogą zmienić swoją kolejność.

Chcesz wypróbować?

Otwórz PictorX w swojej przeglądarce — do uruchomienia nie jest wymagana żadna instalacja ani karta kredytowa.

Wypróbuj sortowanie przez kopcowanie