====== Cvičení 11: Objekty, halda, asociativní pole ======





==== Přelévání nádob ====

Mějme tři nádoby o objemu 2, 5, 9. S nádobami můžeme provádět následující akce:
  * **Nx**: napusť plnou nádobu X, kde X je v rozsahu 0,1,2
  * **Vx**: vylij celou nádobu X, kde X je v rozsahu 0,1,2
  * **xPy**: přelij nádobu X do nádoby Y, kde X a Y jsou různá čísla z rozsahu 0,1,2:
    * pokud se celý objem z X nevejde do Y, odlije se voda z X tak, aby se Y naplnila
Napište program, který najde nejmenší počet kroků takový, že v poslední nádobě bude objem 6.

==== Pohyb koně na šachovnici ====

Naplánujte nejkratší cestu pro šachového koně z políčka 2 na políčko 4. Sudá čísla znamenají volné políčko, lichá čísla obsazené.

<code>
m=[[0,0,0,0,0,0,0,0],
   [0,0,0,0,0,0,4,0], 
   [0,0,0,0,1,0,0,0], 
   [1,1,1,0,1,1,0,0], 
   [0,0,0,1,0,1,0,0], 
   [0,2,0,0,0,1,0,0], 
   [0,0,0,0,0,1,0,0], 
   [0,0,0,0,0,1,0,0]]
</code> 


==== Binární halda ====

[[https://en.wikipedia.org/wiki/Binary_heap |  Binární halda ]] je binární stromová datová struktura. Je tvořena uzly, které mají max. dva potomky (levý a pravý potomek) (odtud přídavné jméno binární), pričemž potomek je opět uzel. Její důležitou vlastností je, že:
   * hodnota každého uzlu je **rovna nebo menší** než hodnoty jejich potomků.  
   * Pokud je tato vlastnost splněna tak platí, že prvek v tzv. kořenu stromu obsahuje **nejmenší** prvek mezi všemi prvky.
   * <fc #ff0000>**V tomto cvičení budeme předpokládat tuto variantu.**</fc>
   * Takové haldě se někdy říká min-halda.


Binární haldu lze samozřejmě realizovat i s opačnou vlastností:
   * hodnota každého uzlu je **rovna nebo větší** než hodnoty jejich potomků.  
   * Pokud je tato vlastnost splněna tak platí, že prvek v tzv. kořenu stromu obsahuje **největší** prvek mezi všemi prvky.
   * Takové haldě se říká max-halda.

Použití binární haldy:
   * Pro realizaci prioritní fronty, v důsledku toho např. pro hledání cest v grafech, mapách, plánování pohybu robotů



{{courses:b3b33alp:cviceni:heap.png?400|}}


=== Binární halda: vyjmutí nejmenšího prvku ===

Předpokládejme, že máme existující binární haldu. Při vyjmutí prvky stačí vzít prvek v kořeni stromu, neboť ten již z definice obsahuje nejmenší hodnotu mezi všemi uzly.
Po odebrání prvku je ale nutné zbylé prvky přeskupit a určit nový kořen haldy. Postup je:

  * Vyjmout prvek z kořene haldy ( prvek s nejmenší hodnotou )
  * Vzít poslední prvek v poslední úrovni a přesunout na pozici kořene.
  * Nyní je třeba nahrat prvky v haldě tak, aby byla splněna vlastnost min-haldy. Jelikož budeme začínat od kořene a procházet strom směrem dolu, říká se tomuto postupu tzv. bubble-down.
  
  
==Bubble-down:==
  * Předpokládejme, že jsme v uzlu $U$.
  * Porovnáme hodnotu $U$, $U$.left a $U$.right. Pokud je splěna vlastnost min-haldy (tj. hodnota $U$ je menší nebo rovna hodnotám jejích potomků), končíme.
  * Pokud ne, vybereme toho potomka, který je menší než $U$. Vyměníme hodnotu $U$ s tímto potomek. 
  * Pokračujeme bubble-down z tohoto potomka.
  * Algoritmus končí, pokud už jsme narazili na uzel bez potomka.


=== Binární halda: vložení prvku ===

Předpokládejme, že máme existující binární haldu. Vložení prvku se provede takto:

===Bubble-up===
  * Vložíme prvek na poslední nejpravější místo v poslední úrovni.
  * Porovnáme hodnotu tohoto prvku s jeho rodičem. Pokud je splněna vlastnost haldy (tj. u min-haldy: hodnota prvku je větší nebo rovna hodnotě jeho rodiče), pak končíme.
  * Pokud ne, vyměníme hodnotu prvku za hodnotu rodiče a opakujeme tento postup od změněného rodiče.
 
Tento algoritmus se nazývá bubble-up, jelikož při něm procházíme haldu ze spodní úrovně nahoru.


==== Realizace binární haldy na poli ====

Nejjednodušší realizací binární haldy je implementaci na poli. Použijeme jednoduchý trik:

  * Nechť uzel má v poli index $i$.
  * Jeho levý potomek má v poli index $2i+1$.
  * Jeho pravý potomek má v poli index $2i+2$.

{{courses:b3b33alp:cviceni:heap1.png?200|}}

  * Jaký je index rodiče, pokud má potomek index v poli $i$?


=== Implementace haldy z přednášky ===

<code python>
# Implementace haldy
#
# http://interactivepython.org/runestone/static/pythonds/Trees/BinaryHeapImplementation.html
# Jan Kybic, 2016

class MinHeap:
  """ binarni halda __init__ konstruktor """
  def __init__(self):
     self.heap = [] # indexujeme od nuly

  def bubble_up(self,i):
    """ probubla prvek i nahoru, zajisti splneni podminek haldy """
    while i>0:
      j=(i-1)//2 # index rodice
      if self.heap[i] >= self.heap[j]:
        break
      self.heap[j],self.heap[i]=self.heap[i],self.heap[j]
      i = j
  
  def insert(self,k):
    """ vloz prvek do haldy """    
    self.heap+=[k]
    self.bubble_up(len(self.heap)-1)

  def peek(self):
    """ vrati nejmensi prvek """
    return self.heap[0]

  def size(self):
    """ vrati pocet prvku v halde """
    return len(self.heap)

  def is_empty(self):
    """ je halda prazdna? """
    return self.size()==0 
  
  def bubble_down(self,i):
     """ probublej prvek dolu """
     n=self.size()
     while 2*i+1 < n:
        j=2*i+1 # zjisti index leveho potomka
        if j+1 < n and self.heap[j] > self.heap[j+1]:
          j+=1
        if self.heap[i]>self.heap[j]:
          self.heap[i],self.heap[j]=self.heap[j],self.heap[i]
        i=j
                  
  def pop(self):
    """ odebere nejmensi prvek a uprav haldu """
    element=self.heap[0]
    self.heap[0]=self.heap[-1]
    self.heap.pop() # smaz posledni prvek
    self.bubble_down(0)
    return element
</code>

==== Implementace funkce delete ===

Implementujte metody pro odebrání prvku na pozici i z binární haldy:

  * Metodu pojmenujte ''delete(i)''
  * metoda dále smaže tento prvek z haldy
  * ošetřete tuto metodu tak, aby ji bylo možné volat i na prázdnou haldu, případně pokud je i větší než velikost haldy

Pomocí této funkce smažte z haldy vytvořené z pole všechna sudá čísla (Nejdříve haldu vytvořte se všemi čísly a pak smažte všechna sudá čísla z haldy):
<code>
pole=[10,21,7,11,31,6,1,-11,31,42,-12,80,25,-7,-12,9,14]
</code>

==== Karty v haldě ====
  * Upravte implementaci haldy tak, aby byla realizována min-halda s kartami ve formátu cvičení 7 příklad 6.
  * Vytvořte haldu z následujících karet:
<code>
cards = [[0, 'Q'], [2, '6'], [1, 'K'], 
         [1, '8'], [2, '10'], [2, '4'], 
         [3, '4'], [0, '4'], [1, '3'], 
         [2, '5'], [0, 'K'], [3, 'A'], 
         [1, 'J'], [0, '3'], [0, '9']]
</code>  
  * V cvičení 8 jsme pro porovnání karet využívali funkci index a dvojího porovnání (nejdříve barvu a pak hodnotu). Nyní definujte pořadí pomocí asociativního pole a operací sčítání a násobení.
==== Asociativní pole a římská čísla ====
  * Využijte následující asociativní pole k převodu římského čísla na dekadické číslo:
<code>
conv={'I':1,'V':5,'X':10,'L':50,'C':100,'D':500,'M':1000}
</code>
  * Převeďte na číslo např. MCMXCIX


===== Domácí úkol =====

{{ :courses:b3b33alp:cviceni:l_zadani_10.pdf |Lehká úloha}}   {{ :courses:b3b33alp:cviceni:rotace.tgz | Testovací data lehká úloha}}

{{ :courses:b3b33alp:cviceni:t_zadani_10.pdf |Těžká úloha}}   {{ :courses:b3b33alp:cviceni:zkumavky.tgz | Testovací data těžká úloha}}