---
# System prepended metadata

title: Zajęcia 07.04.2021
tags: [xivlo]

---

###### 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>