###### tags: `xivlo` # Zajęcia 07.04.2021 > Notatka (z drobnymi zmianami) autorstwa [Bartka Sobockiego](https://hackmd.io/@bsobocki) ## Kopiec -- Heap ### Motywacja Potrzebna nam **kolejka priorytetowa** - struktura danych, która będzie zachowywała porządek względem ustalonego kryterium (na przykład kolejka priorytetowa przechowująca liczby całkowite, zwracająca przy operacji $\text{pop}(\space)$ najmniejszą z dostępnych liczb). Pobierany element za pomocą operacji $\text{pop}(\space)$ (element z korzenia kopca). ### Przykład Kolejka priorytetowa z posortowanymi rosnąco elementami. **Możliwa Implementacja:** $Kopiec\_min$ - korzeń drzewa jest najmniejszym elementem w strukturze. :::danger ***WAŻNE*** Mimo, iż do implementacji kolejki priorytetowej możemy użyć kopca, to kopiec nie jest kolejką priorytetową! Kopiec to kopiec :) ::: ## Struktura Kopiec jest jednym z przykładów **drzewa binarnego**. Składa się z **korzenia - root** (zaznaczonego niebieską strzałką) oraz co najwyżej dwóch synów: <span style="color:green">$lewego$ (kolor zielony)</span> i <span style="color:red">$prawego$ (kolor czerwony)</span>. ![](https://i.imgur.com/kZIwnqs.png) Każdy wierzchołek i jego całe potomstwo - synowie synów, ich synowie, synowie tych synów synów synów itd. tworzą poddrzewo, które również jest kopcem. ### Wysokość Każdy wierzchołek ma 2-ch synów, stąd każdy kolejny poziom ma 2 razy więcej wierzchołków. Oznacza to że liczba takich poziomów wynosi $\lfloor \log n \rfloor + 1$ (podłoga z logarytmu o podstawie 2 z liczby elementów kopca plus 1, bo liczymy, że drzewo jednoelementowe ma wysokość 1). ***Wniosek*** Wysokość drzewa wynosi $O(\log n)$, dlatego operacje **przejścia po drzewie w górę czy w dół** mają złożoność $O(\log n)$. ### Uzupełnianie Kopiec uzupełniany jest ***`w dół od lewej strony do prawej`*** (dodawanie ukazane poniżej oraz w pliku [heap_insert.png](https://github.com/bsobocki/Algorytmy_StrukturyDanych/blob/master/heap--kopiec/images/heap_insert.png) ). Do poziomu $k+1$ można dodać element dopiero gdy poziom $k$ jest cały zapełniony. Przykładwe kopce __niepoprawne__ _(oznaczone <span style="color:red">czerwonym</span> znakiem <span style="color:red">$X$</span>)_ oraz **poprawne** *(oznaczone <span style="color:green">zielonym</span> znakiem <span style="color:green">$V$</span>)*: ![](https://github.com/bsobocki/Algorytmy_StrukturyDanych/blob/master/struktury_danych/heap--kopiec/images/heap_wrong_and_correct.png?raw=true) ## Implementacja Chcemy, aby kopiec był jak najbardziej wydajny czasowo i pamięciowo. W związku z tym kopiec powinien opierać się na tablicy. Dostęp do danych węzłów opiera się na dostępie do odpowiednich komórek. Jeśli $i$ to indeks wierzchołka wówczas: - $lewy\_syn\space(kopiec,\space i) => kopiec\space[\space 2i\space]$ - $prawy\_syn\space(kopiec,\space i) => kopiec\space [\space 2i+1\space]$ - $ojciec\space(kopiec,\space i) => kopiec\space[\space\frac{i}{2}\space]\quad\quad\text{jeśli}\space i\neq0$ Gdzie ułamek $\frac{i}{2}\space$ oznacza dzielenie całkowite $i$ przez $2$. Mała wizualizacja: ![](https://github.com/bsobocki/Algorytmy_StrukturyDanych/blob/master/struktury_danych/heap--kopiec/images/heap_array.png?raw=true) ## Porządek Kopcowy Każdy kopiec jest zaprojektowany według porządku kopcowego. Każdy wierzchołek, powinien spełniać pewne kryterium względem swego potomstwa. ### Kryterium **Przykład:** wspomniany wcześniej $kopiec\_min - heap\_min$. W Kopcu tym korzeń drzewa powinien mieć najmniejszą możliwą wartość z całej struktury. Zatem kryterium brzmi mniej więcej tak: :::info :bulb: Każdy wierzchołek posiada klucz (wartość w węźle) mniejszy niż jego potomstwo. ::: Można zatem zauważyć, ze wtedy **korzeń kopca (root)** ma najmniejszą wartośc spośród wszystkich węzłów. ## Operacje Oznaczymy nasz $kopiec\_min$ jako $H$. ### Minimum ```cpp return H[1]; ``` :::success ***Złożoność*** Czas wykonania **stały** $O(1)$, potrzebujemy tylko dostęu do $H[0]$. ::: ### Insert Dodawanie elementów do kopca: ![](https://github.com/bsobocki/Algorytmy_StrukturyDanych/blob/master/struktury_danych/heap--kopiec/images/gif-insert/insert_heap.gif?raw=true) Kolorem czerwonym zaznaczony został nowo dodany element. Dodawanie polega na włożeniu elementu tak jak zostało to pokazane powyżej, a następnie "przejściu przez drzewo w górę" w celu umiejscowienia dodanego elementu tak, aby został zachwany porządek kopcowy. :::warning Co to oznacza? ::: Dla ułatwienia załóżmy, ze operujemy na $kopcu\_min$ *(analogicznie postępujemy na $kopcu\_max$)*. Dodany element zostaje porównywany z ojcem, a następnie, jeśli jego wartość jest mniejsza to zamieniają się miejscami. Następnie element ten, będąc na miejscu swojego poprzedniego ojca jest porównywany i ewentualnie zamieniany z nowym ojcem. Ta sytuacja powtarza się dopóki syn jest mniejszy od ojca lub dopóki nie dojdziemy do korzenia, który ojca już nie ma ;_; Mały przykład dla operacji `insert` następujących elementów: `10, 7, 8, 9, 4, 2, 6, 1` Mniej więcej będzie wyglądać tak: ![](https://github.com/bsobocki/Algorytmy_StrukturyDanych/blob/master/struktury_danych/heap--kopiec/images/heap_insert_example.png?raw=true) :::success ***Złożoność*** Dodawanie elementu odbywa się w czasie logarytmicznym $O(\log n)$, gdzie podstawą logarytmu jest $2$, a $n$ oznacza liczbę elementów w kopcu. ::: ### Delete_min Możemy już dodawać elementy do naszej struktury, a zatem możemy łatwo zaimplemmentować operację $\text{push}$ w naszej kolejce priorytetowej. Potrzebna będzie nam jeszcze funkcja $\text{pop}$, która zwraca i usuwa z kolejki pierwszy względem ustalonego porządku element. Pomoże nam w tym operacja na kopcu - $delete\_min$. :::warning ***Co chcemy zrobić?*** ::: Chcemy zwrócić korzeń struktury i go usunąć, a następnie przywrócić porządek kopcowy. Możemy to zrobić na dwa sposoby: :::info * pobieranie elementu na samym dole na prawo (ostatni z tablicy) * dodanie do korzenia * "jazda w dół" ::: lub (ciekawostka) :::info * usunięcie korzenia i pozostawienie dziury * "jazda z dziurą w dół" * pobranie elementu na samym dole na prawo * wstawienie go zamiast dziury * "jazda w górę" ::: $n$ - liczba elementów w kopcu **Usuwanie przez zastąpienie ostatnim elementem** Pierwszy sposób brzmi dość prosto i w miarę intuicyjnie. Chcemy po prostu mieć jak najmniej zaburzeń, więc element ostatni z tablicy jest najlepszą opcją, aby struktura i porządek kopcowy poza korzeniem pozostali nienaruszeni. **Ilość porównań** będzie wynosić $2 \log n$, ponieważ najpierw porównamy synów pomiędzy sobą, a następnie ojca i mniejszego syna. ![](https://github.com/bsobocki/Algorytmy_StrukturyDanych/blob/master/struktury_danych/heap--kopiec/images/heap_delete_min.png?raw=true) **Usuwanie z użyciem dziury** Drugi sposób teoretycznie jest bardziej skomplikowany, ale przekonamy się, że może być lepszy. Mamy dziurę, pusty element, który "idzie w dół" drzewa, a my ignorujemy póki co fakt, że naruszona zostaje struktura kopca. Z każdym krokiem staje się ojcem dla dwóch wierzchołków. Porównujemy te dwa wierzchołki i mniejszy z nich staje się ojcem, a dziura przechodzi na jego miejsce. Dzieje się tak, dopóki ten pusty element nie dojdze, gdzie już synów mieć nie będzie. Po dotarciu tam nagle zauważamy, że nasza struktura zostaje naruszona, a więc któryś element musi wejść na jej miejsce. Na ochotnika zgłasza się ostatni element $v$ z tablicy (prawy dolny na ostatnim poziomie), ale może zdarzyć się, że będzie on zbyt mały, aby pozostać w tym miejscu, dlatego "idziemy z nim w górę". Teoretycznie **ilość porównań** wynosić będzie $2 \log n$, ponieważ "idąc w dół" dziurą porównujemy ze sobą tylko jej kolejnych synów, natomiast "idąc w górę" naszym ochotnikiem $v$ porównujemy go z kolejnymi ojcami. ![](https://github.com/bsobocki/Algorytmy_StrukturyDanych/blob/master/struktury_danych/heap--kopiec/images/heap_delete_min_hole.png?raw=true) ``` - Czy zatem są one równe pod względem ilości porównań? - Nie. ``` Zauważmy, że "idąc w górę z dołu" elementem $v$ w zasadzie nie zajdziemy za daleko. Prawdopodobieństwo, że ten element będzie wystarczająco mały, żeby pójść wysoko w górę (na szczyt na pewno nie dojdzie, bo inaczej nie byłby na dole) jest znikome, dlatego złożoność drugiego sposobu będzie dużo niższa. :::success ***Złożoność*** Usunięcie elementu wynosi $O(1)$, natomiast wstawianie na jego miejsce, któregoś z istniejących już wierzchołków wiąże się z kosztem $O(\log n)$, stąd operacja $delete\_min$ ma złożoność $O(\log n)$. ::: ### Przywracanie porządku Jak powyżej można przeczytać, Kopiec potrzebuje swojego porządku, aby prawidłowo i szybko funkcjonować. Przywracanie porządku dla danego elementu $e$ polega na: 1) "pójściu w górę" : Sprawdzeniu, czy jest on na odpowiednim miejscu, to znaczy, czy jego ojciec jest od niego mniejszy. Jeśli tak to zamieniają się miejscami i procedura przywracania porządku wywoływana jest dla $e$, które teraz jest już na miejscu swojego ojca. Idziemy w ten sposób *"do góry"* dopóki każdy kolejny ojciec jest większy lub do korzenia. 2) "pójściu w dół" : Sprawdzeniu, który syn jest mniejszy, a następnie czy dany wierzchołek $e$ jest mniejszy od mniejszego z nich. Jeśli jest większy, to zamieniamy je miejscami. W ten sposób najmniejszy z danej trójki (ojca i synów) zostaje ojcem. Idziemy w ten sposób *"w dół"* dopóki któryś z synów będzie mniejszy od danego wierzchołka, lub dopóki nie dojdziemy do najniższego poziomu drzewa. Tak przywracamy porządek dla danego $v$. Używamy przywracania porządku w operacjach takich jak $insert$, $delete\_min$, czy zmiany wartosci danego wierzchołka (przy zmianie wartości możemy "iść w górę", ale też mozemy "iść w dół", bo wartość może być za duża na swoje miejsce. Warto o tym pamiętać. ## Tablica https://miro.com/app/board/o9J_lLBeO78=/ <iframe width="768" height="432" src="https://miro.com/app/live-embed/o9J_lMH9YTc=/?moveToViewport=-768,266,1536,749" frameBorder="0" scrolling="no" allowFullScreen></iframe>