Prioritätenliste

Klasse PriorityQueue (als Heap)

 aufwärts

Die Prioritäten­liste ist hier als Heap implementiert. Dadurch benötigen sowohl insert als auch extract nur O(log(n)) Schritte.

Beim Aufruf des Konstruktors wird mit dem Parameter updown = 1 oder updown = -1 festgelegt, ob mit extract das Paar mit dem höchsten oder mit dem niedrigsten Zahlenwert zurück­gegeben werden soll.

 

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

 

up

 

homeH.W. Lang   Hochschule Flensburg   lang@hs-flensburg.de   Impressum   Datenschutz   ©   Created: 06.02.2009   Updated: 17.06.2018
Valid HTML 4.01 Transitional

Hochschule Flensburg
Campus Flensburg

Informatik in Flensburg studieren...

 

Neu gestaltetes Studienangebot:

Bachelor-Studiengang
Angewandte Informatik

mit Schwerpunkten auf den Themen Software, Web, Mobile, Security und Usability.

Ihr Abschluss
nach 7 Semestern:
Bachelor of Science

 

Ebenfalls ganz neu:

Master-Studiengang
Angewandte Informatik

Ein projektorientiertes Studium auf höchstem Niveau mit den Schwerpunkten Internet-Sicherheit, Mobile Computing und Human-Computer Interaction.

Ihr Abschluss
nach 3 Semestern:
Master of Science

 

Weitere Informatik-Studienangebote an der Hochschule Flensburg:

Medieninformatik

Wirtschaftsinformatik