haldy.py

# -*- 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()