Ich verwende eine Prioritätswarteschlange als Scheduler mit einer zusätzlichen Anforderung. Ich muss geplante Artikel stornieren können. Dies entspricht dem Entfernen eines Elements aus der Mitte der Prioritätswarteschlange.
Ich kann std::priority_queue nicht verwenden, da der Zugriff auf ein anderes Element als top geschützt ist.
Ich versuche, die Heap-Funktionen von algorithm zu verwenden. Aber ich vermisse immer noch das Stück, das ich brauche. Wenn ich ein Element I aus der Mitte des Heaps entferne, möchte ich, dass es sich effizient neu erstellt. C ++ bietet diese Heap-Funktionen:
std::make_heap O (3n)
std::push_heap O (lg (n))
std::pop_heap O (2 lg (n))
Ich möchte eine neue Funktion wie std::repair_heap mit einem großen O & lt; 3n . Ich würde es mit der Position des Lochs angeben, wo sich das abgebrochene Element befand, und es würde den Heap richtig anpassen.
Es scheint ein großes Versehen zu sein, keine std::repair_heap Funktion zur Verfügung zu stellen. Fehle ich etwas Offensichtliches?
Gibt es eine Bibliothek, die ein stl-konformes std::repair_heap ?
Gibt es eine bessere Datenstruktur für die Modellierung eines Schedulers?
HINWEIS :
Ich verwende kein std::map aus ein paar Gründen.
Leider fehlt dem Standard diese (ziemlich wichtige) Funktion. Mit g ++ können Sie dazu die Nicht-Standard-Funktion std::__adjust_heap verwenden, aber es gibt keine einfache übertragbare Methode - und __adjust_heap ist in verschiedenen Versionen von g ++ etwas anders, so dass Sie es nicht einmal tun können portabel über g ++ - Versionen.
Wie funktioniert Ihr repair_heap() ? Hier ist meine Vermutung:
Wenn Ihr Heap durch einen Iterator-Bereich definiert ist, sagen Sie (heapBegin, heapEnd). Das Element, das Sie entfernen möchten, ist das Stammverzeichnis eines Teilbaums des Heapspeichers, der von einem Teilbereich (subHeapBegin, subHeapEnd) definiert wird. Verwenden Sie std::pop_heap(subHeapBegin, subHeapEnd) und dann, wenn subHeapEnd != heapEnd , die Werte bei *(subHeapEnd-1) und *(heapEnd-1) , was Ihr gelöschtes Element am Ende des Heap-Containers ablegen sollte. Jetzt müssen Sie das Element bei * (subHeapEnd-1) in Ihrer Unterhyphe hochsaugen. Wenn ich etwas nicht verpasst habe, was möglich ist, dann muss nur noch das Endelement vom Heap-Container abgeschnitten werden.
Bevor wir versuchen, das richtig zu programmieren (ich habe einige Details übersprungen, wie subHeapBegin und subHeapEnd berechnet), würde ich einige Tests durchführen, um festzustellen, ob make_heap() Sie wirklich verlangsamt. Big-O ist nützlich, aber es ist nicht dasselbe wie die tatsächliche Ausführungszeit.
Ich nehme an, Sie wissen, welches Element im Heap-Container (Index n) Sie löschen möchten.
v[n] = BIG; fest, der Wert BIG ist wirklich größer als alle anderen Werte im Heap. std::push_heap( v.begin(), v.begin()+n+1 );
std::pop_heap( v.begin(), v.end() );
v.pop_back();
Operation ist O (ln (n))
RE: Nachprüfungsantrag
Zuerst ein Qualifier:
Diese Methode geht von dem Algorithmus aus, der von std push_heap verwendet wird
Insbesondere nimmt es an, dass std push_heap (v.begin (), v.begin () + n + 1)
Ändere nur den Bereich [0, n]
für diejenigen Elemente, die aufsteigend von n sind, d. h. Indizes in dem folgenden Satz:
Hier ist eine typische Spezifikation für std push_heap:
Ссылка "Bei einem Heap-Bereich [first, last-1] erweitert diese Funktion den Bereich, der als Heap betrachtet wird, auf [first, last], indem sie den Wert in last-1 an die entsprechende Stelle in ihm setzt."
Gewährleistet es, den "normalen Heap-Algorithmus" zu verwenden, den Sie in Lehrbüchern gelesen haben? Du sagst es mir.
Wie auch immer, hier ist der Code, den Sie empirisch ausführen und sehen können, dass es funktioniert. Ich benutze VC 2005.
%Vor%Aber ich habe ein anderes Problem, nämlich wie man den Index "n" kennt, der gelöscht werden muss. Ich kann nicht sehen, wie man das verfolgt (kenne den Platz im Heap), während du std push_heap und std pop_heap verwendest. Ich denke, Sie müssen Ihren eigenen Heap-Code schreiben und den Index im Heap jedes Mal in ein Objekt schreiben, wenn das Objekt im Heap verschoben wird. Seufz.
Es scheint mir, dass das Entfernen aus der Mitte eines Heaps bedeuten kann, dass der gesamte Heap neu aufgebaut werden muss: Der Grund, dass es keinen repair_heap gibt, ist, dass er dieselbe (große-oh) Arbeit wie make_heap ausführen müsste.
Können Sie etwas wie put std::pair<bool, Item> in den Heap tun und Elemente einfach ungültig machen, statt sie zu entfernen? Dann, wenn sie endlich an die Spitze kommen, ignorieren Sie einfach den Gegenstand und gehen Sie weiter.
Hier ist ein bisschen Delphi-Code, den ich verwendet habe, um Elemente von einem Heap zu entfernen. Ich kenne dieses C ++ nicht, von dem du sprichst und keine Reparaturfunktion hast, aber hey ..
Zuerst der Pop, damit Sie eine Vorstellung davon bekommen, wie das Ding funktioniert:
%Vor%jetzt zum Kontrast, die Löschung:
%Vor%ist natürlich ein No-No, an das man überhaupt denken kann tun, was wir hier tun, aber hey, kostet ändern Sie sich manchmal und Jobs werden abgebrochen.
genießen. Ich hoffe, das hilft.
Tags und Links c++ stl data-structures priority-queue