Vad ' är skillnaden mellan ett binärt sökträd och en binär hög?

Heap garanterar bara att element på högre nivåer är större (för max-heap) eller mindre (för min-heap) än element på lägre nivåer, medan BST garanterar ordning (från ”vänster” till ”höger”) . Om du vill sortera element, gå med BST. av Dante är inte en nörd

Heap är bättre på findMin / findMax (O ( 1)), medan BST är bra för alla fynd (O (logN)). Infoga är O (logN) för båda strukturerna. Om du bara bryr dig om findMin / findMax (t.ex. prioritetsrelaterad), gå med heap. Om du vill allt sorterat, gå med BST.

av xysun

Kommentarer

• Jag tycker att BST är bättre i findMin & findMax stackoverflow .com / a / 27074221/764592
• Jag tror att det här bara är ett komm om missuppfattning. Ett binärt träd kan enkelt modifieras för att hitta min och max enligt Yeo. Detta är faktiskt en begränsning av högen: den enda effektiva sökningen är min eller max. Den verkliga fördelen med högen är O (1) genomsnittlig infogning som jag förklarar: stackoverflow.com/a/29548834/895245
• Enligt den här videon kan du ha större värden på en lägre nivå, så länge den större inte är en efterkommare av den nedre.
• Heap sorteras rot till blad och BST sorteras från vänster till höger.
• vad händer om jag vill hitta medianen i konstant tid och ta bort medianen i logaritmisk tid? vilken datastruktur ska jag gå till? fungerar implementering av MinHeap? vänligen föreslå.

Sammanfattning

 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) 

Alla genomsnittliga tider i denna tabell är desamma som de värsta tiderna förutom Infoga.

• *: överallt i detta svar, BST == Balanserad BST, eftersom obalanserad suger asymptotiskt
• **: med hjälp av en trivial modifiering som förklaras i det här svaret
• ***: log(n) för pekarträdets hög, n för dynamisk arrayheap

Fördelar med binär heap över en BST

• genomsnittlig tidsinsättning i en binär hög är O(1), för BST är O(log(n)). Denna är mördare i högar.

  Det finns också andra högar som når O(1) amorterat (starkare) som Fibonacci Heap , och till och med i värsta fall, som Brodal-kö , även om de kanske inte är praktiska på grund av icke-asymptotisk prestanda: https://stackoverflow.com/questions/30782636/are-fibonacci-heaps-or-brodal-queues-used-in-practice-anywhere

• binära högar kan implementeras effektivt ovanpå dynamiska matriser eller pekarbaserade träd, endast BST pekarbaserade träd. Så för högen kan vi välja en mer rymdeffektiv implementering av matriser, om vi har råd med enstaka storleksfördröjningar.

• binär höghantering är O(n) i värsta fall , O(n log(n)) för BST.

Fördel med BST jämfört med binär hög

• sökning efter godtyckliga element är O(log(n)). Denna är mördare i BSTs.

  För hög är det O(n) i allmänhet, förutom det största elementet som är O(1).

”Falsk” fördel med hög över BST

• heap är O(1) för att hitta max, BST O(log(n)).

  Detta är en vanlig missuppfattning, eftersom det är trivialt att ändra en BST för att hålla reda på det största elementet och uppdatera det närhelst det här elementet kan ändras: vid införande av en större swap, vid borttagning, hitta den näst största. https://stackoverflow.com/questions/7878622/can-we-use-binary-search-tree-to-simulate-heap-operation (nämns av Yeo ).

  Egentligen är detta en begränsning av högar jämfört med BST: den enda effektiva sökningen är den för det största elementet.

Genomsnittlig binär heapinsats är O(1)

Källor:

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

Intuitivt argument:

• nedre trädnivåer har exponentiellt fler element än toppnivåer, så nya element är nästan säkra att gå längst ner
• höginsättning börjar från botten , BST måste börja från början

I en binär hög är det också att öka värdet vid ett visst index O(1) av samma anledning. Men om du vill göra det är det troligt att du vill hålla ett extra index uppdaterad om högoperationer https://stackoverflow.com/questions/17009056/how-to-implement-ologn-decrease-key-operation-for-min-heap-based-priority-queu t.ex. för Dijkstra. Möjligt utan extra kostnad.

GCC C ++ standardbibliotek infoga riktmärke på riktig hårdvara

Jag benchmarkade C ++ std::set ( Rödsvart träd BST ) och std::priority_queue ( dynamisk matrishög ) infoga för att se om jag hade rätt i infogningstiderna, och det är vad jag fick:

• referenskod
• plot-skript
• plotdata
• testat på Ubuntu 19.04, GCC 8.3.0 i en Lenovo ThinkPad P51-bärbar dator med CPU: Intel Core i7-7820HQ CPU (4 kärnor / 8 trådar , 2,90 GHz-bas, 8 MB cache), RAM: 2x Samsung M471A2K43BB1-CRC (2x 16GiB, 2400 Mbps), SSD: Samsung MZVLB512HAJQ-000L7 (512 GB, 3000 MB / s)

Så tydligt:

• heap insert t ime är i grund och botten konstant.

  Vi ser tydligt storlekspunkter för dynamisk matris. Eftersom vi räknar i genomsnitt vart 10 000 inlägg för att kunna se någonting alls ovanför systembrus , är dessa toppar faktiskt ungefär 10 000 gånger större än visat!

  Den zoomade grafen utesluter i huvudsak endast gruppens storleksändringspunkter och visar att nästan alla inlägg faller under 25 nanosekunder.

• BST är logaritmiskt. Alla inlägg är mycket långsammare än den genomsnittliga högeninsatsen.

• BST vs hashmap detaljerad analys vid: https://stackoverflow.com/questions/18414579/what-data-structure-is-inside-stdmap-in-c/51945119#51945119

GCC C ++ standardbibliotek infoga riktmärke på gem5

gem5 är en fullständig systemsimulator och ger därför en oändligt exakt klocka med m5 dumpstats. Så jag försökte använda den för att uppskatta tidpunkter för enskilda insatser.

Tolkning:

• heapen är fortfarande konstant, men nu ser vi mer detaljerat att det finns några rader, och varje högre rad är mer gles .

  Detta måste motsvara minnesåtkomstfördröjningar för högre och högre insatser.

• TODO Jag kan inte riktigt tolka BST helt som den ser inte så logaritmisk ut och något mer konstant.

  Med denna större detalj kan vi dock se kan också se några distinkta rader, men jag är inte säker på vad de representerar: jag förväntar mig att vara tunnare, eftersom vi sätter upp längst ner?

Benchmarked med denna Buildroot-installation på en aarch64 HPI CPU .

BST kan inte implementeras effektivt på en matris

Heap operationer behöver bara bubbla upp eller ner i en enskild trädgren, så O(log(n)) worst case swaps, O(1) genomsnitt.

Att hålla en BST-balanserad kräver trädrotationer, vilket kan ändra toppelementet för en annan, och kräver att hela matrisen flyttas (O(n)).

Heapar kan implementeras effektivt på en array

Föräldra- och underordnade index kan beräknas från det aktuella indexet som visas här .

Det finns inga balanseringsåtgärder som BST.

Radera min är den mest oroande åtgärden eftersom den måste vara uppifrån och ner. Men det kan alltid göras genom att ”perkolera ner” en enda gren av högen som förklaras här . Detta leder till ett O (log (n)) värsta fall, eftersom högen alltid är välbalanserad.

Om du sätter in en enda nod för varje du tar bort, förlorar du fördelen med den asymptotiska O (1) genomsnittlig infogning som högar ger när borttagningen skulle dominera, och du kan lika gärna använda en BST. Dijkstra uppdaterar dock noder flera gånger för varje borttagning, så vi mår bra.

Dynamiska arrayheapar vs pekarträdshögar

Heaps kan implementeras effektivt ovanpå pekarhögarna: https://stackoverflow.com/questions/19720438/is-it-possible-to-make-efficient-pointer-based-binary-heap-implementations

Den dynamiska arrayimplementeringen är mer utrymmeeffektiv. Antag att varje heapelement bara innehåller en pekare till en struct:

• trädimplementeringen måste lagra tre pekare för varje element: parent, vänster barn och höger barn. Så minnesanvändningen är alltid 4n (tre trädpekare + 1 struct pekare).

  Trädets BST skulle också behöver ytterligare balansinformation, t.ex. svart-rödhet.

• implementeringen av den dynamiska matrisen kan vara av storlek 2n strax efter en fördubbling. Så i genomsnitt kommer det att bli 1.5n.

Å andra sidan har trädhögen bättre värsta fallet, för att kopiera den dynamiska backningmatrisen till att dubbla storleken tar O(n) i värsta fall, medan trädhögen bara gör nya små tilldelningar för varje nod.

Fortfarande, backningen Arbetsfördubbling är O(1) amorterad, så det kommer ner till en maximal latensövervägning. Här nämns .

Filosofi

• BST: er upprätthåller en global egenskap mellan en förälder och alla ättlingar (vänster mindre, höger större).

  Den övre noden på en BST är mittelementet , som kräver global kunskap för att upprätthålla (att veta hur många mindre och större element som finns).

  Denna globala egenskap är dyrare att underhålla (log n insert), men ger mer kraftfulla sökningar (log n search) .

• Högar upprätthåller en lokal egendom mellan föräldrar och direkta barn (förälder> barn).

  Den högsta anteckningen i en hög är det stora elementet, som kräver endast lokal kunskap för att upprätthålla (känna din förälder).

Jämföra BST vs Heap vs Hashmap:

• BST: kan antingen vara rimligt:

  • oordnad uppsättning (en struktur som avgör om ett element tidigare har infogats eller inte). Men hashmap tenderar att bli bättre på grund av O (1) amorterad insats.
  • sorteringsmaskin. Men heap är i allmänhet bättre på det, varför heapsort är mycket mer känt än trädsorter

• heap: är bara en sorteringsmaskin. Det kan inte vara en effektiv oordnad uppsättning, eftersom du bara kan söka efter det minsta / största elementet snabbt.

• hash-karta: kan bara vara en oordnad uppsättning, inte en effektiv sorteringsmaskin, eftersom hashing blandar ihop alla beställningar.

Dubbel länkad lista

En dubbelt länkad lista kan ses som en delmängd av högen där det första objektet har störst prioritet, så låt oss jämföra dem också här:

• insättning:
  • position:
    • dubbelt länkad lista: det infogade objektet måste vara antingen det första eller det sista, eftersom vi bara har pekare till dessa element.
    • binär hög: det infogade objektet kan hamna i valfri position. Mindre restriktiv än länkad lista.
  • tid:
    • dubbelt länkad lista: O(1) värsta fall eftersom vi har pekare på artiklarna och uppdateringen är väldigt enkel
    • binär heap: O(1) genomsnitt, alltså sämre än länkad lista. med mer allmän infogningsposition.
• sökning: O(n) för båda

Ett användningsfall för detta är när nyckeln till högen är den aktuella tidsstämpeln: i så fall kommer nya poster alltid att gå till början av listan. Så vi kan till och med glömma den exakta tidsstämpeln helt och hållet och bara behålla positionen i listan som prioritet.

Detta kan användas för att implementera en LRU-cache . Precis som för heap-applikationer som Dijkstra , vill du behålla en extra hashmap från nyckeln till motsvarande nod i listan för att hitta vilken nod som ska uppdateras snabbt .

Jämförelse av olika balanserad BST

Även om den asymptotiska infogar och hittar gånger för alla datastrukturer som vanligtvis klassificeras som ”Balanserade BST” som jag hittills har sett är desamma, har olika BBST olika avvägningar. Jag har inte studerat detta ännu, men det skulle vara bra att sammanfatta dessa avvägningar här:

• Rödsvart träd . Verkar vara den mest använda BBST från och med 2019, t.ex. det är den som används av GCC 8.3.0 C ++ -implementeringen
• AVL-träd . Verkar vara lite mer balanserad än BST, så det kan vara bättre att hitta latens, på bekostnad av något dyrare fynd.Wiki sammanfattar: ”AVL-träd jämförs ofta med röda-svarta träd eftersom båda stöder samma uppsättning operationer och tar [samma] tid för de grundläggande operationerna. För uppslagsintensiva applikationer är AVL-träd snabbare än röda-svarta träd eftersom de är mer balanserade. Liksom röda svarta träd är AVL-träd höjdbalanserade. Båda är i allmänhet varken viktbalanserade eller mu-balanserade för alla mu < 1 / 2, det vill säga syskonnoder kan ha enormt olika antal ättlingar. ”
• WAVL . originalpapper nämner fördelarna med den versionen i termer av gränser för ombalansering och rotation.

Se även

Liknande fråga om CS: Vad ' är skillnaden mellan ett binärt sökträd och en binär hög?

Kommentarer

• Bra svar . Vanlig tillämpning av hög är median, k min, top k-element. För dessa vanligaste operationer, ta bort min och sedan infoga (vanligtvis har vi en liten hög med få rena insättningsoperationer). Så verkar det som i praktiken, för dessa algoritmer överträffar det inte BST.
• Exceptionellt svar !!! Genom att använda deque som underliggande högstruktur kan du dramatiskt minska storleksändringstiderna, även om det fortfarande är O (n) i värsta fall eftersom det måste omfördela (mindre) matris med pekare till bitar.

Båda binära sökträd och binära högar är trädbaserade datastrukturer.

Högar kräver att noder har prioritet framför sina barn. I en maxhög måste varje nods barn vara mindre än sig själv. Detta är motsatsen för en minhög:

Binära sökträd (BST) följer en specifik ordning (förbeställning, beställning, postorder) bland syskonenoder. Trädet måste sorteras, till skillnad från högar:

BST har ett genomsnitt på $ O (\ log n) $ för insättning, radering och sökning.
Binära högar har i genomsnitt $ O (1) $ för findMin / findMax och $ O (\ log n) $ för infogning och radering.

Kommentarer

• @FrankW Extraction är $ O (\ log n) $, nej?

Ovanpå föregående svar måste högen ha egenskapen högstruktur ; trädet måste vara fullt, och det nedersta lagret, som inte alltid kan vara fullt, måste fyllas längst till höger utan luckor.