Implementieren von Verringerungsschlüssel mit STL-Heap in O (logn) -Zeit

Question

Momentan unterstützt STL Heap keine Verkleinerungsschlüssel, jedoch kann man einfach den Wert auf dem Vektor 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?

Answer 1

können Sie pop_heap durch Vermindern des von push_heap gefolgt Wert folgt verwendet werden:

int main() { 
    //Create the heap 
    std::vector<int> heap{1,2,3,4,5,6,7}; 
    std::make_heap(heap.begin(), heap.end()); 

    //Decrease key 
    std::pop_heap(heap.begin(), heap.end()); 
    --*(std::prev(heap.end())); 
    std::push_heap(heap.begin(), heap.end()); 
} 

EDIT: Ist das, was Sie meinen, oder haben Sie den Schlüssel von jede Element zu verringern, in der Lage sein wollen Haufen?

Answer 2

bin ich ziemlich sicher, dass es keine Standard-konforme Art und Weise, es zu tun - Wikipedia says so too:

gibt es keinen Standard-Support für die Abnahme/Zunahme-Tasten-Bedienung

Obwohl es geht nicht um auf die gheap Bibliothek zu zeigen, die einen Blick wert sein könnte.

Das Problem hier ist, dass der Standard nicht vorgibt, welche Form die Heap-Struktur nimmt, noch, wie genau die Operationen ausgeführt werden. (In der Regel ist dies eine gute Sache.)

Wenn die Implementierung eines Standard-Binär-Heap verwendet dann denke ich, Sie einfach das Element an heap[i] verringern und rufen dann push_heap(heap.begin(), heap.begin() + i + 1), die die notwendige up Haufen Operation tun wird. Das Element, das an der Position i endet, darf nicht größer als der ursprüngliche Wert sein, sodass die Heap-Eigenschaft des gesamten Heap beibehalten wird. Aber dies wird vom Standard nicht unterstützt, auch wenn es manchmal in einigen Implementierungen funktioniert.