Momentan unterstützt STL Heap den Verkleinerungsschlüssel nicht, jedoch kann man einfach den Wert des Vektors direkt ändern und make_heap erneut aufrufen, was O (n) Zeit ist. Dies ist jedoch nicht so effizient wie ein binärer Heap-Verkleinerungsschlüssel, der eine O (Logn) -Zeit benötigt.
Gibt es eine Möglichkeit, O (logn) -Zeit mit STL-Heap-Funktionen zu erreichen?
Ich bin mir ziemlich sicher, dass es keine standardkonforme Methode dafür gibt - Wikipedia sagt das auch :
Es gibt keine Standardunterstützung für die Funktion zum Verkleinern / Vergrößern von Tasten
Obwohl es weiterhin auf die gheap -Bibliothek verweist, die einen Blick wert sein könnte.
Das Problem hierbei ist, dass der Standard nicht vorschreibt, wie die Heap-Struktur aussieht und wie genau die Operationen ausgeführt werden. (Im Allgemeinen ist das eine gute Sache.)
Wenn die Implementierung einen Standard-Binary-Heap verwendet, dann können Sie das Element einfach auf heap[i] reduzieren und dann push_heap(heap.begin(), heap.begin() + i + 1) aufrufen, wodurch die erforderliche Up-Heap-Operation ausgeführt wird. Das Element, das an der Position i endet, darf nicht größer als der ursprüngliche Wert sein. Daher wird die Heap-Eigenschaft des gesamten Heapspeichers beibehalten. Aber dies wird vom Standard nicht unterstützt, auch wenn es manchmal in einigen Implementierungen funktioniert.