Implementazione della chiave di riduzione con heap STL in tempo O (logn)

Question

Al momento STL Heap non supporta la chiave di riduzione, tuttavia è possibile modificare direttamente il valore sul vettore e chiamare di nuovo make_heap che è O (n). Tuttavia non è efficiente come una chiave di riduzione dell'heap binario che richiederebbe il tempo O (logn).

Esiste un modo per ottenere il tempo O (logn) utilizzando le funzioni heap STL?

Answer 1

È possibile utilizzare pop_heap seguito dal decremento del valore seguito da push_heap:

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: E 'questo quello che vuoi dire, o si vuole essere in grado di diminuire la chiave di ogni elemento nella mucchio?

Answer 2

Sono abbastanza sicuro che non c'è modo conforme agli standard di farlo - Wikipedia says so too:

non c'è il supporto standard per la riduzione/aumento-chiave operativa

Anche se lo fa andare per puntare alla libreria gheap, che potrebbe valere la pena dare un'occhiata.

Il problema qui è che lo standard non richiede quale forma assume la struttura dell'heap, né come esattamente vengono eseguite le operazioni. (In generale, questa è una buona cosa.)

Se l'implementazione utilizza un heap binario standard, penso che si possa semplicemente diminuire l'elemento a heap[i] e quindi chiamare push_heap(heap.begin(), heap.begin() + i + 1), che eseguirà l'operazione up-heap necessaria. L'elemento che termina alla posizione i non deve essere più grande del valore lì originariamente, e quindi la proprietà heap dell'intero heap viene preservata. Ma questo non è supportato dallo standard anche se a volte funziona a volte in alcune implementazioni.