In der Informatik ist eine Vorzugswarteschlange ein abstrakter Datentyp, der einer regelmäßigen Warteschlange oder Stapel-Datenstruktur ähnlich ist, aber zusätzlich wird jedes Element mit einem "Vorrang" vereinigt.

• Stapel — Elemente werden im letzten - in "erstem gezogen bestellen" (z.B ein Stapel von Papieren)
• Warteschlange — Elemente werden im ersten - in "erstem gezogen bestellen" (z.B eine Linie in einem Selbstbedienungsrestaurant)
• Vorzugswarteschlange — Elemente werden "höchster Vorrang zuerst" gezogen (z.B in der Linie oder Dienst der wichtigen Persönlichkeit schneidend).

Es ist ein häufiger Irrtum, dass eine Vorzugswarteschlange ein Haufen ist. Eine Vorzugswarteschlange ist ein abstraktes Konzept wie "eine Liste" oder "eine Karte"; da eine Liste mit einer verbundenen Liste oder einer Reihe durchgeführt werden kann, kann eine Vorzugswarteschlange mit einem Haufen oder einer Vielfalt anderer Methoden durchgeführt werden.

Eine Vorzugswarteschlange muss mindestens die folgenden Operationen unterstützen:

• : fügen Sie ein Element zur Warteschlange mit einem verbundenen Vorrang hinzu
• : entfernen Sie das Element von der Warteschlange, die den höchsten Vorrang hat, und geben Sie es zurück (auch bekannt als "pop_element (Von)", "get_maximum_element", oder "get_front (meiste) _element"; eine Vereinbarung denkt niedrigere Prioritäten, höher zu sein, so kann das auch als "get_minimum_element" bekannt sein, und wird häufig genannt, "werden minutig" in der Literatur; die Literatur führt auch manchmal getrennte "peek_at_highest_priority_element-" und "Delete_element"-Funktionen durch, die verbunden werden können, "um pull_highest_priority_element" zu erzeugen)

,

Fortgeschrittenere Durchführungen können mehr komplizierte Operationen wie pull_lowest_priority_element unterstützen, die ersten im höchsten Maße - oder Elemente des niedrigsten Vorrangs untersuchend (nach dem höchsten Vorzugselement guckend, kann O (1) Zeit mit fast allen Durchführungen gemacht werden), die Warteschlange klärend, Teilmengen der Warteschlange klärend, einen Gruppe-Einsatz durchführend, zwei oder mehr Warteschlangen in eine verschmelzend, Vorrang jedes Elements usw. erhöhend.

Ähnlichkeit zu Warteschlangen

Man kann sich eine Vorzugswarteschlange als eine modifizierte Warteschlange vorstellen, aber wenn man das folgende Element von der Warteschlange bekommen würde, wird das Element des höchsten Vorrangs zuerst wiederbekommen.

Stapel und Warteschlangen können als besondere Arten von Vorzugswarteschlangen modelliert werden. In einem Stapel ist der Vorrang jedes eingefügten Elements Monotonically-Erhöhung; so ist das letzte eingefügte Element immer das wiederbekommene erste. In einer Warteschlange ist der Vorrang jedes eingefügten Elements das Monotonically-Verringern; so ist das erste eingefügte Element immer das wiederbekommene erste.

Durchführung

Naive Durchführungen

Es gibt eine Vielfalt von einfachen, gewöhnlich ineffizient, Weisen, eine Vorzugswarteschlange durchzuführen. Sie stellen eine Analogie zur Verfügung, um zu helfen, man versteht, wie eine Vorzugswarteschlange ist. Zum Beispiel kann man alle Elemente in einer unsortierten Liste behalten. Wann auch immer das Element des höchsten Vorrangs gebeten wird, durchsuchen Sie alle Elemente für dasjenige mit dem höchsten Vorrang. (In der großen O Notation: O (1) Einfügungszeit O ziehen (n) Zeit, die erwartet ist zu suchen.)

Übliche Durchführung

Um Leistung besser zu werden, verwenden Vorzugswarteschlangen normalerweise einen Haufen als ihr Rückgrat, O gebend (loggen Sie n) Leistung für Einsätze und Eliminierungen und O (n), um am Anfang zu bauen. Wechselweise, wenn ein selbstbalancierender binärer Suchbaum verwendet wird, nehmen Einfügung und Eliminierung auch O (loggen Sie n) Zeit, obwohl, den Baum von einer vorhandenen Folge von Elementen bauend, nimmt O (n loggen n) Zeit; das ist eine populäre Lösung, wo man bereits Zugang zu diesen Datenstrukturen, solcher als durch Dritt- oder Standardbibliotheken hat.

Bemerken Sie, dass von einer Einstellung der rechenbetonten Kompliziertheit Vorzugswarteschlangen zum Sortieren von Algorithmen gleichwertig sind. Sieh die folgende Abteilung dafür, wie effiziente Sortieren-Algorithmen effiziente Vorzugswarteschlangen schaffen können.

Es gibt mehrere Spezialhaufen-Datenstrukturen, dass entweder zusätzliche Operationen liefern Sie oder die obengenannten Annäherungen überbieten Sie. Der binäre Haufen verwendet O (loggen Sie n) Zeit für beide Operationen, aber erlaubt, nach dem Element vom höchsten Vorrang zu gucken, ohne es in der unveränderlichen Zeit zu entfernen. Binomische Haufen fügen noch mehrere Operationen hinzu, aber verlangen O (loggen Sie n) die Zeit für das Gucken. Haufen von Fibonacci können Elemente, Piepsen am höchsten Vorzugselement einfügen, und einen Vorrang eines Elements in der amortisierten unveränderlichen Zeit vergrößern (Auswischen ist noch O (loggen Sie n)).

Während das Verlassen auf einen Haufen eine allgemeine Weise ist, Vorzugswarteschlangen für Daten der ganzen Zahl durchzuführen, bestehen schnellere Durchführungen (das kann sogar für datatypes gelten, die begrenzte Reihe, wie Hin- und Herbewegungen haben):

• Wenn der Satz von Schlüsseln {1, 2..., C} ist, unterstützt ein Baum von van Emde Boas das Minimum, das Maximum, den Einsatz, löschen Sie, suchen Sie mit dem Extrakt minutig, Extrakt-max, Vorgänger und Nachfolger-Operationen rechtzeitig, aber hat Raumkosten nach kleinen Warteschlangen ungefähr O (2), wo M die Zahl von Bit im Vorzugswert ist.
• Der Fusionsbaumalgorithmus durch Fredman und Willard führt die minimale Operation in O (1) Zeit und Einsatz und mit dem Extrakt minutige Operationen rechtzeitig durch.

Für Anwendungen, die viele "Piepsen"-Operationen wegen jeder "mit dem Extrakt minutigen" Operation tun, kann die Zeitkompliziertheit für das Piepsen auf O (1) im ganzen Baum und Haufen-Durchführungen durch das Verstecken des höchsten Vorzugselements nach jeder Einfügung und Eliminierung reduziert werden. (Für die Einfügung trägt das an unveränderlichsten Kosten bei, da das kürzlich eingefügte Element nur im Vergleich zum vorher versteckten minimalen Element sein muss. Für das Auswischen fügt das höchstens zusätzliche "Piepsen"-Kosten hinzu, die fast immer preiswerter sind als die Auswischen-Kosten, so wird gesamte Zeitkompliziertheit durch diese Änderung nicht betroffen).

Gleichwertigkeit von Vorzugswarteschlangen und Sortieren-Algorithmen

Das Verwenden einer Vorzugswarteschlange zur Sorte

Die Semantik von Vorzugswarteschlangen deutet natürlich eine Sortieren-Methode an: Fügen Sie alle Elemente ein, die in eine Vorzugswarteschlange zu sortieren sind, und entfernen Sie sie folgend; sie werden in der sortierten Ordnung herauskommen. Das ist wirklich das durch mehrere Sortieren-Algorithmen verwendete Verfahren, einmal wird die Schicht der von der Vorzugswarteschlange zur Verfügung gestellten Abstraktion entfernt. Diese Sortieren-Methode ist zu den folgenden Sortieren-Algorithmen gleichwertig:

• Heapsort, wenn die Vorzugswarteschlange mit einem Haufen durchgeführt wird.
• Smoothsort, wenn die Vorzugswarteschlange mit einem Haufen von Leonardo durchgeführt wird.
• Auswahl-Sorte, wenn die Vorzugswarteschlange mit einer nicht eingeordneten Reihe durchgeführt wird.
• Einfügungssorte, wenn die Vorzugswarteschlange mit einer bestellten Reihe durchgeführt wird.
• Baumsorte, wenn die Vorzugswarteschlange mit einem selbstbalancierenden binären Suchbaum durchgeführt wird.

Das Verwenden eines Sortieren-Algorithmus, um eine Vorzugswarteschlange zu machen

Ein Sortieren-Algorithmus kann auch verwendet werden, um eine Vorzugswarteschlange durchzuführen. Spezifisch sagt Thorup:

Wir präsentieren die allgemeine deterministische geradlinige Raumverminderung von Vorzugswarteschlangen zum Sortieren der Andeutung, dass, wenn wir bis zu n Schlüsseln in S (n) Zeit pro Schlüssel dann sortieren können, es ein Vorzugswarteschlange-Unterstützen gibt, löschen und fügen in O (S (n)) Zeit ein und finden minutig in der unveränderlichen Zeit.

D. h. wenn es einen Sortieren-Algorithmus gibt, der in O (S) Zeit pro Schlüssel sortieren kann, wo S etwas Funktion von n und Wortgröße ist, dann kann man das gegebene Verfahren verwenden, um eine Vorzugswarteschlange zu schaffen, wo das Ziehen des Elements des höchsten Vorrangs O (1) Zeit ist, und das Einfügen neuer Elemente (und Löschen-Elemente) O (S) Zeit ist. Zum Beispiel, wenn man einen O (n lg (lg (n))) Sorte-Algorithmus hat, kann man eine Vorzugswarteschlange mit O (1) das Ziehen und O (lg (lg (n))) Einfügung leicht schaffen.

Bibliotheken

Wie man

häufig betrachtet, ist eine Vorzugswarteschlange eine "Behälterdatenstruktur".

Standard Template Library (STL) und der C ++ 1998-Standard, geben als eine der STL Behälteradapter-Klassenschablonen an. Es führt einen max-priority-queue durch. Verschieden von wirklichen STL Behältern erlaubt es Wiederholung seiner Elemente nicht (es klebt ausschließlich an seiner abstrakten Datentyp-Definition). STL hat auch Dienstprogramm-Funktionen, um einen anderen Behälter des zufälligen Zugangs als ein binärer Max-Haufen zu manipulieren.

Das heapq Modul der Pythonschlange führt einen binären Minute-Haufen oben auf einer Liste durch.

Javas Bibliothek enthält eine Klasse, die eine "Minute-Vorzugswarteschlange" durchführt.

Die Bibliothek von Go enthält ein Modul des Behälters/Haufens, das einen Minute-Haufen oben auf jeder vereinbaren Datenstruktur durchführt.

Die PHP Standardbibliothekserweiterung enthält die Klasse SplPriorityQueue.

Das Kernfundament-Fachwerk des Apfels enthält eine Struktur von CFBinaryHeap, die einen Minute-Haufen durchführt.

Anwendungen

Bandbreite-Management

Das Vorzugsschlangestehen kann verwendet werden, um beschränkte Mittel wie Bandbreite auf einer Übertragungslinie von einem Netzrouter zu führen. Im Falle des aus dem Amt scheidet Verkehrs, der wegen der ungenügenden Bandbreite Schlange steht, können alle anderen Warteschlangen gehalten werden, um den Verkehr von der höchsten Vorzugswarteschlange nach der Ankunft zu senden. Das stellt sicher, dass der prioritized Verkehr (wie Echtzeitverkehr, z.B ein RTP Strom einer Verbindung von VoIP) mit kleinster Verzögerung und kleinster Wahrscheinlichkeit nachgeschickt wird, wegen einer Warteschlange zurückgewiesen zu werden, die seine maximale Kapazität erreicht. Ganzer anderer Verkehr kann behandelt werden, wenn die höchste Vorzugswarteschlange leer ist. Eine andere verwendete Annäherung soll unverhältnismäßig mehr Verkehr von höheren Vorzugswarteschlangen senden.

Viele moderne Protokolle für Lokale Bereichsnetze schließen auch das Konzept von Vorzugswarteschlangen an der Teilschicht von Media Access Control (MAC) ein, um sicherzustellen, dass vordringliche Anwendungen (wie VoIP oder IPTV) niedrigere Latenz erfahren als andere Anwendungen, denen mit dem Besten Anstrengungsdienst gedient werden kann. Beispiele schließen IEEE 802.11e ein (eine Änderung von IEEE 802.11, der Qualität des Dienstes zur Verfügung stellt) und ITU-T G.hn (ein Standard für das Lokale Hochleistungsbereichsnetz mit der vorhandenen Hausverdrahtung (Starkstromleitungen, rufen Sie Linien und koaxiale Kabel an).

Gewöhnlich wird eine Beschränkung (policer) veranlasst, die Bandbreite zu beschränken, die der Verkehr von der höchsten Vorzugswarteschlange nehmen kann, um hohe Vorzugspakete davon abzuhalten, ganzen anderen Verkehr abzuwürgen. Diese Grenze wird gewöhnlich wegen hoher Kontrollbeispiele wie Cisco Callmanager nie erreicht, der programmiert werden kann, um Anrufe zu hemmen, die die programmierte Bandbreite-Grenze überschreiten würden.

Getrennte Ereignis-Simulation

Ein anderer Gebrauch einer Vorzugswarteschlange soll die Ereignisse in einer getrennten Ereignis-Simulation führen. Die Ereignisse werden zur Warteschlange mit ihrer als der Vorrang verwendeten Simulierungszeit hinzugefügt. Die Ausführung der Simulation geht durch das wiederholte Ziehen der Spitze der Warteschlange und die Durchführung des Ereignisses darauf weiter.

Siehe auch: (Computerwissenschaft), queueing Theorie planend

Der Algorithmus von Dijkstra

Wenn der Graph in der Form der Angrenzen-Liste oder Matrix versorgt wird, kann Vorzugswarteschlange verwendet werden, um Minimum effizient herauszuziehen, wenn sie den Algorithmus von Dijkstra durchführt.

A* und SMA* suchen Algorithmen

Der A* Suchalgorithmus findet den kürzesten Pfad zwischen zwei Scheitelpunkten oder Knoten eines belasteten Graphen, die viel versprechendsten Wege zuerst erprobend. Die Vorzugswarteschlange (auch bekannt als die Franse) wird verwendet, um unerforschte Wege nachzugehen; derjenige, für den ein niedrigerer zur Gesamtpfad-Länge gebunden hat, ist am kleinsten wird höchster Vorrang gegeben. Wenn Speicherbeschränkungen A* unpraktisch machen, kann der SMA* Algorithmus statt dessen mit einer doppelt beendeten Vorzugswarteschlange verwendet werden, um Eliminierung von Sachen des niedrigen Vorrangs zu erlauben.

DURCHSTREIFEN SIE Triangulationsalgorithmus

Der Algorithmus von Real-time Optimally Adapting Meshes (ROAM) schätzt eine sich dynamisch ändernde Triangulation eines Terrains. Es arbeitet durch das Aufspalten von Dreiecken, wo mehr Detail erforderlich ist und das Mischen von ihnen, wo weniger Detail erforderlich ist. Der Algorithmus teilt jedes Dreieck im Terrain ein Vorrang zu, der gewöhnlich mit der Fehlerabnahme verbunden ist, wenn dieses Dreieck gespalten würde. Der Algorithmus verwendet zwei Vorzugswarteschlangen, ein für Dreiecke, die gespalten werden können und ein anderer für Dreiecke, die verschmolzen werden können. In jedem Schritt wird das Dreieck von der Spalt-Warteschlange mit dem höchsten Vorrang gespalten, oder das Dreieck von der Verflechtungswarteschlange mit dem niedrigsten Vorrang wird mit seinen Nachbarn verschmolzen.

Siehe auch

• Gruppe-Warteschlange
• Verschluss
• Befehl-Muster
• Befehl-Warteschlange
• Funktionsgegenstand
• Job-Planer
• Muster-Ansicht-Kontrolleur

Weiterführende Literatur

• Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest und Clifford Stein. Einführung in Algorithmen, die Zweite Ausgabe. MIT Presse und McGraw-Hügel, 2001. Internationale Standardbuchnummer 0-262-03293-7. Abschnitt 6.5: Vorzugswarteschlangen, pp.138-142.

Links

• C ++ Verweisung für
• Beschreibungen von Lee Killough
• PQlib - Offene Quellvorzugswarteschlange-Bibliothek für C
• libpqueue ist eine allgemeine Vorzugswarteschlange (Haufen) Durchführung (in C) verwendet durch das HTTP Apachen-Server-Projekt.
• Überblick über bekannte Vorzugswarteschlange-Strukturen durch Stefan Xenos
• UC Berkeley - Informatik 61B - Vortrag 24: Vorzugswarteschlangen (Video) - Einführung in Vorzugswarteschlangen, die binären Haufen verwenden
• Doppelt beendete Vorzugswarteschlangen durch Sartaj Sahni