Search
Mějme tři nádoby o objemu 2, 5, 9. S nádobami můžeme provádět následující akce:
Napište program, který najde nejmenší počet kroků takový, že v poslední nádobě bude objem 6.
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é.
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]]
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:
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:
Předpokládejme, že máme existující binární haldu. Vložení prvku se provede takto:
Tento algoritmus se nazývá bubble-up, jelikož při něm procházíme haldu ze spodní úrovně nahoru.
Nejjednodušší realizací binární haldy je implementaci na poli. Použijeme jednoduchý trik:
# 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
Implementujte metody pro odebrání prvku na pozici i z binární haldy:
delete(i)
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]
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']]
conv={'I':1,'V':5,'X':10,'L':50,'C':100,'D':500,'M':1000}
Lehká úloha Testovací data lehká úloha
Těžká úloha Testovací data těžká úloha