Skip to content

Instantly share code, notes, and snippets.

@honzakral
Forked from EmmetBrickHacker/haldy.py
Last active August 29, 2015 14:05
Show Gist options
  • Save honzakral/c566333961ad7bb101eb to your computer and use it in GitHub Desktop.
Save honzakral/c566333961ad7bb101eb to your computer and use it in GitHub Desktop.
# -*- coding: cp1250 -*-
class Halda():
"""halda - dokumentace
TYP 1A na vrcholu nejmenší hodnota, prosté položky
TYP 1B na vrcholu nejmenší hodnota, strukturované položky
TYP 2A na vrcholu největší hodnota, prosté položky
TYP 2B na vrcholu největší hodnota, strukturované položky
"""
### 0 Konstrukční procedury
def __init__(self, order = "<", value_index = -1):
self._data = []
self.value_index = value_index
self.order = order
def __getitem__(self, key):
return self._data[key]
def __setitem__(self, i, y):
return self._data.__setitem__(i,y)
def __len__(self):
return self._data.__len__()
### 1 Informativní funkce
def last_index(self):
"""
Vrátí index poslední položky v haldě.
V případě, že je halda prázdná, vrátí None.
"""
if len(self) == 0:
return None
return self._data.index(self[-1])
def peak(self):
"""
Vrátí kořen haldy.
V případě, že je halda prázdná, vrátí None.
"""
if len(self) == 0:
return None
return self[0]
def deep(self):
"""
Vrátí hloubku haldy, tj. počet uzlů v nejdelší cestě
od kořene k listu.
V případě, že je halda prázdná, nastaví hloubku 0.
"""
if len(self) == 0: # pokud je halda prázdná, vrátí hloubku 0
return 0
from math import log
deep = log(len(self),2)
deep = int(deep) + 1
return deep
### 2 Funkce pro vyhledávání v haldě
def _parent(self, child):
"""
Vrátí index rodiče zadaného uzlu.
:arg child: index dítěte, jehož rodiče hledáme.
"""
if child == 0:
return None
return (child - 1)/2
def _left_child(self, parent):
"""
Vrátí index pozice, na které by se mělo nacházet
levé dítě zadaného uzlu.
Nekontroluje, jestli dítě skutečně existuje!
:arg parent: index rodičeho, jehož levé dítě hledáme.
"""
return parent*2 + 1
def _right_child(self, parent):
"""
Vrátí index pozice, na které by se mělo nacházet
pravé dítě zadaného uzlu.
Nekontroluje, jestli dítě skutečně existuje!
:arg parent: index rodičeho, jehož pravé dítě hledáme.
"""
return parent*2 + 2
### 3 Porovnávání a uspořádání položek v haldě
def value(self, index):
"""
Vrátí porovnávanou hodnotu zadané položky v haldě.
:arg index: index položky, jejíž hodnotu chceme znát.
"""
if self.value_index == -1:
return self[index]
return self[index][self.value_index]
def _check_existence(self, index):
"""
Zkontroluje, zda v haldě existuje prvek se zadaným indexem.
"""
if index >= 0 and index <= self.last_index():
return True
else:
return False
def _cmp(self, a, b):
if self.order == "<":
return a <= b
return a >= b
def _choose_child(self, left_child, right_child):
"""
Porovná oba potomky rodiče a vrátí index toho významnějšího
pro kontrolu uspořádání.
:arg left_child: index levého dítěte.
:arg right_child: index pravého dítěte.
"""
if self._cmp(self.value(left_child), self.value(right_child)):
return left_child
return right_child
def _order_up(self, index = -1):
"""
Projde haldu od zadaného indexu směrem ke kořeni (nahoru)
a zajistí uspořádání procházené větve.
:arg index: index uzlu, od něhož chceme zajisti uspořádání,
defaultní hodnota odkazuje k poslední položce
v haldě.
Pokud by byl zadán index kořenového uzlu, procedura
se ukončí - není již co kontrolovat.
"""
if index == -1:
index = self.last_index()
elif index == 0: # byl zadán index kořenového uzlu
return # a procedura se ukončí
parent = self._parent(index)
if not self._cmp(parent, index):
self[parent], self[index] = self[index], self[parent]
self._order_up(parent)
def _order_down(self, index = 0):
"""
Projde haldu od zadaného indexu směrem k listu (dolů)
a zajistí uspořádání procházené větve.
:arg index: index uzlu, od něhož chceme zajisti uspořádání,
defaultní hodnota odkazuje ke kořeni haldy.
Pokud by byl zadán index kořenového uzlu, procedura
se ukončí - není již co kontrolovat.
"""
if not self._check_existence(index):
return
left_child = self._left_child(index)
right_child = self._right_child(index)
if not self._check_existence(left_child):
return
elif not self._check_existence(right_child):
child = left_child
else:
child = self._choose_child(left_child, right_child)
if not self._cmp(index, child):
self[child], self[index] = self[index], self[child]
self._order_down(child)
### 4 Operace pro přidávání a odebírání z haldy
def push(self, item):
"""
Přidá položku do haldy.
:arg item: položka jíž přidáváme do haldy. Je třeba, aby měla
odpovídající formát.
"""
self._data.append(item)
if len(self) > 1:
self._order_up()
def pop(self):
"""
Odebere z haldy kořenovou položku a vrátí její hodnotu.
Halda se následně přerovná do odpovídajícího uspořádání.
"""
if len(self) == 0:
return None
root = self.peak()
self[0] = self[-1]
del self._data[-1]
self._order_down()
return root
### 5 Zobrazení struktury haldy
def draw(self):
"""
Vykreslí haldu pomocí ASCII artu.
"""
from math import log
deep = self.deep()
i = 0
for d in range(deep):
act_deep = int(log(i+1,2)) # aktuální hladina stromu
diff_deep = deep-1 - act_deep # rozdíl maximální a aktuální hladiny
line01 = ""
line02 = ""
while int(log(i+1,2)) == act_deep:
if act_deep > 0:
if i % 2 == 1:
line01 += ((2**diff_deep)-1)*"{0: >5}".format(" ")
line01 += " ,----"
line01 += ((2**diff_deep)-1)*5*"-" + "^"
else:
line01 += ((2**diff_deep)-1)*5*"-"
line01 += "----, "
line01 += ((2**diff_deep)-1)*"{0: >5}".format(" ")
line02 += ((2**diff_deep)-1)*"{0: >5}".format(" ")
line02 += "{0:>5}".format("["+str(i)+"]") + " " + "{0: <4}".format(str(self.value(i)))
line02 += ((2**diff_deep)-1)*"{0: >5}".format(" ")
if i < (len(self)-1):
i+= 1
else:
break
print line01
print line02
class HeapSort(Halda):
def __init__(self, data, order='>', value_index=-1):
self._data = data
self.value_index = value_index
self.order = order
self._order_down()
def heapsort(data):
heap = HeapSort(data)
while len(heap):
print heap.pop()
def test():
heapsort([2, 5, 1, 10])
"testovací data"
print "================"
print "[Testuji TYP 1A]"
print "================"
h = Halda()
h.push(1)
h.push(9)
h.push(2)
h.push(8)
h.push(3)
h.push(7)
h.push(4)
h.push(6)
h.push(5)
h.push(0)
h.draw()
print
print "================"
print "[Testuji TYP 1B]"
print "================"
h = Halda("<",0)
h.push([1])
h.push([9])
h.push([2])
h.push([8])
h.push([3])
h.push([7])
h.push([4])
h.push([6])
h.push([5])
h.push([0])
h.draw()
print
print "================"
print "[Testuji TYP 2A]"
print "================"
h = Halda(">")
h.push(1)
h.push(2)
assert h.peak() == 2
h.push(8)
assert h.peak() == 8
h.push(9)
assert h.peak() == 9
h.push(3)
h.push(7)
h.push(4)
h.push(6)
h.push(5)
h.push(0)
h.draw()
assert h.pop() == 9
print
print "================"
print "[Testuji TYP 2B]"
print "================"
h = Halda(">",0)
h.push([1])
h.push([9])
h.push([2])
h.push([8])
h.push([3])
h.push([7])
h.push([4])
h.push([6])
h.push([5])
h.push([0])
h.draw()
if __name__ == '__main__':
test()
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment