halda jako třída

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):
        ORDER = ["<", ">"]
        if order not in ORDER:
            raise ValueError("Neplatný typ uspořádanání")
        if not (type(value_index) == int and value_index >= -1):
            raise ValueError("Index porovnávané hodnoty musí být přirozené číslo, nebo -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 __delitem__(self, item):
        del self._data[item]

    def __len__(self):
        return self._data.__len__()

    def __repr__(self):
        return self._data.__repr__()

    def __str__(self):
        return self._data.__str__()

### 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 len(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]
        ### V případě, že budeme chtít porovnávat podle něčeho jiného
        ### než podle číselných hodnot, stačí upravit tuto metodu

    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, sup, sub):
        """
        Vrátí porovnání, které by mělo odpovídat nastavenému uspořádání.

        :arg sup: index položky, která by v uspořádání měla být výše.
        :arg sub: index položky, která by v uspořádání měla být níže.
        """
        if self.order == "<":
            return self.value(sup) <= self.value(sub)
        elif self.order == ">":
            return self.value(sup) >= self.value(sub)

    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 not ((right_child == left_child + 1) and (right_child%2 == 0)):
            raise ValueError("Zadané indexy neodpovídají dětem žádného uzlu v haldě!")
        if self._cmp(left_child,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[-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 VirtualHeap(Halda):
    """
    Vytvoří uvnitř seznamu virtuální haldu, který slouží k rychlejšímu tídění
    """
    def __init__(self, data, order = "<", value_index = -1):
        ORDER = ["<", ">"]
        if order not in ORDER:
            raise ValueError("Neplatný typ uspořádanání")
        if not (type(value_index) == int and value_index >= -1):
            raise ValueError("Index porovnávané hodnoty musí být přirozené číslo, nebo -1")
        def invert(order):
            """Vrátí usopřádání opačené vůči zadanému."""
            if order == "<":
                return ">"
            elif order == ">":
                return "<"
            ### prostor pro případné rozšíření o další formy uspořádání
        self._data = data
        self.order = invert(order)
        self.value_index = value_index
        list_ = self
        if len(data):
            self._ordered = 0      # index podlední položky ve virtuální haldě
        else:
            self._ordered = -1

    def __len__(self):
        if len(self._data) == 0:
            return 0
        return (self._ordered + 1)

    def _len_data(self):
        return self._data.__len__()

    def push(self):
        """
        Přidá do virtuál haldy první nezatříděnou položku seznamu.

        Proces se opakuje dokud není virtuální halda vytvořena z celého seznamu
        """
        if self._len_data() < 2:
            return
        while not len(self) == self._len_data():
            self._ordered += 1
            self._order_up(self._ordered)

    def pop(self):
        """
        Odebere z virtuální haldy kořenovou položku a umístí ji do pole
        za poslední položku haldy.
        Virtuální halda se následně přerovná do odpovídajícího uspořádání.

        Proces se opakuje dokud není virtuální halda prázdná.
        """
        while self._ordered:
            self[0], self[self._ordered] = self[self._ordered], self[0]
            self._ordered -= 1
            self._order_down()
            
   
def heapsort(data, order = "<", value_index = -1):
    """
    Setřídí vstupní data pomocí haldy.

    :arg data: data v podobě seznamu, který má být setřízen.
    :arg order: typ uspořádání dat
                value: "<" (defaultní) uspořádání od nejmenší položky k největší,
                       porovnávaná hodnota má podobný čísla.
                value: ">" uspořádání od největší položky k nejmenší,
                       porovnávaná hodnota má podobný čísla.
    :arg value_index: určuje index, pod kterým se v prvku nachází
         porovnávaná hodnota.
                value: "-1" (defaultní) určuje, že prvek nemá žádnou vnitřní
                       strukturu a sám je provnávanou hodnotou.
    """
    data = VirtualHeap(data, order, value_index)
    data.push()
    data.pop()
    data = data._data
##    print data

def hungryheapsort(data, order = "<", value_index = -1):
    """
    Setřídí vstupní data pomocí haldy.

    Tato varianta potřebuje dvojnásobek paměti - slouží jen k testování.

    :arg data: data v podobě seznamu, který má být setřízen.
    :arg order: typ uspořádání dat
                value: "<" (defaultní) uspořádání od nejmenší položky k největší,
                       porovnávaná hodnota má podobný čísla.
                value: ">" uspořádání od největší položky k nejmenší,
                       porovnávaná hodnota má podobný čísla.
    :arg value_index: určuje index, pod kterým se v prvku nachází
         porovnávaná hodnota.
                value: "-1" (defaultní) určuje, že prvek nemá žádnou vnitřní
                       strukturu a sám je provnávanou hodnotou.
    """
    heap = Halda(order, value_index)
    for item in data:
        heap.push(item)
    for i in range(len(data)):
        data[i] = heap.pop()
    
### ==========================
### ===== TESTOVACÍ DATA =====
### ==========================
def test():
    "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()

def test2():
    print
    print "=================="
    print "[Testuji heapsort]"
    print "=================="
    L = [1,9,2,8,3,7,4,6,5,0]
    #L = [1,9,2,8,3,7]
    print "L =", L
    heapsort(L,">")
    # assert L == [0,1,2,3,4,5,6,7,8,9]
    print "heapsort(L) =", L

if __name__ == '__main__':
    test2()