# Lista 7 Zadanie 4.
:::info
Kacper Olejak (300814)
:::
## Treść zadania.

Zakładam, że procedury zostały przedstawione na wykładzie, stąd brak ich pseudokodu.

### `insert` : O(1)

Dodajemy do struktury kopca nowy węzeł. Koszt tej operacji to $O(1)$. Zmiana potencjalu w tym przypadku $= 1$.

Koszt zamortyzowany $:= 1 + O(1) = O(1)$

### `deletemin` : O($d_{max}$) = O($log_{n}$)

*d_max* - maksymalna liczba dzieci w jakimkolwiek węźle w kopcu

Najpierw odcinamy minimalny korzeń i przenosimy dzieci do listy korzeni.
Mamy maksymalnie $d_{max}$ dzieci do przyłączenia. Koszt tego to $O(d_{max})$
Niektóre z nich mogą stracić zaznaczenie. Zmiana potencjału w tym przypadku jest $<= d_{max}$.
Stąd koszt zamortyzowany tej częśći to $O(d_{max})$.

Teraz łączymy ze sobą drzewa o jednakowym stopniu.
Załóżmy, że wykonujemy $t$ połączeń i dostajemy $d$ drzew. Mamy więc $t+d$ drzew od których zaczęlismy. Potencjał zmniejszył się o $t$.
Stąd koszt zamortyzowany tej części to $O(d)$ i $d <= d_{max}$.
Więc ostatecznie mamy koszt zamortyzowany = $O(d_{max})$.

### `decreasekey` : O(1)

*Węzeł nazywamy **zaznaczonym** w momencie, gdy stracił drugiego syna.*

Rozważmy przypadki:
- węzęł nie musi się przemieścić; wtedy potencjał nie ulega zmianie, potrzebujemy $O(1)$ operacji elementarnych stąd koszt zamortyzowany = $O(1)$.
- węzęł musi się przemieścić, nazwijmy go $A$, wykonujemy kroki:
(i) Przenosimy go do listy korzeni w $O(1)$. Potencjał wzrośnie o $<= 1$: O $1$ jeśli $A$ nie był *zaznaczony*, o $-1$ jeśli był.
(ii) Sprawdzamy zaznaczonych przodków $A$ i przenosimy ich do listy korzeni w $O(1)$. Potencjał wzrasta o $1$ (bo mamy nowy korzeń) i zmniejsza się o $2$, bo węzeł zostaje odznaczony.
Stąd koszt zamortyzowany $= O(1) - 1 = 0$. (bez znaczenia na ilość zaznaczonych przodków).
(iii) Przodek mógł zostać zaznaczony. Koszt tej operacji to $O(1)$
a potencjał wzrasta o $2$.
Podsumowując zamortyzowany koszt mamy $O(1)$.

### `meld` : O(1)

Łączymy dwa kopce, meld jest zdefiniowany leniwie. Zmiana potencjału w tym przypadku = 0.

Koszt zamortyzowany $:= 0 + O(1)$

### `findmin` : O(1)
Nie zmieniamy nic w kopcu.
Struktura pamięta wskaźnik na minimalny element.

Koszt zamortyzowany $:= O(1)$