Perché un max-heap non ha un'operazione di tasto di diminuzione e un heap minimo un'operazione di aumento della chiave?

Question

Perché un max-heap non ha un'operazione di tasto di diminuzione e un heap minimo un'operazione di aumento della chiave?

#1 da (1 voti)

0

L'operazione di aumento-chiave o diminuzione-chiave è per l'aggiornamento di una chiave all'interno di un massimo o min-heap, rispettivamente.

Perché un max-heap non ha un'operazione di tasto decremento e un heap minimo un'operazione di tasto aumento?

Grazie.

data-structures heap

posta Tim 15.10.2016 - 16:55

fonte

1 risposta

Leggi altre domande sui tag data-structures heap

Perché alcuni alberi di ricerca posizionano gli elementi degli insiemi che rappresentano solo nelle foglie, mentre alcuni in tutti i nodi? come raggiungere tutti i nodi in una struttura ad albero in cui la fine dell'albero è sconosciuta

score 1 · Answer 1

Questo è stato discusso prima qui . Per riassumere, queste operazioni possono essere facilmente implementate in O(log(n)) , ma di solito non vengono fornite perché hanno scarso interesse da una pura prospettiva algoritmica.

Al contrario, il tasto di riduzione su un heap minimo ha un'implementazione O(1) esistente in un heap di Fibonacci e ha un'applicazione, ad esempio in un percorso di ricerca di Dijkstra.