Prioritätenliste

class PriorityList(list):

    # Parameter updown=+1 oder -1:
    # extract liefert maximales oder minimales Element
    def __init__(self, updown=1):
        self.updown=updown
    
    # fuegt ein Objekt mit einer Prioritaet ein
    def insert(self, priority, item=None):
        x=[priority, item]
        self.append(x)
        self.upheap()
    
    # gibt das groesste bzw. das kleinste Element zurueck,
    # je nach dem, ob updown=+1 oder -1 ist
    def extract(self):
        self.exchange(self.root(), self.lastLeaf())
        q=self.pop()          # letztes Element entfernen
        self.downheap()
        return q
    
    def upheap(self):
        v=self.lastLeaf()
        while not self.isRoot(v):
            u=self.pred(v);          # u ist Vorgaenger
            if self.p(u)>=self.p(v): # u hat die Heap-Eigenschaft
                return
            else:
                self.exchange(u, v)
                v=u                  # weiter mit u

    def downheap(self):
        v=self.root()
        while not self.isLeaf(v):
            w=self.succ(v);          # erster Nachfolger
            if self.exists(w+1):     # gibt es einen zweiten Nachfolger?
                if self.p(w+1)>self.p(w):
                    w+=1
            # w ist der Nachfolger mit der groesseren Markierung
            if self.p(v)>=self.p(w): # v hat die Heap-Eigenschaft
                return   
            else:
                self.exchange(v, w)
                v=w                  # weiter mit w

    # liefert die Prioritaet von Eintrag v
    def p(self, v):
        return self.updown*self[v][0]

    # vertauscht Eintraege u und v
    def exchange(self, u, v):
        self[u], self[v]=self[v], self[u]

    # letzter Knoten
    def lastLeaf(self):
        return self.size()-1

    # Wurzel
    def root(self):
        return 0

    # Vorgaenger
    def pred(self, v):
        return (v-1)//2

    # erster Nachfolger
    def succ(self, v):
        return v*2+1

    # v ist die Wurzel
    def isRoot(self, v):
        return v==0;

    # v ist Blatt
    def isLeaf(self, v):
        return v>=self.size()//2;

    # vorhanden
    def exists(self, v):
        return v<self.size()
    
    # ergibt die Laenge der Liste
    def size(self):
        return len(self)

    # true, wenn die Liste leer ist
    def isEmpty(self):
        return self.size()==0

# Test

if __name__=="__main__":
    p=PriorityList(-1)
    p.insert(6, "f")
    p.insert(5, "e")
    p.insert(1, "a")
    print(p.extract())
    p.insert(3, "c")
    p.insert(4, "d")
    p.insert(2, "b")
    print(p.extract())
    print(p.extract())
    print(p.extract())
    print(p.extract())
    print(p.extract())