Qual è ' la differenza tra un albero di ricerca binario e un heap binario?

Heap garantisce solo che gli elementi su livelli più alti siano maggiori (per max-heap) o più piccoli (per min-heap) rispetto agli elementi su livelli inferiori, mentre BST garantisce lordine (da “sinistra” a “destra”) . Se vuoi elementi ordinati, vai con BST. di Dante non è un geek

Heap è migliore in findMin / findMax (O ( 1)), mentre BST è buono in tutti i find (O (logN)). Insert è O (logN) per entrambe le strutture. Se ti interessa solo findMin / findMax (ad es. Relativo alla priorità), vai con heap. Se vuoi tutto in ordine, vai con BST.

di xysun

Commenti

• Penso che BST sia migliore in findMin & findMax stackoverflow .com / a / 27074221/764592
• Penso che sia solo una comunicazione su idee sbagliate. Un albero binario può essere facilmente modificato per trovare min e max come indicato da Yeo. Questa è in realtà una restrizione dellheap: l unica ricerca efficiente è min o max. Il vero vantaggio dellheap è O (1) inserto medio come spiego: stackoverflow.com/a/29548834/895245
• Secondo questo video , puoi avere valori maggiori a un livello inferiore, purché il maggiore non discenda di quello inferiore.
• Lheap è ordinato da radice a foglia e BST da sinistra a destra.
• E se volessi trovare la mediana in tempo costante e rimuovere la mediana in tempo logaritmico? quale struttura dati dovrei scegliere? limplementazione di MinHeap funzionerà? suggerisci.

Riepilogo

 Type BST (*) Heap Insert average log(n) 1 Insert worst log(n) log(n) or n (***) Find any worst log(n) n Find max worst 1 (**) 1 Create worst n log(n) n Delete worst log(n) log(n) 

Tutti i tempi medi in questa tabella sono gli stessi dei tempi peggiori tranne che per linserimento.

• *: ovunque in questa risposta, BST == BST bilanciato, poiché sbilanciato fa schifo in modo asintotico
• **: utilizzo di una modifica banale spiegata in questa risposta
• ***: log(n) per lheap dellalbero del puntatore, n per heap array dinamico

Vantaggi dellheap binario rispetto a un BST

• il tempo medio di inserimento in un heap binario è O(1), per BST è O(log(n)). Questo è la caratteristica killer degli heap.

  Ci sono anche altri heap che raggiungono O(1) ammortizzato (più forte) come Fibonacci Heap e anche nel caso peggiore, come Coda di Brodal , anche se potrebbero non essere pratiche a causa delle prestazioni non asintotiche: https://stackoverflow.com/questions/30782636/are-fibonacci-heaps-or-brodal-queues-used-in-practice-anywhere

• gli heap binari possono essere implementati in modo efficiente sopra gli array dinamici o gli alberi basati su puntatori, solo BST alberi basati su puntatori. Quindi per lheap possiamo scegliere limplementazione dellarray più efficiente in termini di spazio, se possiamo permetterci latenze di ridimensionamento occasionali.

• creazione di heap binario è O(n) caso peggiore , O(n log(n)) per BST.

Il vantaggio di BST rispetto allheap binario

• ricerca di elementi arbitrari è O(log(n)). Questa è la caratteristica killer dei BST.

  Per heap, è O(n) in generale, ad eccezione dellelemento più grande che è O(1).

Vantaggio “falso” dellheap rispetto a BST

• heap è O(1) per trovare BST massimo O(log(n)).

  Questo è unidea sbagliata comune, perché è banale modificare un BST per tenere traccia dellelemento più grande e aggiornarlo ogni volta che quellelemento potrebbe essere cambiato: allinserimento di uno scambio più grande, alla rimozione trova il secondo più grande. https://stackoverflow.com/questions/7878622/can-we-use-binary-search-tree-to-simulate-heap-operation (menzionato da Yeo ).

  In realtà, questa è una limitazione di cumuli rispetto ai BST: la unica ricerca efficiente è quella per lelemento più grande.

Linserimento di heap binario medio è O(1)

Fonti:

• Carta: http://i.stanford.edu/pub/cstr/reports/cs/tr/74/460/CS-TR-74-460.pdf
• Diapositive WSU: http://www.eecs.wsu.edu/~holder/courses/CptS223/spr09/slides/heaps.pdf

Argomento intuitivo:

• i livelli più bassi dellalbero hanno esponenzialmente più elementi rispetto ai livelli superiori, quindi è quasi certo che i nuovi elementi vadano in fondo
• inserimento heap inizia dal basso , BST deve iniziare dallalto

In un heap binario, laumento del valore in un dato indice è anche O(1) per lo stesso motivo. Ma se vuoi farlo, è probabile che tu voglia mantenere aggiornato un indice extra sulle operazioni di heap https://stackoverflow.com/questions/17009056/how-to-implement-ologn-decrease-key-operation-for-min-heap-based-priority-queu ad es per Dijkstra. Possibile senza costi aggiuntivi.

Benchmark dellinserimento della libreria standard GCC C ++ su hardware reale

Ho confrontato il C ++ std::set ( albero rosso-nero BST ) e std::priority_queue ( heap di array dinamico ) inserire per vedere se avevo ragione sui tempi di inserimento, e questo è quello che ho ottenuto:

• codice benchmark
• script di trama
• grafico dei dati
• testato su Ubuntu 19.04, GCC 8.3.0 in un laptop Lenovo ThinkPad P51 con CPU: CPU Intel Core i7-7820HQ (4 core / 8 thread , 2,90 GHz di base, 8 MB di cache), RAM: 2x Samsung M471A2K43BB1-CRC (2x 16GiB, 2400 Mbps), SSD: Samsung MZVLB512HAJQ-000L7 (512 GB, 3.000 MB / s)

Quindi chiaramente:

• heap insert t ime è fondamentalmente costante.

  Possiamo vedere chiaramente i punti di ridimensionamento degli array dinamici. Poiché stiamo calcolando una media ogni 10k di inserimenti per essere in grado di vedere qualsiasi cosa al di sopra del rumore di sistema , questi picchi sono in realtà circa 10k volte più grandi di quanto mostrato!

  Il grafico ingrandito esclude essenzialmente solo i punti di ridimensionamento dellarray e mostra che quasi tutti gli inserimenti sono inferiori a 25 nanosecondi.

• BST è logaritmico. Tutti gli inserimenti sono molto più lenti dellinserimento di heap medio.

• Analisi dettagliata BST e hashmap su: https://stackoverflow.com/questions/18414579/what-data-structure-is-inside-stdmap-in-c/51945119#51945119

benchmark dellinserimento della libreria standard GCC C ++ su gem5

gem5 è un simulatore di sistema completo e quindi fornisce un orologio infinitamente accurato con m5 dumpstats. Quindi ho provato a usarlo per stimare i tempi per i singoli inserti.

Interpretazione:

• lheap è ancora costante, ma ora vediamo più in dettaglio che ci sono poche righe e ogni riga superiore è più sparsa .

  Questo deve corrispondere alle latenze di accesso alla memoria sono fatte per inserimenti sempre più alti.

• PER TUTTO Non posso davvero interpretare il BST completamente come esso non sembra così logaritmico e un po più costante.

  Con questo dettaglio maggiore, tuttavia, possiamo vedere anche alcune linee distinte, ma non sono sicuro di cosa rappresentino: mi aspetto che la linea di fondo essere più sottile, dato che inseriamo in alto in basso?

Benchmarked con questa configurazione Buildroot su un aarch64 CPU HPI .

BST non può essere implementato in modo efficiente su un array

Heap le operazioni devono solo salire o scendere un singolo ramo di un albero, quindi O(log(n)) peggiore dei casi, O(1) nella media.

Mantenere un BST bilanciato richiede rotazioni dellalbero, che possono cambiare lelemento superiore con un altro e richiederebbe lo spostamento dellintero array intorno (O(n)).

Gli heap possono essere implementati in modo efficiente su un array

Gli indici padre e figlio possono essere calcolati dallindice corrente come mostrato qui .

Non ci sono operazioni di bilanciamento come BST.

Elimina min è loperazione più preoccupante in quanto deve essere dallalto verso il basso. Ma è sempre possibile “filtrare” un singolo ramo dellheap come spiegato qui . Questo porta a un caso peggiore O (log (n)), poiché lheap è sempre ben bilanciato.

Se stai inserendo un singolo nodo per ognuno che rimuovi, perdi il vantaggio dellasintotico O (1) inserto medio fornito dagli heap mentre leliminazione dominerebbe, e potresti anche usare un BST. Dijkstra tuttavia aggiorna i nodi più volte per ogni rimozione, quindi stiamo bene.

Heap di array dinamici vs heap di albero di puntatori

Gli heap possono essere implementati in modo efficiente sopra gli heap di puntatori: https://stackoverflow.com/questions/19720438/is-it-possible-to-make-efficient-pointer-based-binary-heap-implementations

Limplementazione dellarray dinamico è più efficiente in termini di spazio. Supponiamo che ogni elemento dellheap contenga solo un puntatore a un struct:

• limplementazione dellalbero deve memorizzare tre puntatori per ogni elemento: genitore, bambino sinistro e bambino destro. Quindi lutilizzo della memoria è sempre 4n (3 puntatori ad albero + 1 puntatore struct).

  Anche i BST ad albero lo farebbero necessitano di ulteriori informazioni di bilanciamento, ad es black-red-ness.

• limplementazione dellarray dinamico può avere le dimensioni 2n subito dopo un raddoppio. Quindi, in media, sarà 1.5n.

Daltra parte, lheap dellalbero ha un inserimento del caso peggiore migliore, perché copiare larray dinamico di supporto per raddoppiarne le dimensioni richiede O(n) il caso peggiore, mentre lheap dellalbero esegue solo nuove piccole allocazioni per ogni nodo.

Tuttavia, il supporto il raddoppio dellarray viene O(1) ammortizzato, quindi si riduce a una considerazione della latenza massima. Menzionato qui .

Filosofia

• I BST mantengono una proprietà globale tra un genitore e tutti i discendenti (a sinistra più piccolo, a destra più grande).

  Il nodo superiore di un BST è lelemento centrale , che richiede una conoscenza globale da mantenere (sapere quanti elementi più piccoli e più grandi ci sono).

  Questa proprietà globale è più costosa da mantenere (log n insert), ma fornisce ricerche più potenti (log n search) .

• Gli heap mantengono una proprietà locale tra genitore e figli diretti (genitore> figli).

  La nota superiore di un mucchio è lelemento grande, che richiede solo la conoscenza locale per mantenere (conoscere il tuo genitore).

Confronto tra BST e Heap e Hashmap:

• BST: può essere un valore ragionevole:

  • insieme non ordinato (una struttura che determina se un elemento è stato precedentemente inserito o meno). Ma hashmap tende ad essere migliore a causa dellinserto ammortizzato O (1).
  • macchina di smistamento. Ma lheap è generalmente migliore in questo, motivo per cui heapsort è molto più conosciuto di tree sort

• heap: è solo una macchina di smistamento. Non può essere un insieme non ordinato efficiente, perché puoi controllare velocemente solo lelemento più piccolo / più grande.

• mappa hash: può essere solo un insieme non ordinato, non una macchina di ordinamento efficiente, perché lhashing confonde qualsiasi ordine.

Elenco a doppio collegamento

Una lista doppiamente collegata può essere vista come sottoinsieme dellheap in cui il primo elemento ha la massima priorità, quindi confrontiamoli anche qui:

• inserimento:
  • posizione:
    • lista doppiamente collegata: lelemento inserito deve essere il primo o lultimo, poiché abbiamo solo puntatori a quegli elementi.
    • heap binario: lelemento inserito può finire in qualsiasi posizione. Meno restrittivo dellelenco collegato.
  • ora:
    • elenco doppiamente collegato: O(1) caso peggiore poiché abbiamo puntatori agli elementi e laggiornamento è davvero semplice
    • heap binario: O(1) medio, quindi peggiore dellelenco collegato. con una posizione di inserimento più generale.
• cerca: O(n) per entrambi

Un caso duso per questo è quando la chiave dellheap è il timestamp corrente: in quel caso, le nuove voci andranno sempre allinizio della lista. Quindi possiamo persino dimenticare del tutto il timestamp esatto e mantenere la posizione nellelenco come priorità.

Questo può essere utilizzato per implementare una cache LRU . Proprio come per le applicazioni heap come Dijkstra , ti consigliamo di mantenere una hashmap aggiuntiva dalla chiave al nodo corrispondente dellelenco, per trovare quale nodo aggiornare rapidamente .

Confronto di diversi BST bilanciati

Sebbene linserimento asintotico e trova i tempi per tutte le strutture di dati che sono comunemente classificate come “BST bilanciate” che ho visto finora sono gli stessi, BBST diversi hanno compromessi diversi. Non lho ancora studiato a fondo, ma sarebbe bene riassumere questi compromessi qui:

• albero rosso-nero . Sembra essere il BBST più comunemente usato nel 2019, ad es. è quello utilizzato dallimplementazione C ++ di GCC 8.3.0
• albero AVL . Sembra essere un po più bilanciato del BST, quindi potrebbe essere migliore per trovare la latenza, a costo di ritrovamenti leggermente più costosi.Wiki riassume: “Gli alberi AVL vengono spesso confrontati con gli alberi rosso-nero perché entrambi supportano lo stesso insieme di operazioni e impiegano [lo stesso] tempo per le operazioni di base. Per le applicazioni ad alta intensità di ricerca, gli alberi AVL sono più veloci degli alberi rosso-nero perché sono più strettamente bilanciati. Simili agli alberi rosso-neri, gli alberi AVL sono bilanciati in altezza. Entrambi, in generale, non sono né bilanciati in peso né mu-bilanciati per qualsiasi mu < 1 / 2; ovvero, i nodi di pari livello possono avere un numero di discendenti estremamente diverso. “
• WAVL . Il documento originale menziona i vantaggi di quella versione in termini di limiti sulle operazioni di ribilanciamento e rotazione.

Vedi anche

Domanda simile su CS: Cosa ' è la differenza tra un albero di ricerca binario e un heap binario?

Commenti

• Ottima risposta . Lapplicazione comune di heap è mediana, k min, top k elementi. Per queste operazioni più comuni, rimuovere min quindi inserire (di solito abbiamo un piccolo heap con poche operazioni di inserimento puro). Quindi sembra che in pratica, per questi algoritmi non supera BST.
• Risposta eccezionale !!! Usando deque come struttura di heap sottostante, puoi ridurre drasticamente i tempi di ridimensionamento, sebbene sia ancora O (n) il caso peggiore poiché deve riallocare un array (più piccolo) di puntatori a blocchi.

Entrambi alberi di ricerca binaria e binary heap sono strutture di dati basate su albero.

heap richiedono che i nodi abbiano una priorità sui loro figli. In un heap massimo, i figli di ogni nodo devono essere inferiori a se stesso. Questo è lopposto per un heap minimo:

Gli alberi di ricerca binari (BST) seguono un ordine specifico (pre-ordine, in ordine, post-ordine) tra i nodi di pari livello. Lalbero deve deve essere ordinato, a differenza degli heap:

BST ha una media di $ O (\ log n) $ per linserimento, leliminazione e la ricerca.
Gli heap binari hanno $ O (1) $ nella media per findMin / findMax e $ O (\ log n) $ per inserimento ed eliminazione.

Commenti

• @FrankW Extraction is $ O (\ log n) $, no?

Con la struttura dei dati si devono distinguere i livelli di interesse.

1. Le strutture di dati astratte (oggetti memorizzati, le loro operazioni) in questo q le uestion sono diverse. Uno implementa una coda di priorità, laltro un set. Una coda con priorità non è interessata a trovare un elemento arbitrario, solo quello con la priorità maggiore.

2. L implementazione concreta delle strutture. Qui a prima vista sono entrambi alberi (binari), con proprietà strutturali differenti. Differiscono sia lordine relativo delle chiavi che le possibili strutture globali. (Un po impreciso, in un BST le chiavi sono ordinate da sinistra a destra, in un heap sono ordinate dallalto verso il basso.) Come IPlant osserva correttamente, anche un heap dovrebbe essere “completo” .

3. Cè unultima differenza nell implementazione di basso livello . Un albero di ricerca binario (sbilanciato) ha unimplementazione standard che utilizza i puntatori. Un heap binario al contrario ha unimplementazione efficiente utilizzando un array (proprio a causa della struttura ristretta).

Oltre alle risposte precedenti, lheap deve avere la proprietà della struttura dellheap ; lalbero deve essere pieno e il livello più in basso, che non può essere sempre pieno, deve essere riempito da sinistra a destra senza spazi.