heap.py

Dateiinhalt

# Priority-Queue mit Listen-Heap
# SH 2012-12-16

class Heap(list):
    """Klasse implementiert einfache Liste"""
    def __init__(self):
        self.append(('start',0))                        # fixes Startelement

    def __repr__(self):                                 # Ausgabe Konsole
        return str(self[1:])                            # wandle in str um
                                                        # ohne erstes Element!
    def __str__(self):                                  # Ausgabe via print()
        ausgabe = ""
        for i in self[1:]:
            ausgabe+="%10s:%4.1f\n"%i
        return "\nPrio-Warteschlange:\n"+ausgabe
        #return str(self[1:])                            # wie oben

    def einfügen(self, element, prio, verbose=True):    # neues Element einfügen
        "Einfügen eines Knoten am Ende (ws)"
        self.append((element, prio))                    # hinten einfügen
        self.bubbleUp()                                 # hochblubbern lassen
        if verbose:                                     # Im Normalfall...
            print("%10s:%4.1f -> enqueued!"%(element,prio))          # ...gib Rückmeldung
        
    def entfernen(self, verbose=True):                  # kleinstes ausgeben
        "erstes Listenelement ausgeben" 
        erstes = self.pop(1)                            # speichern ...            
        self.insert(1,self.pop())                       # letztes nach vorne
        self.sirtDown()                                 # durchsickern lassen
        if verbose:                                     # Im Normalfall...
            print("dequeued -> %10s:%4.1f"%erstes)                   # ...mit Rückmeldung
        return erstes                                   # Ausgabe
             
    def sirtDown(self, index=1):                        
        "siebt neuen Knoten nach unten durch"
        try:                                            # fängt Indexfehler ab
            if self[index][1] > self[index*2][1]:       # Vgl. lnach...?                                # vater>lnach?
                self[index],self[index*2] = self[index*2],self[index]#...tauschen                 # l nach oben
            if self[index][1] > self[index*2+1][1]:     # Vgl. rnach ...?
                self[index],self[index*2+1] = self[index*2+1],self[index]#...tauschen
            self.sirtDown(index*2)                      # Index verdoppeln
        except:
            pass
        
    def bubbleUp(self):
        "blubbert neue Einträge nach oben"
        index=len(self)-1                               # letzter Element-Index
        while index>1:                                  # untere Grenze
            if self[index][1] < self[index//2][1]:      # Prio-Vergleich...
                self[index],self[index//2] = self[index//2],self[index]#...tauschen
                index=index//2                          # Index halbieren, ganzzahlig
            else:
                break                                   # Abbruchbedingung 
            
    def neuePrio(self, element, prioAlt, prioNeu):
        "ändert Priorität eines Elements"
        print("\nPrio-Wechsel bei '%s': %4.1f statt %4.1f\n"
              %(element, prioNeu, prioAlt))
        self.remove((element,prioAlt))                  # Element entfernen...
        self.einfügen(element, prioNeu)                 # ... mit neuer Prio
                                                        # wieder einfügen

if __name__=="__main__":
    h=Heap()
    h.einfügen("sechstes",6)
    h.neuePrio("sechstes",6,16)
    h.einfügen("drittes",3)
    h.einfügen("fünftes",5)
    h.einfügen("erstes",1)
    h.einfügen("zweites",2)
    h.einfügen("viertes",4)
    h.einfügen("siebtes",7)
    h.einfügen("achtes",8)
    print(h)

    while True:
        try:
            h.entfernen()
        except IndexError:
            print("Schlange leer!")
            break