Ho usato una struttura di dati che lo sviluppatore originale ha chiamato a heap, viene utilizzato per implementare una coda prioritaria.
Sebbene sia scritto molto sugli alberi binari, i cumuli (min / max) sembrano meno definiti (i dettagli variano tra le implementazioni).
Alcune caratteristiche che ho notato non si applicano necessariamente alle strutture ad albero binario.
- Lo stesso elemento può essere in coda più volte senza causare complicazioni nell'esecuzione o nell'implementazione.
- Ricerca (mentre possibile e più veloce di una ricerca esaustiva), non è così efficiente (poiché gli elementi figlio di ciascun nodo non devono essere bilanciati).
- Poiché la ricerca non è efficiente e esiste la possibilità di duplicati, la rimozione potrebbe richiedere la memorizzazione di un riferimento a
node, invece di usare akeyper cercare il nodo (che è pratica comune per gli alberi binari). - Cambiare le priorità nell'heap è banale, rispetto a un albero binario dove è più comune cancellare + inserire.
(con un caso migliore e un caso peggiore rispetto agli alberi binari)
Esiste una terminologia più dettagliata per le strutture dati che corrispondono a queste caratteristiche?
O è semplicemente un min/max heap che sembra essere usato come a priority-queue?
Nota, ecco un link a min-heap che ha le caratteristiche sopra descritte.
risposte:
2 per risposta № 1UN heap binario è un'implementazione concreta di coda di priorità struttura dati astratta. È popolare perché è facile da implementare, efficiente in termini di memoria e ragionevolmente veloce: O (log n) inserimento e O (log n) rimozione dell'elemento root (il più piccolo in un heap minimo, il più grande in un heap massimo) . La maggior parte delle implementazioni fornisce anche un metodo di anteprima che consente di visualizzare l'elemento radice senza rimuoverlo.
Un heap binario non fa nient'altroparticolarmente bene. Contrariamente alla tua osservazione, la ricerca di un particolare elemento in un heap binario richiede una scansione sequenziale. Sebbene i nodi siano ordinati (non ordinati), l'ordine non si presta bene alla ricerca.
L'implementazione tipica di un heap binario è in un array. Dovuto al proprietà forma (la struttura può essere vista come un perfetto (ocompleto) albero binario), il che significa che la relazione tra genitore e figlio è rappresentata implicitamente. Gli articoli vengono archiviati nella matrice in ordine di ampiezza.
Come ha indicato l'utente templatetypedef nel suorisposta, un heap binario è un tipo specifico di albero binario e non deve essere confuso con un albero di ricerca binario, che è specificamente progettato per l'inserimento e l'eliminazione rapidi di elementi e l'individuazione di elementi per chiave.
Sebbene cambiare la priorità di un elemento nell'heap o rimuovere un elemento arbitrario dall'heap sia molto semplice, il problema, come hai sottolineato, è posizionamento l'oggetto su cui operare. In un tipico heap binario, la ricerca dell'elemento da modificare richiede una ricerca sequenziale. Se hai bisogno della possibilità di spostare elementi nell'heap, in genere sposerai il binario con un dizionario o una mappa hash "indicizzata dalla chiave dell'elemento". Il valore è l'indice dell'elemento nella matrice. Tale indice viene aggiornato ogni volta che viene spostato un elemento. Questo rallenta le operazioni di heap di un fattore costante, ma ti dà la possibilità di localizzare un oggetto in O (1).
C'è anche qualcosa chiamato a Heap min-max, che è un tipo di heap binario che ti dà accesso O (1) sia all'elemento minimo che a quello massimo. L'implementazione è molto simile all'implementazione di un heap min binario standard.
Per confondere ancora di più le cose, esiste anchel'heap d-ary, che è un heap che contiene più di due figli per nodo. Ad esempio, un heap trinario ha tre figli per nodo. Anche questi sono implementati in array con puntatori figlio impliciti.
Esistono altre strutture di dati che sono comunementechiamati heap, ma in realtà non sono affatto correlati all'heap, tranne per il fatto che si tratta di implementazioni diverse della struttura dei dati delle code di priorità. I più popolari sembrano essere Heap di accoppiamento, heap di Fibonacci e heap binomiale, tutti elementi che possono anche essere implementato con alberi binari (di nuovo, non alberi di ricerca binari).
Ho scritto un'introduzione in qualche modo guidata a heap binari (e heap d-ary) nel mio blog qualche anno fa. Se sei interessato, dai un'occhiata questa voce, che elenca tutti gli articoli di quella serie.
2 per risposta № 2
Penso che tu stia confondendo il binario ricerca alberi e alberi binari. Un albero binario ha più una forma che altro: è un albero in cui ogni nodo ha al massimo due figli. I nodi non devono necessariamente avere valori al loro interno e, in caso affermativo, non è necessario che rispettino regole particolari.
Un binario ricerca tree è un albero binario in cui ogni nodo contiene achiave e ciascun nodo obbedisce alla regola secondo cui tutte le chiavi nella sottostruttura sinistra sono inferiori alla chiave del nodo e tutte le chiavi nella sottostruttura destra sono maggiori della chiave del nodo. (Alcune definizioni allentano il requisito di consentire meno-o-uguale-invece di appena meno di, ecc.)
Esistono molte altre strutture di dati costruite da alberi binari che non sono BST. Gli alberi k-d memorizzano dati multidimensionali. I tentativi binari memorizzano stringhe di bit.
Quindi penso che la migliore descrizione qui sia “binariagli heap sono alberi binari che sono completi e obbediscono alla proprietà heap, che non è la stessa di un albero di ricerca binario anche se hanno la stessa forma sottostante (più o meno) ".