Heapify All The Things With Heap Sort

Vaidehi Joshi

Follow

Jul 13, 2017 – 11 min read

Ktoś mi kiedyś powiedział, że wszystko co ważne w informatyce sprowadza się do drzew. Dosłownie tylko drzew. Możemy ich używać do budowania rzeczy, parsowania rzeczy i interpretowania rzeczy (tak, może się tu dziać trochę przedrzeźniania, nie przejmuj się tym, jeśli nie ma to jeszcze dla ciebie sensu, bo wkrótce będzie!). I możemy nawet użyć ich do – zgadłeś! – sortować rzeczy.

Ach, sortowanie. Zrobiliśmy tego tak wiele w ciągu ostatnich kilku tygodni, ale teraz zbliżamy się do końca naszych przygód z sortowaniem. Jednak niemożliwe i niesprawiedliwe jest mówienie o sortowaniu bez mówienia o specjalnym rodzaju sortowania, które wykorzystuje najnowszą strukturę danych w naszym pasie narzędzi struktur danych.

Ostatnio nauczyliśmy się kochać sterty, specjalny rodzaj drzewa binarnego, które podąża za ścisłym zestawem reguł i jest używane do implementacji takich rzeczy jak kolejki priorytetowe i zadania w tle. Ale to nie są jedyne rzeczy, do których sterty są dobre. Okazuje się, że sterty binarne są często używane nie do innych celów niż efektywne sortowanie. Wiele programów będzie polegać na sortowaniu sterty, ponieważ jest to jeden z najbardziej efektywnych sposobów sortowania tablicy. A teraz, gdy wiemy, co to jest sterta, możemy spróbować zrozumieć, dlaczego działa tak dobrze, jeśli chodzi o problem sortowania!

Przed zanurzeniem się w sortowaniu sterty, upewnijmy się, że mamy sterty prosto w naszych głowach. Możemy pamiętać, że sterta jest tak naprawdę niczym więcej niż drzewem binarnym z kilkoma dodatkowymi zasadami, których musi przestrzegać: po pierwsze, musi zawsze mieć strukturę sterty, gdzie wszystkie poziomy drzewa binarnego są wypełnione, od lewej do prawej, a po drugie, musi być albo uporządkowana jako sterta max lub sterta min. Dla celów sortowania sterty, będziemy mieli do czynienia wyłącznie z maksymalnymi stertami, gdzie każdy węzeł nadrzędny (w tym korzeń) jest większy lub równy wartości jego węzłów dziecięcych.

Okay, przejdźmy do odpowiedzi na pytanie godziny: jak sortować używając sterty? Cóż, aby odpowiedzieć na to pytanie, będziemy musieli najpierw zrozumieć, czym jest algorytm sortowania sterty!

Algorytm sortowania sterty jest techniką sortowania, która opiera się na binarnych strukturach danych sterty. Ponieważ wiemy, że sterty muszą zawsze zachowywać określoną kolejność, możemy wykorzystać tę właściwość i użyć jej do znalezienia największego elementu o maksymalnej wartości oraz do sekwencyjnego sortowania elementów poprzez wybranie węzła głównego sterty i dodanie go do końca tablicy.

Wiemy już, że sortowanie sterty jest efektywnym sposobem sortowania nieposortowanej tablicy; ale co ma wspólnego tablica ze stertą? I jak posortować tablicę używając sterty? Cóż, istnieją trzy kluczowe kroki do tego, jak to działa w praktyce. Przyjrzymy się im bardziej szczegółowo za chwilę, ale spójrzmy najpierw na wysoki poziom tego, czym są te trzy kroki.

1. Na początek, mamy nieposortowaną tablicę. Pierwszym krokiem jest wzięcie tej tablicy i przekształcenie jej w stertę; w naszym przypadku, będziemy chcieli przekształcić ją w maksymalną stertę. Tak więc, musimy przekształcić i zbudować maksymalną stertę z naszych nieposortowanych danych tablicy. Zazwyczaj jest to zamknięte w pojedynczej funkcji, która może się nazywać coś w stylu buildMaxHeap.
2. Gdy już mamy nasze dane tablicowe w formacie sterty max, możemy być pewni, że największa wartość znajduje się w węźle głównym sterty. Pamiętajmy, że nawet jeśli cała sterta nie będzie posortowana, to jeśli zbudowaliśmy naszą max stertę poprawnie i bezbłędnie, każdy pojedynczy węzeł nadrzędny w naszej stercie będzie miał większą wartość niż jego dzieci. Przeniesiemy więc największą wartość – znajdującą się w węźle nadrzędnym – na koniec sterty, zamieniając ją z ostatnim elementem.
3. Teraz największy element sterty znajduje się w ostatnim węźle, co jest świetne. Wiemy, że jest on na posortowanej pozycji, więc można go całkowicie usunąć ze sterty. Ale jest jeszcze jeden krok: upewnienie się, że nowy element węzła głównego znajduje się na właściwym miejscu! Jest bardzo mało prawdopodobne, że element, który zamieniliśmy na pozycję węzła korzenia, jest we właściwym miejscu, więc przesuniemy element węzła korzenia w dół na jego właściwe miejsce, używając funkcji, która zwykle nazywa się coś w stylu heapify.

I to w zasadzie wszystko! Algorytm kontynuuje powtarzanie tych kroków, aż sterta zostanie zredukowana do jednego węzła. W tym momencie wie, że wszystkie elementy w nieposortowanej tablicy są na swoich posortowanych pozycjach, i że ostatni pozostały węzeł będzie w końcu pierwszym elementem posortowanej tablicy.

Okay, wiem, że powiedziałem, że są to jedyne trzy kroki do sortowania sterty. Ale jeśli te trzy kroki wydają się zagmatwane, nie martw się; mogą być dość skomplikowane i trudne do zrozumienia, dopóki nie zobaczysz ich w akcji. W rzeczywistości, myślę, że ten algorytm ma o wiele więcej sensu z ilustrowanym przykładem. Ponieważ sterty są rodzajem drzewa, pomocne jest ich zwizualizowanie, tak samo jak to robimy z drzewami binarnymi. Więc zróbmy to teraz!

Czy kiedykolwiek zajrzałeś pod maskę sortowania sterty?

W porządku, czas na moją absolutnie ulubioną część nauki sortowania sterty: narysowanie go! Hurra! Aby zrozumieć, co dzieje się pod maską sortowania sterty, będziemy pracować z małym, nieposortowanym zbiorem danych.

Zaczniemy od nieposortowanej tablicy z pięcioma elementami, które są super poza kolejnością: .

Pamiętajmy, że ponieważ jest to sortowanie stertowe, z którym pracujemy, będziemy musieli przekształcić tę tablicę w stertę, aby rozpocząć.

Na ilustracji pokazanej tutaj widać, że tablica została przekształcona w drzewo – nie jest to jeszcze sterta, ponieważ nadal nie jest w żadnym maksymalnym lub minimalnym porządku sterty! Widzimy, że tak jest, ponieważ 3 nie jest ani największym, ani najmniejszym elementem, a mimo to jest w tej chwili węzłem głównym. To jest po prostu drzewo, z elementami z tablicy bezpośrednio przetłumaczonymi na format drzewa binarnego.

Ale, ponieważ musimy mieć do czynienia z max stertą, będziemy musieli przekształcić naszą strukturę z drzewa binarnego w max stertę. Zauważ, że w przypadku sterty max, węzły nadrzędne są większe od swoich dzieci. W zeszłym tygodniu poznaliśmy algorytmy, które pozwalają nam określić węzły-dzieci na podstawie indeksu tablicy; w tym tygodniu zobaczymy je w akcji. Algorytmy te są tym, czego używamy do przekształcenia tej tablicy w drzewo, a następnie w stertę.

Dobrze, teraz mamy rzeczywistą maksymalną stertę. Świetnie! Teraz do właściwej pracy sortowania.

Ponieważ wiemy, że największy element znajduje się w węźle głównym, wiemy, że będziemy musieli umieścić go na samym końcu tablicy, w ostatnim dostępnym miejscu indeksu. Tak więc, zamienimy węzeł główny z ostatnim węzłem. Gdy dokonamy tej zamiany, nasz ostatni węzeł będzie zawierał największy element o maksymalnej wartości.

Cool! Teraz możemy zobaczyć, że 19, największy element, który wcześniej był węzłem głównym, jest teraz na ostatniej pozycji w tablicy. A ponieważ jest on efektywnie „posortowany” względem reszty elementów, możemy go całkowicie usunąć ze sterty.

Teraz dobrą wiadomością jest to, że mamy jeden węzeł mniej w naszej stercie do posortowania! Zła wiadomość? Nasza sterta nie jest już właściwie stertą: całkowicie narusza regułę porządku sterty, ponieważ nie jest stertą maksymalną. Zauważ, że 1 jest węzłem głównym, ale na pewno nie jest większy niż jego dwa dzieci, 14 i 7. Musimy więc przesunąć go w dół, na jego właściwe miejsce w drzewie.

Zastosujmy heapify tego drzewa i uczyńmy je ponownie max heap!

Absome! Na powyższej ilustracji widzimy, że najpierw zamieniliśmy 1 i 14, a następnie zamieniliśmy 1 i 8. Teraz wróciliśmy do prawidłowej maksymalnej sterty. Możemy powtórzyć te same kroki, które wykonaliśmy podczas sortowania elementu 19:

→ Najpierw zamienimy pierwszy i ostatni węzeł.
→ Następnie zwałujemy drzewo, aż znów będzie prawidłową maksymalną stertą.

Zróbmy to z naszym nowym węzłem głównym, elementem 14. Oto jak wyglądałyby nasze kolejne dwa kroki:

Rad! Zamieniliśmy pierwszy i ostatni węzeł, a następnie usunęliśmy ostatni węzeł, 14, ponieważ znajdował się on w posortowanej pozycji. Jedyną rzeczą, którą musieliśmy teraz zrobić, było przeniesienie węzła korzenia do jego właściwej lokalizacji i stertowanie elementu 3, aż wróciliśmy do stanu maksymalnej sterty.

Kontynuowalibyśmy to jeszcze trzy razy. W końcu zostałby nam tylko 1, ostatni węzeł w stercie. W tym momencie algorytm sortowania sterty zostałby zakończony, a my wiedzielibyśmy, że 1 będzie pierwszym elementem w tablicy i wiedzielibyśmy, że tablica została ostatecznie posortowana.

Oto świetna wizualizacja całego procesu, przez który właśnie przeszliśmy. Zauważ, jak z każdym iteracyjnym sortowaniem, największy nieposortowany element trafia na swoje właściwe miejsce w stercie, a następnie w tablicy.

Heap sort: what is it good for?

Gdy po raz pierwszy czytałem o heap sort, coś w tym algorytmie wydawało mi się dziwnie znajome. Dopiero po zilustrowaniu sortowania sterty zdałem sobie sprawę, skąd pochodziło moje uczucie déjà vu: sortowanie sterty było prawie dokładnie takie samo jak sortowanie selekcyjne! Być może pamiętasz z wcześniejszych części serii, że sortowanie przez wybór jest algorytmem sortującym, który sortuje listę nieposortowanych elementów poprzez iterację przez listę elementów, znalezienie najmniejszego z nich i odłożenie go na posortowaną listę. Kontynuuje sortowanie, znajdując najmniejszy nieposortowany element i dodając go do posortowanej listy.

Czy to nie brzmi zupełnie jak sortowanie sterty, ale po prostu odwrócone?

Okazuje się, że sortowanie sterty jest bardzo podobne do sortowania selekcyjnego w swojej logice: oba algorytmy znajdują najmniejszy lub największy element, „wybierają” go i umieszczają ten element w jego właściwej lokalizacji na posortowanej liście.

Jednakże, tak podobne jak są, sortowanie sterty jest znacznie lepsze od sortowania selekcyjnego w jeden masywny sposób: jego wydajność! Heap sort jest w zasadzie super ulepszoną wersją sortowania selekcyjnego. Tak, znajduje największy element w nieposortowanej kolekcji i zamawia go na końcu listy – jednak wykonuje całą tę pracę o wiele szybciej niż sortowanie selekcyjne!

Okay, so just how much faster is heap sort? I dlaczego jest szybsze?

No cóż, spójrzmy na kod. Istnieją różne implementacje sortowania sterty, a poniższy kod jest zaadaptowany z implementacji sortowania sterty w JavaScript przez Rosetta Code. Pamiętasz, że sortowanie sterty ma dwie ważne części: buildMaxHeap i heapify. Możemy je zobaczyć w akcji w wersji heapSort poniżej.

Funkcja buildMaxHeap wykonuje pracę polegającą na faktycznym tworzeniu maksymalnej sterty. Zauważ, że nawet ta funkcja wywołuje heapify, która wykonuje pracę polegającą na przesuwaniu jednego elementu na raz w dół do jego właściwej lokalizacji w stercie.

Funkcja heapify jest dość ważna, więc przyjrzyjmy się jej. Zauważ, że polega ona na algorytmach określania lewego i prawego dziecka węzła, które omawialiśmy w zeszłym tygodniu, kiedy po raz pierwszy dowiedzieliśmy się o stertach.

I na koniec funkcja swap, którą widzieliśmy już wcześniej w innych algorytmach sortowania, ale warto na nią szybko spojrzeć, aby przypomnieć sobie, co robi:

Dobra, teraz, gdy mamy już pewien kontekst tego, jak te funkcje oddziałują i wywołują się nawzajem, wróćmy do naszego pierwotnego pytania, jak i dlaczego sortowanie sterty jest o wiele bardziej wydajne niż sortowanie selekcyjne! Jeśli przyjrzymy się dokładnie kodowi, zauważymy dwie rzeczy: po pierwsze, musimy zbudować maksymalną stertę raz, przekazując do niej wszystkie elementy tablicy; po drugie, musimy ponownie i ponownie heapifikować wszystkie elementy w stercie, z wyjątkiem pierwszego elementu węzła głównego.

Te dwie obserwacje są właściwie kluczem do odpowiedzi na pytanie, jak i dlaczego heap sort jest tak szybki, jak jest. Wywołanie buildMaxHeap zajmuje O(n) czasu, ponieważ każdy pojedynczy element musi zostać dodany do sterty, a większa ilość elementów oznacza większą stertę. Pamiętajmy jednak, że mamy do czynienia z drzewem binarnym, a drzewa binarne są z natury logarytmiczne. Tak więc, nawet jeśli musimy wywołać heapify ponownie i ponownie, wywołanie tej funkcji jest w rzeczywistości dość szybkie, ponieważ będzie działać w czasie logarytmicznym, lub O(log n).

Kombinacja tych dwóch złożoności czasowych jest czymś, co już widzieliśmy wcześniej! Heap sort działa w czasie liniowo-rytmicznym, lub w notacji Big O, O(n log n). Tak więc, mimo że sortowanie sterty wydaje się być bardzo podobne do sortowania selekcyjnego, jest ono o wiele szybsze! Sortowanie selekcyjne działa w czasie kwadratowym, lub O(n²), który jest o wiele mniej wydajny niż czas liniowo-rytmiczny.

Szybko przyjrzyjmy się innym sposobom, w jakie sortowanie sterty porównuje się do innych algorytmów sortowania.

Sortowanie sterty przekształca tablicę, która przechodzi do niego podczas sortowania; w przeciwieństwie do niektórych algorytmów sortowania, nie tworzy całkowicie oddzielnej kopii danych wejściowych. To sprawia, że jest to algorytm sortowania in-place. Heap sort również nie potrzebuje pamięci zewnętrznej i jest wewnętrznym algorytmem sortującym. Działa iteracyjnie (a więc jest nierekursywny) i porównuje dwa elementy na raz, gdy zamienia i wywołuje funkcję heapify, co czyni go algorytmem sortowania porównawczego.

Jednakże, z powodu natury sterty i funkcji heapify, jeśli istnieją zduplikowane elementy, nie możemy polegać na tym, że elementy zachowają swoją kolejność! Tak więc, sortowanie sterty jest niestabilne; jest to główna różnica między sortowaniem scalającym a sortowaniem sterty, z których każde polega na strukturach drzewiastych, aby wykonywać je tak wydajnie. Jednak merge sort wygrywa w bitwie o stabilność, podczas gdy heap sort zawodzi w tej kategorii.

Pomimo różnic, merge sort i heap sort mogą zgodzić się co do jednej rzeczy: bez drzew binarnych, obaj byliby zgubieni!

Źródła

Istnieje kilka naprawdę fantastycznych notatek z kursów i wykładów na temat sortowania sterty, a także kilka dobrych samouczków wideo. Zrobiłem trochę googlingu, abyś nie musiał! Oto kilka świetnych miejsc, od których możesz zacząć, jeśli jesteś zainteresowany dowiedzeniem się więcej o sortowaniu sterty.

1. Wprowadzenie do algorytmów: sortowanie sterty, MIT
2. Algorytmy: sortowanie sterty, profesor Ching-Chi Lin
3. Sortowanie sterty, Growing with the Web
4. Sortowanie sterty w 4 minuty, Michael Sambol
5. Sortowanie sterty: Max heap, strohtennis