Nodi marcati negli heap di Fibonacci

Question

Nodi marcati negli heap di Fibonacci

#1 da (4 voti)

2

Non capisco perché heap di Fibonacci abbiano nodi marcati (picture ). Un nodo è contrassegnato quando il figlio viene cancellato. Citando da Wikipedia: "[Mantenendo basso il grado di ciascun nodo] si ottiene la regola che possiamo tagliare al massimo un figlio di ciascun nodo non root. Quando un secondo figlio viene tagliato, il nodo stesso deve essere tagliato dal suo genitore e diventa la radice di un nuovo albero. "

Perché abbiamo bisogno di farlo? Perché non lasciare il nodo dove si trova dopo che il secondo figlio è stato tagliato? La struttura dell'heap non viene violata. Non vedo il punto di questa ottimizzazione.

data-structures heap

posta Alexei Andreev 18.02.2013 - 07:11

fonte

1 risposta

Leggi altre domande sui tag data-structures heap

Come si inseriscono gli oggetti nello stile moderno C ++ (stl, policy-classes, funzionale)? Implementazione della funzionalità di annullamento / ripristino basata sul contesto

score 4 · Accepted Answer

Il motivo non è che violerebbe l'invariante dell'heap, ma porterebbe a uno stato in cui l'heap sarebbe inefficiente.

L'heap è efficiente perché dopo la compattazione ci sono solo alberi log ( N ). Per garantire che sia necessario sapere che un albero con grado di radice k contiene almeno O (2 ^k) i nodi. Ma se riesci a tagliare i nodi liberamente, potresti tagliare tutti i bambini di secondo livello e l'albero rimarrà di grado k , ma potrebbe arrivare a k +1 nodi.

Questo è evitato facendo a pezzi l'albero e comprimendo di nuovo le sue parti nel prossimo passo di compattazione.