Erhöhen-Taste und Verringern-Taste in einem binären Min-Heap

16

In vielen Diskussionen über Binär-Heap wird normalerweise nur der Abnahme-Schlüssel als unterstützte Operation für einen Min-Heap aufgelistet. Zum Beispiel CLR-Kapitel 6.1 und diese Wikipedia-Seite . Warum wird normalerweise kein Erhöhungsschlüssel für Min-Heap aufgeführt? Ich stelle mir vor, dass es möglich ist, dies in O (Höhe) zu tun, indem das erhöhte Element (x) mit dem Minimum seiner Kinder iterativ vertauscht wird, bis keines seiner Kinder größer als x ist.

z.B

IncreaseKey(int pos, int newValue)
{
   heap[pos] = newValue;
   while(left(pos) < heap.Length)
   {
      int smallest = left(pos);
      if(heap[right(pos)] < heap[left(pos)])
         smallest = right(pos);
      if(heap[pos] < heap[smallest])
      { 
         swap(smallest, pos);
         pos= smallest;
      }
      else return;
   }   
}

Ist das obige richtig? Wenn nein, warum? Wenn ja, warum ist der Erhöhungsschlüssel für den Min-Heap nicht aufgeführt?

GatotPujo
quelle
1
Nachdem ich alle Antworten gelesen habe, würde ich sagen, dass es eine seltsame Auslassung ist, die wahrscheinlich durch die historisch erste Verwendung von min-heap im Dijkstra-Algorithmus verursacht wurde.
Maaartinus
3
Sie können natürlich immer einen Erhöhen-Schlüssel mit einem Löschen gefolgt von einem Einfügen implementieren, und das Löschen selbst kann als Verringern-Schlüssel (bis -∞) gefolgt von einem Löschen-Min. Implementiert werden.
Davmac
@ Maaartinus Kommentar ist die richtige Antwort.
Max.

Antworten:

6

Der von Ihnen vorgeschlagene Algorithmus ist einfach gehäuft. Und in der Tat - wenn Sie den Wert eines Elements in einem Min-Heap erhöhen und dann dessen Unterbaum heapifizieren, erhalten Sie einen legalen Min-Heap.

Shaull
quelle
Warum dann nicht CLR- oder Wikipedia-Liste? Erhöhen Sie den Schlüssel, um eine unterstützte Operation zu sein? Es hat mich irgendwie irregeführt zu denken, dass es nicht in einem Min-Heap möglich ist
GatotPujo
Ich stimme zu, dass es irreführend ist, aber ich sehe keinen Fehler im Algorithmus.
Shaull
5

Der Grund dafür, dass Ihre Operation nicht aufgeführt ist, ist, dass man nicht einfach an allen Operationen interessiert ist, die mit einer bestimmten Datenstruktur einfach implementiert werden können, sondern auf die andere Weise. Welche Methode ist bei einer Reihe von Operationen (in Bezug auf Raum und Zeit) am effizientesten, um diese Operationen zu implementieren? (Aber dazu später mehr)

Binäre Heaps implementieren die Prioritätswarteschlange für abstrakte Datenstrukturen, in der nach den Operationen is_empty, add_element (ein Schlüssel mit seiner Priorität), find_min und delete_min gefragt wird. Weitergehende Warteschlangen ermöglichen es auch, die Priorität des Schlüssels zu verringern (in einem min_heap) oder sogar zu erhöhen. Tatsächlich haben Sie eine Implementierung angegeben.

Zwei Bemerkungen. Ihre Operation wird in der Funktion heapify verwendet, mit der ein Heap effizient aus einem Array erstellt wird. In Heapify wird Ihre Operation wiederholt (beginnend mit dem letzten Schlüssel).

Am wichtigsten ist jedoch, dass Ihr Code die Position des Knotens verwendet. Für die Prioritätswarteschlange der reinen Datenstruktur, die betrügt. Diese Datenstruktur fordert dazu auf, eine bestimmte Operation bei gegebenem Schlüssel auszuführen. Um die Priorität eines Elements zu verringern oder zu erhöhen, müssen Sie es zuerst suchen. Ich denke, das ist der Hauptgrund, warum es nicht aufgeführt ist.

Hendrik Jan
quelle
1
Danke für die Erklärung. In der CLR-Verkleinerung hat die Taste jedoch auch die Position als Knoten als Parameter.
GatotPujo
Du hast recht. Ich konnte keinen Grund für diese Asymmetrie in der Definition der Prioritätswarteschlangen in Abschn. 6.5 von CLRS finden. Hinweis: In Heapsort, der Anwendung dieses Kapitels, wird keine Erhöhungstaste verwendet. Es scheint, dass die Asymmetrie zwischen Zunahme und Abnahme nur mit der Art und Weise zusammenhängt, wie die Datenstruktur in zB dem Dijkstra-Algorithmus verwendet wird. Dort (unter Verwendung eines Min-Heap) könnten einige ausgewählte Knoten dringlicher werden und im Heap "nach oben" verschoben werden.
Hendrik Jan
0

Ich denke, dass das erste, was zu berücksichtigen ist, was eine unterstützte Operation ist?

Entspricht "Einfügen eines Wertes mit einem bestimmten festen Schlüssel" (z. B. für Schlüssel aus dem Integer-Bereich, Einfügen mit Schlüssel = 3) einer unterstützten Operation für den Min-Heap?

Nein, da diese Operation mit allgemeineren unterstützten Operationen einfach implementiert werden kann. Ebenso können mit der bestehenden insertOperation 2 Elemente gleichzeitig eingefügt werden.

Andererseits kann die insertOperation nur definiert werden, indem Implementierungsdetails offengelegt werden. Mit heapifyAusnahme der auf der Wikipedia-Seite aufgelisteten Vorgänge , die wahrscheinlich durch eine Sequenz von implementiert werden könnten, ist dies im Großen und Ganzen dasselbe insert.

Mit anderen Worten, es gibt elementare Operationen auf dem Typ, die eng an die Implementierungsdetails gebunden sind, damit sie gut funktionieren, und es gibt andere Operationen, die diese Regel nicht einhalten und daher als Kombinationen implementiert werden können der kanonischen.

Glauben Sie angesichts dieser Definition, dass die Erhöhungstaste ausschließlich mit anderen unterstützten Operationen implementiert werden kann, ohne dass Leistungseinbußen auftreten? In diesem Fall handelt es sich nicht um eine unterstützte Operation gemäß der obigen Definition. Andernfalls haben Sie möglicherweise recht.

Die Definition einer unterstützten Operation, die ich zur Verfügung stelle, ist meines Wissens nach meine. Es ist nicht formal und daher Gegenstand von Diskussionen (obwohl es mir ziemlich klar erscheint). Ich würde mich jedoch freuen, wenn jemand eine Quelle bereitstellen könnte, die klar und eindeutig definiert, was eine unterstützte Operation für Datentypen ist, oder zumindest besser definiert als meine (ist diese Definition in der CLR angegeben? Ich habe keine Kopie ).

Mein zweiter Punkt wird sein, wie wir eine Prioritätswarteschlange definieren (was die Existenzberechtigung von Binärhaufen ist). Ist die increase_keyOperation für diesen Datentyp erforderlich, dh für die ordnungsgemäße Verwendung?

Wie Sie sehen, dreht sich in meinem Blickwinkel alles um Definitionen. Ich kann Ihre Fragen nicht wirklich beantworten, nur einige Hinweise, daher sind Verbesserungen willkommen.

didierc
quelle
1
Ein Beispielanwendungsfall kann sein, wenn ich eine Prioritätswarteschlange von Objekten basierend auf zuletzt verwendeten Objekten verwalten möchte (z. B. damit ich zuletzt verwendete Objekte leicht löschen kann). Ich kann einen Min-Heap mit dem letzten Zugriffsdatum als Schlüssel verwenden. Wenn auf ein Objekt zugegriffen wird, muss dessen Schlüssel erhöht werden.
GatotPujo
Sehr guter Punkt. Mein Standpunkt ist anscheinend etwas eingeschränkt. Wirklich, @HendrikJan Antwort bringt eine sehr gute Erklärung.
Didierc