Prioritätenliste

Klasse PriorityQueue (als sortierte Liste)

 aufwärts

Die Prioritäten­liste ist hier der Einfachheit halber als sortierte Liste implementiert. Die Liste wird jeweils neu sortiert, bevor ein Element mit extract ausgegeben wird, nachdem vorher Elemente mit insert eingefügt worden sind.

Im schlechtesten Fall benötigt extract daher Θ(n log(n)) Schritte, wobei n die Länge der Liste ist; insert benötigt O(1) Schritte. Bei einer Implementierung als Heap benötigen die Operationen extract und insert jeweils Θ(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 PriorityQueue(list):

    # Parameter updown=+1 oder -1:
    # extract liefert maximales oder minimales Element
    def __init__(self, updown=1):
        self.updown=updown
        self.sorted=True
    
    # fuegt ein Objekt mit einer Prioritaet ein
    def insert(self, priority, item=None):
        x=[priority, item]
        self.append(x)
        self.sorted=False
    
    # gibt das groesste bzw. das kleinste Element zurueck,
    # je nach dem, ob updown gleich +1 oder -1 ist
    def extract(self):
        if not self.sorted:
            self.sort(reverse=self.updown<1)
            self.sorted=True
        return self.pop()
        
    # 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=PriorityQueue(-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