# AiSD 17.03.2021

###### tags: `AiSD`

## Zadanie 1.2

procedure zamien(K[1..n], v, u)
    pom <- K[u]
    K[u] <- K[v]
    K[v] <- [pom]
    v <- u
    
procedure bracia(K[1..n], v)
    // jesli brat nie istnieje
    if not brat(v) then
        return false
    if (isLeftson(v) and K[v] > K[brat(v)]) or (Rightson(v) and K[v] < K[brat(v)]) then
        zamien(v, brat(v))
        return true
    return false

procedure przesuń-wyżej-prawy(K[1..n], v)
    // Rnode(v) - prawy syn naszego dziadka
    if v > 3 and K[v] > K[Rnode(v)] then
        zamien(v, Rnode(v)
        przesuń-wyżej-prawy(K[1..n], v)

procedure przesuń-wyżej-lewy(K[1..n], v)
    // Lnode(v) - lewy syn naszego dziadka
    if v > 3 and K[v] < K[Lnode(v)] then
        zamien(v, Lnode(v))
        przesuń-wyżej-lewy(K[1..n], v)
        
procedure przesuń-dziura(K[1..n], v)
    if LastLayer(v) then
        return
    if isLeftson(v) then
        if K[Lewysyn(v)] < K[Lewysyn(brat(v))] then
            zamien(v, Lewysyn(v))
        else
            zamien(v, Lewysyn(brat(v)))
    else
        if K[Prawysyn(v)] > K[Prawysyn(brat(v))] then
            zamien(v, Prawysyn(v))
        else
            zamien(v, Prawysyn(brat(v)))
    przesuń-dziura(K[1..n], v)

procedure przesuń-niżej(K[1..n], v)
    // bracia zamieni nam wierzchołki
    if bracia(K[1..n], v) then
        v <- brat(v)
    if LastLayer(v) then
        return
    if isLeftson(v) then
        if K[Lewysyn(v)] < K[Lewysyn(brat(v))] then
            if K[v] < K[Lewysyn(v)] then
                zamien(v, Lewysyn(v))
        else 
            if K[v] < K[Lewysyn(brat(v))] then
                zamien(v, Lewysyn(brat(v)))
    else
        if K[Prawysyn(v)] > K[Prawysyn(brat(v))] then
            if K[v] > K[Prawysyn(v)] then
                zamien(v, Prawysyn(v))
        else 
            if K[v] > K[Prawysyn(brat(v))] then
                zamien(v, Prawysyn(brat(v)))
    przesuń-niżej(K[1..n], v)
    
procedure wstaw(K[1..n], val)
    n = n+1
    v = n
    K[v] = val
    // naprawianie relacji z bratem
    if brat(v) then
        bracia(K[1..n], v)
    else if K[v] < K[Lnode(v)] then
        zamien(v, Lnode(v))
    else if K[v] > K[Rnode(v)] then
        zamien(v, Rnode(v))
    
    if isLeftson(v) then
        przesun-wyżej-lewy(K[1..n], v)
    else
        przesun-wyżej-prawy(K[1..n], v)
        
procedure delete-min(K[1..n])
    K[2] <- K[n]
    n = n-1
    przesuń-niżej(K[1..n], 2)

procedure delete-max(K[1..n])
    K[3] <- K[n]
    n = n-1
    przesuń-niżej(K[1..n], 3)

## Zadanie 1.7

https://pl.wikipedia.org/wiki/Algorytm_Floyda-Warshalla

$A = \{x : x \notin\{v_1, v_2, ..., v_k\}\}$

wszystkie elementy z $A$ $v_k, v_{k-1}, ... v_2, v_1$
$n - k + i$
$D_i$

Floyd-Warshall(G,w)

dla każdego wierzchołka v1 w V[G] wykonaj
  dla każdego wierzchołka v2 w V[G] wykonaj
    d[v1][v2] = nieskończone
    poprzednik[v1][v2] = niezdefiniowane
  d[v1][v1] = 0
dla każdej krawędzi (v1,v2) w E[G]
  d[v1][v2] = w(v1,v2)
  poprzednik[v1][v2] = v1
dla każdego wierzchołka u w V[G], w zmodyfikowanej kolejności, wykonaj
  dla każdego wierzchołka v1 w V[G] wykonaj
    dla każdego wierzchołka v2 w V[G] wykonaj
      jeżeli d[v1][v2] > d[v1][u] + d[u][v2] to
        d[v1][v2] = d[v1][u] + d[u][v2]
        poprzednik[v1][v2] = poprzednik[u][v2]

## Zadanie 2.2

Posortuj odcinki względem ich końca. 
Wybierz odcinek który kończy się najwcześniej.
Wynik<-1
Koniec(//jest to koniec naszego najpóźniejszego odcinka)<- odc.koniec
Dla każdego odcinka o z listy:
    Jeśli o.start>koniec:
        Wynik<-Wynik+1
        Koniec<-o.koniec

A - uporządkowanie naszego algorytmu
O - ułozenie optymalne

Wybieramy pierwsza pare odcinkow, ktora sie rozni tzn. nasz algorytm wybral inny odcinek niz ten ktory wybral algorytm optymalny (patrzac po koncach). Niech to bedzie $A_i$ i $O_i$
* $O_i$ konczy sie wczesnij niz $A_i$
* $O_i$ konczy sie wtedy co $A_i$