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

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?

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.

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.

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.