Prioritätenliste

Klasse PriorityQueue (als sortierte Liste)

Die Prioritätenliste 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ückgegeben 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]

H.W. Lang mail@hwlang.de Impressum Datenschutz
Created: 06.02.2009 Updated: 19.02.2023
Diese Webseiten sind während meiner Lehrtätigkeit an der Hochschule Flensburg entstanden