Ich habe die Anweisungen in diese Frage (die Antwort von Jason) befolgt schreibe meine PriorityQueue<T> mit einem SortedList . Ich verstehe, dass das Feld count innerhalb dieser Klasse verwendet wird, um eindeutige Prioritäten sicherzustellen und die Reihenfolge der Enqueues unter derselben Priorität zu erhalten.
Wenn count jedoch seinen Maximalwert erreicht und 1 zu ihm addiert, beginnt letzterer erneut mit 0, so dass die Priorität der nachfolgenden Elemente höher ist als die Priorität der vorherigen Elemente. Unter Verwendung dieses Ansatzes könnte ich eine Möglichkeit benötigen, um den Zähler count ... "sicher" zurückzusetzen. Nehmen wir an, dass der folgende Warteschlangenzustand vorliegt (im Format priority | count | item ):
0 | 123 | Ein
0 | 345 | B
1 | 234 | C
2 | 200 | D
Nehmen wir nun an, dass das Zählerlimit erreicht ist, also muss ich es auf 0 zurücksetzen: als Konsequenz wird das nächste eingefügte Element den Zähler 0 haben: Wenn ich beispielsweise ein Element mit der Priorität 1 einfüge, wird es sein falsch eingefügt vor 1 | 234 | D
0 | 123 | Ein
0 | 345 | B
1 | 000 | neues Element
1 | 234 | C
2 | 200 | D
Das Problem der Priorität kann durch die Implementierung eines Heaps gelöst werden: Ich habe eine Klasse Heap erstellt, dann habe ich Heap<KeyValuePair<TPriority, TElement> und eine benutzerdefinierte PriorityComparer verwendet, um Elemente nach TPriority zu sortieren.
Wenn TPriority als int und TElement als string angegeben wird, lautet PriorityComparer wie folgt:
UPDATE
Auf diese Weise (mit PriorityComparer ) ist es mir gelungen, eine Prioritätswarteschlange zu implementieren.
Jetzt möchte ich Unterstützung hinzufügen, um sein Verhalten zur Laufzeit zu ändern, dh von FIFO zu Prioritätssortierung und umgekehrt. Da meine Implementierung der Prioritätswarteschlange ein IComparer -Feld enthält, reicht es aus, eine Comparer -Eigenschaft hinzuzufügen, um dieses Feld zu bearbeiten, wie folgt:
In der Zwischenzeit dachte ich, ich würde einen anderen Ansatz wählen: Anstatt einen binären Heap zu verwenden, um Prioritäten zu verwalten, könnte ich verschiedene Warteschlangen (jede Warteschlange bezieht sich auf eine bestimmte Priorität) wie folgt einpacken.
%Vor%Du könntest "schummeln" und BigInteger verwenden, damit du niemals "rennst" aus Zahlen ". Dies führt natürlich zu einer allmählichen Verschlechterung der Leistung im Laufe der Zeit, aber wahrscheinlich nicht signifikant genug, um wichtig zu sein.
Kombinieren Sie das mit einer Heap -basierten Prioritätswarteschlange, und Sie sind eingestellt!
Versuchen Sie nicht, "von FIFO zu Prioritätssortierung und umgekehrt" zu wechseln - fügen Sie einfach Elemente in beide Datenstrukturen ein, die für die Aufgabe geeignet sind ( Warteschlange und Prioritätswarteschlange).
Ich würde sowohl Queue als auch Priority Queue verwenden
Aber wenn du musst ...
Verwenden Sie anstatt eines Schlüssels zwei Schlüssel für ein Element.
Der erste Schlüssel priority wird die Priorität sein.
Der zweite Schlüssel time wird ein Zähler sein, der wie ein Zeitstempel sein wird.
Verwenden Sie für das normale Verhalten die priority -Schlüssel.
Wenn der Heap voll ist, HEAPIFY it durch den Schlüssel time .
Dann entfernen Sie n benötigte Elemente.
Jetzt HEAPIFY erneut mit der priority Taste, um zum normalen Verhalten zurückzukehren.
BEARBEITEN: Sie haben das, was Sie fragen, mit Ihren Änderungen geändert. Sie gingen von einer Frage zu einem neuen Ansatz und einer neuen Frage. Sollte wahrscheinlich eine neue Frage für Ihren neuen Ansatz eröffnen, da dieser jetzt verwirrend ist, was Antwort / Antwort auf welche Frage / Kommentar ist. Ich glaube, Ihre ursprüngliche Frage zum Sortieren gleicher Prioritäten wurde beantwortet.
Sie könnten eine Long verwenden, um mehr Werte zu berücksichtigen. Sie werden schließlich immer ein Ende erreichen, also müssten Sie ein neues Muster für eindeutige Werte verwenden oder die Elemente nacherzählen, wenn das Maximum erreicht ist (durchlaufen Sie jedes und setzen Sie den eindeutigen Zählwert zurück).
Vielleicht stattdessen eine GUID für jedes Element verwenden?
Guid.NewGuid()
BEARBEITEN:
Nach der Bearbeitung hinzufügen: Wenn die neue 1 nach der vorhandenen eingefügt werden soll, geben Sie in der Überschreibungsüberprüfung ein Ergebnis größer als (1) zurück, wenn die Werte gleich sind. So wird Folgendes passieren:
%Vor%EDIT 2:
Wenn der zweite Parameter nur ein eindeutiger Wert sein soll, könnten Sie immer eine Zeichenkette verwenden und den Wert stattdessen als numerische Zeichenketten festlegen. Auf diese Weise wirst du niemals eine Kappe erreichen, sondern musst die Saite entsprechend analysieren. Sie können führende Alpha-Werte verwenden, die eine neue Menge darstellen.
Ich habe diesen Code nicht getestet, nur eine Idee, was Sie tun könnten.
%Vor%EDIT 3: Werte zurücksetzen
%Vor%Bearbeiten Sie 4: Für Ihre zweite Frage:
Sie können einen FIFO-Stack wie gewohnt verwenden, haben aber auch eine Prioritätsliste, in der nur die eindeutige ID der Elemente gespeichert ist. Sie müssten das Element jedoch jedes Mal aus der Liste entfernen, wenn Sie es aus dem FIFO-Stapel entfernen.
%Vor%Tags und Links algorithm .net c# data-structures