Come modificare l'elemento max in un heap nella libreria standard C++?

Se ho un heap massimo, e se ho bisogno di cambiare l'elemento max, si tratta di un singolo algoritmo bubble-down. C'è un modo per farlo attraverso la libreria standard C++, senza codificare manualmente l'algoritmo?Come modificare l'elemento max in un heap nella libreria standard C++?

Capisco che dovrebbe essere equivalente a pop_heap + push_heap, ma si tratta di 2 operazioni di svuotamento anziché di una sola.

Quindi - questo algoritmo di bubble-down è esposto tramite l'API della libreria?

fonte

2015-04-15 rincewind

Il più vicino si ottiene è std::make_heap, che è probabilmente più lento del semplice pop/push.

Tuttavia, boost heap (s?) Dispone di "The Fixup Interface" che consente modifiche come desiderato. http://www.boost.org/doc/libs/1_51_0/doc/html/heap/concepts.html#heap.concepts.mutability

fonte

2015-04-15 23:43:48

Penso che 'std :: make_heap' sarebbe un po 'più lento di pop e spingere per un grande heap. Per un piccolo heap, potrebbe essere più veloce. – rici

@rici: Non so come sia implementato 'make_heap', ma è _possible_ che potrebbe essere super veloce per cose che sono già un heap ad eccezione di un elemento. È possibile che sia persino ottimale per quella situazione. Dipende però dall'implementazione. E sto solo speculando, potrebbe essere che l'implementazione di make_heap sia più o meno richiesta per essere la stessa runtime indipendentemente dal layout iniziale. –

Comunque sia implementato, ha bisogno di controllare ogni elemento per sapere che quello che gli dai è già un heap ad eccezione di un elemento. Quindi questo è O (N). Pop e push sono O (log N) con un moltiplicatore costante leggermente più grande (probabilmente non più di due o tre, però), quindi per un heap di grandi dimensioni 'make_heap' non verrà ridimensionato. – rici

Se siete disposti a chiamare std::pop_heap() sul proprio contenitore v, allora si può solo prima v.push_back() sul contenitore dell'elemento "modificato" prima popping mucchio. Quindi, ridurre v.

// Precondition is that v is already a heap. 
void change_max_element (std::vector<int> &v, int modified_value) { 
    v.push_back(modified_value); 
    std::pop_heap(v.begin(), v.end()); 
    v.pop_back(); 
}

Questa "opere", perché std::pop_heap() è definito scambiare il primo e l'ultimo elemento e bolla verso il basso. Tuttavia, viene anche richiesto che la sequenza di input sia un heap valido. Se siamo in grado di definire un'operazione di confronto specializzata che consentirebbe all'elemento back appena richiamato di riportarsi appartenere all'ultima posizione se fosse già nell'ultima posizione, potrebbe tecnicamente soddisfare il requisito.

fonte

2015-04-16 00:18:48 jxh

C'è comunque un avvertimento (ma non penso sia un problema). Il documento di std :: pop_heap() richiede [primo, ultimo] essere su un heap, ma quando si preme un nuovo valore come ultimo, non si garantisce che [primo, ultimo] sia un heap. Non penso che questo sia importante perché l'ultimo elemento è comunque spostato in primo luogo e viene eseguito l'heapify. – szli

@szli: questo è un buon punto. Un'implementazione futura potrebbe sfruttare tale requisito e produrre comunque gli effetti specificati. Tuttavia, sta dicendo che gli effetti sono stati descritti in modo specifico. – jxh

Ho dato un'occhiata all'implementazione GNU/Clang/SGI di STL, l'unica ipotesi è [first, last-1) è un heap. Il primo passo è quello di scambiare il primo e l'ultimo-1, quindi ingrandire [primo, ultimo-1). È sicuro, almeno per ora. – szli

Come modificare l'elemento max in un heap nella libreria standard C++?

risposta

Problemi correlati