Table of Contents

Cvičení 11 Halda, asociativní pole

náplň cvičení

Úkol 1: Genealogie

class Person:
    def __init__(self, name, sex):
        self.name = name
        self.sex = sex   
        self.children = []  
        self.parents = []   # parents of this node
        self.partner = None   # partner (=husband/wife of this node)
 
    def addChild(self, node):
        self.children.append(node)
 
    def addParent(self, node):
        self.parents.append(node)
 
    def setPartner(self, node):
        self.partner = node
 
    def __repr__(self):
        s = "Female" if self.sex == 'F' else "Male" 
        return self.name + " " + s

Vstupní soubor family.txt: 

M Jana Jan F M
P Jana Martin F M
P Jana Robert F M
P Robert Gabriel M M
P Robert Oleg M M
P Robert Ondrej M M
P Martin Jiri M M
P Martin Rudolf M M
P Jan Petra M F
P Jan Uxana M F
P Uxana Klara  F F
P Uxana Jakub F M
P Uxana Adam F M
P Petra Alex F M
P A C M M
P A D M F
P D K F F
P C J M M 
P C I M F
P C H M M
P B E F F
P B F F M 
P B G F F

Schéma rodiny ve family.txt:

Prémie navíc: zobrazení přes dot format

Uložení načtených dat do ' Dot ' souboru, který lze pak vykreslit do png nástrojem dot z balíku nástrojů Graphviz: 

dot -Tpng family.dot  > family.png

Příklad family.dot: 

digraph G {
Jana[ color=red];
Jana->Martin [label="child"];
Jana->Robert [label="child"];
Jana->Jan[color=blue; penwidth=4];
Jan[ color=green];
Jan->Petra [label="child"];
Jan->Uxana [label="child"];
Jan->Jana[color=blue; penwidth=4];
Martin[ color=green];
Martin->Jiri [label="child"];
Martin->Rudolf [label="child"];
Martin->Jana [style=dashed];
...
}

Binární halda

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:

Binární haldu lze samozřejmě realizovat i s opačnou vlastností:

Použití binární haldy:

Binární halda: vyjmutí 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:

Bubble-down:

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

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:

Implementace haldy z přednášky

# Implementace haldy
#
# http://interactivepython.org/runestone/static/pythonds/Trees/BinaryHeapImplementation.html
# Jan Kybic, 2016
 
class MinHeap:
  """ binární halda, implementovaná pomocí metod """
  def __init__(self):
     self.heap = [] # indexujeme od nuly
 
  def bubble_up(self,i):
    """ probublá prvek 'i', zajistí splnění vlastnosti haldy """
    while i>0:
      j=(i-1)//2 # index rodiče  
      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):
    self.heap+=[k]
    self.bubble_up(len(self.heap)-1)
 
  def peek(self):
    """ vrátí nejmenší prvek """
    return self.heap[0]
 
  def size(self):
    return len(self.heap)
 
  def is_empty(self):
    return self.size()==0 
 
  def bubble_down(self,i):
     n=self.size()
     while 2*i+1 < n:
        j=2*i+1 # zjisti index menšího syna
        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):
    """ odeber a vrať nejmenší prvek """
    element=self.heap[0]
    self.heap[0]=self.heap[-1]
    self.heap.pop() # smaž poslední prvek
    self.bubble_down(0)
    return element

Úkol 1: implementace funkce delete

Implementujte metody pro odebrání prvku na pozici i z binární 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): 

pole=[10,21,7,11,31,6,1,-11,31,42,-12,80,25,-7,-12,9,14]

Úkol 2: Karty v haldě

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']]

Úkol 3: Asociativní pole a římská čísla

conv={'I':1,'V':5,'X':10,'L':50,'C':100,'D':500,'M':1000}

domácí práce

Lehčí varianta:

Příklad

24 K
13 H
25 R
 1 M
-4 T0
 4 C
-4 T1
-3 T2
15 G
12 Y

T0: R K H M
T1: C
T2:
Depo: G Y

* Výstup:

Těžší varianta:

Úkolem je implementovat kódování a dekódování textu pomocí Hammingova kódu Hamming(8,12) - tedy na 8 bitů kódu znaku, se použijí 4 bity pro opravu. 

cAhoj Hammingu!

001000010010
010100100110
011111100110
110010100110
010000010100
000100110010
011000000110
111001100110
111001100110
101100100110
100111100110
101011000110
101101011110
101000010100

d
001000010110
010100100111
011111100100
110010110110
010010010100
000100010010
011000000100
111011100110
111001100100
101100100111
100110100110
101001000110
101001011110
100000010100

Ahoj Hammingu!