Hva ' er forskjellen mellom et binært søketre og en binær dyng?

Heap garanterer bare at elementer på høyere nivåer er større (for max-heap) eller mindre (for min-heap) enn elementer på lavere nivåer, mens BST garanterer orden (fra «venstre» til «høyre») . Hvis du vil ha sorterte elementer, gå med BST. av Dante er ikke en nerd

Heap er bedre på findMin / findMax (O ( 1)), mens BST er bra i alle funn (O (logN)). Insert er O (logN) for begge strukturer. Hvis du bare bryr deg om findMin / findMax (f.eks. Prioritetsrelatert), gå med heap. Hvis du vil alt sortert, gå med BST.

av xysun

Kommentarer

• Jeg tror BST er bedre i findMin & findMax stackoverflow .com / a / 27074221/764592
• Jeg tror dette bare er en kommisjon på misforståelse. Et binært tre kan enkelt modifiseres for å finne min og max som pekt av Yeo. Dette er faktisk en begrensning av dyngen: det eneste effektive funnet er min eller maks. Den virkelige fordelen med dyngen er O (1) gjennomsnittlig innsats som jeg forklarer: stackoverflow.com/a/29548834/895245
• I følge denne videoen , kan du ha større verdier på et lavere nivå, så lenge den største ikke er etterkommer av den nedre.
• Haug sorteres rot til blad og BST sorteres fra venstre til høyre.
• hva om jeg vil finne medianen i konstant tid og fjerne medianen i logaritmisk tid? hvilken datastruktur skal jeg gå for? fungerer implementering av MinHeap? vær så snill å foreslå.

Sammendrag

 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) 

Alle gjennomsnittstider på denne tabellen er de samme som de verste tidene bortsett fra Sett inn.

• *: overalt i dette svaret, BST == Balansert BST, siden ubalansert suger asymptotisk
• **: ved hjelp av en triviell modifikasjon forklart i dette svaret
• ***: log(n) for pekertrebunken, n for dynamisk array-heap

Fordeler med binær heap over en BST

• gjennomsnittlig tidsinnsetting i en binær haug er O(1), for BST er O(log(n)). Denne er drapsmannfunksjonen til dynger.

  Det er også andre dynger som når O(1) amortisert (sterkere) som Fibonacci Heap , og til og med i verste fall, som Brodal kø , selv om de kanskje ikke er praktiske på grunn av ikke-asymptotisk ytelse: https://stackoverflow.com/questions/30782636/are-fibonacci-heaps-or-brodal-queues-used-in-practice-anywhere

• binære dynger kan implementeres effektivt på toppen av enten dynamiske matriser eller pekerbaserte trær, bare BST pekerbaserte trær. Så for bunken kan vi velge den mer plasseffektive arrayimplementeringen, hvis vi har råd til sporadiske størrelsesforsinkelser.

• binær bunkeoppretting er O(n) worst case , O(n log(n)) for BST.

Fordelen med BST over binær bunke

• søk etter vilkårlige elementer er O(log(n)). Denne er drapsmannfunksjonen i BST-er.

  For heap er det O(n) generelt, bortsett fra det største elementet som er O(1).

«Falsk» fordel med dyng over BST

• bunke er O(1) for å finne maks, BST O(log(n)).

  Dette er en vanlig misforståelse, fordi det er trivielt å endre en BST for å holde oversikt over det største elementet, og oppdatere det når elementet kan endres: ved innsetting av en større bytte, ved fjerning, finn den nest største. https://stackoverflow.com/questions/7878622/can-we-use-binary-search-tree-to-simulate-heap-operation (nevnt av Yeo ).

  Egentlig er dette en begrensning av dynger sammenlignet med BST: det eneste effektive søket er det for det største elementet.

Gjennomsnittlig binær bunkeinnsats er O(1)

Kilder:

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

Intuitivt argument:

• bunnenivå av tre har eksponentielt flere elementer enn toppnivåer, så nye elementer er nesten sikre på å gå nederst
• hauginnføring starter fra bunnen , må BST starte fra toppen

I en binær bunke er det også å øke verdien ved en gitt indeks O(1) av samme grunn. Men hvis du vil gjøre det, er det sannsynlig at du vil holde en ekstra indeks oppdatert på dyngoperasjoner https://stackoverflow.com/questions/17009056/how-to-implement-ologn-decrease-key-operation-for-min-heap-based-priority-queu f.eks for Dijkstra. Mulig uten ekstra tidskostnad.

GCC C ++ standard biblioteksinnsats benchmark på ekte maskinvare

Jeg benchmarket C ++ std::set ( Rød-svart tre BST ) og std::priority_queue ( dynamisk matrishaug ) sett inn for å se om jeg hadde rett i innsettingstidene, og dette er hva jeg fikk:

• referansekode
• plotteskript
• plotdata
• testet på Ubuntu 19.04, GCC 8.3.0 i en Lenovo ThinkPad P51 bærbar PC med CPU: Intel Core i7-7820HQ CPU (4 kjerner / 8 tråder , 2,90 GHz base, 8 MB cache), RAM: 2x Samsung M471A2K43BB1-CRC (2x 16GiB, 2400 Mbps), SSD: Samsung MZVLB512HAJQ-000L7 (512 GB, 3000 MB / s)

Så tydelig:

• hauginnsats t ime er i utgangspunktet konstant.

  Vi ser tydelig størrelsespoeng for dynamiske matriser. Siden vi beregner et gjennomsnitt på hvert tiende innskudd for å kunne se noe i det hele tatt over systemstøy , er disse toppene faktisk omtrent ti tusen ganger større enn vist!

  Den zoomede grafen utelukker i hovedsak bare størrelsesendringspunktene for matrisen, og viser at nesten alle innsatser faller under 25 nanosekunder.

• BST er logaritmisk. Alle innleggene er mye tregere enn den gjennomsnittlige hauginnsatsen.

• BST vs hashmap detaljert analyse ved: https://stackoverflow.com/questions/18414579/what-data-structure-is-inside-stdmap-in-c/51945119#51945119

GCC C ++ standard bibliotek setter inn referanseindeks på gem5

gem5 er en full systemsimulator, og gir derfor en uendelig nøyaktig klokke med m5 dumpstats. Så jeg prøvde å bruke den til å estimere tidspunkter for individuelle innsatser.

Tolkning:

• bunken er fortsatt konstant, men nå ser vi mer detaljert at det er noen få linjer, og hver høyere linje er mer sparsom .

  Dette må tilsvare at minnetilgangsforsinkelser gjøres for høyere og høyere innlegg.

• TODO Jeg kan ikke virkelig tolke BST fullstendig som den ser ikke så logaritmisk og noe mer konstant ut.

  Med denne større detalj, men vi kan se, kan også se noen få forskjellige linjer, men jeg er ikke sikker på hva de representerer: Jeg forventer at bunnlinjen være tynnere siden vi setter inn øverste bunn?

Benchmarked med dette Buildroot-oppsettet på en aarch64 HPI CPU .

BST kan ikke implementeres effektivt på en matrise

Haug operasjoner trenger bare å boble opp eller ned en enkelt tregren, så O(log(n)) worst case swaps, O(1) gjennomsnitt.

Å holde en BST balansert krever trerotasjoner, som kan endre toppelementet for en annen, og vil kreve å flytte hele matrisen rundt (O(n)).

Heaps kan effektivt implementeres på en matrise

Foreldre- og underordnede indekser kan beregnes fra gjeldende indeks som vist her .

Det er ingen balanseringsoperasjoner som BST.

Slett min er den mest bekymringsfulle operasjonen da den må være ovenfra og ned. Men det kan alltid gjøres ved å «perkolere ned» en enkelt gren av dyngen som forklart her . Dette fører til en O (log (n)) verste sak, siden dyngen alltid er godt balansert.

Hvis du setter inn en enkelt node for hver du fjerner, mister du fordelen med den asymptotiske O (1) gjennomsnittsinnsats som dynger gir når slettingen ville dominere, og du kan like gjerne bruke en BST. Dijkstra oppdaterer imidlertid noder flere ganger for hver fjerning, så vi har det bra.

Dynamiske matrishauger vs pekertre-hauger

Hauger kan implementeres effektivt på toppen av pekerhaugene: https://stackoverflow.com/questions/19720438/is-it-possible-to-make-efficient-pointer-based-binary-heap-implementations

Den dynamiske arrayimplementeringen er mer plasseffektiv. Anta at hvert heapelement bare inneholder en peker til en struct:

• treimplementeringen må lagre tre pekere for hvert element: foreldre, venstre barn og høyre barn. Så minnebruk er alltid 4n (3 trepekere + 1 struct peker).

  Tre-BST vil også trenger ytterligere balanseringsinformasjon, f.eks svart-rødhet.

• implementeringen av den dynamiske matrisen kan være av størrelse 2n like etter en dobling. Så i gjennomsnitt blir det 1.5n.

På den annen side har trehaugen bedre verste innlegg, fordi det å kopiere den dynamiske matrisen til å støtte dobbelt til størrelsen tar O(n) i verste fall, mens trehaugen bare gjør nye små tildelinger for hver node.

Likevel, støtten dobling av matriser er O(1) amortisert, så det kommer til en maksimal latensbetraktning. Nevnt her .

Filosofi

• BST-er opprettholder en global egenskap mellom en forelder og alle etterkommere (venstre mindre, høyre større).

  Den øverste noden til en BST er midtelementet , som krever global kunnskap for å opprettholde (å vite hvor mange mindre og større elementer som er der).

  Denne globale eiendommen er dyrere å vedlikeholde (log n insert), men gir kraftigere søk (log n search) .

• Hauger opprettholder en lokal eiendom mellom foreldre og direkte barn (foreldre> barn).

  Den øverste tonen i en haug er det store elementet, som krever bare lokal kunnskap for å opprettholde (å kjenne foreldrene dine).

Sammenligning av BST vs Heap vs Hashmap:

• BST: kan enten være enten rimelig:

  • uordnet sett (en struktur som avgjør om et element tidligere ble satt inn eller ikke). Men hashmap har en tendens til å bli bedre på grunn av O (1) amortisert innsats.
  • sorteringsmaskin. Men dyng er generelt bedre på det, og det er derfor heapsort er mye mer kjent enn tresort

• bunke: er bare en sorteringsmaskin. Kan ikke være et effektivt ikke-ordnet sett, fordi du bare kan se etter det minste / største elementet raskt.

• hash-kart: kan bare være et ikke-ordnet sett, ikke en effektiv sorteringsmaskin, fordi hashing blander sammen hvilken som helst bestilling.

Dobbeltkoblet liste

En dobbeltkoblet liste kan sees på som en delmengde av haugen der det første elementet har størst prioritet, så la oss sammenligne dem også her:

• innsetting:
  • posisjon:
    • dobbeltkoblet liste: det innsatte elementet må være enten det første eller det siste, ettersom vi bare har pekere til disse elementene.
    • binær heap: det innsatte elementet kan havne i hvilken som helst posisjon. Mindre restriktiv enn koblet liste.
  • tid:
    • dobbeltkoblet liste: O(1) worst case siden vi har pekere på elementene, og oppdateringen er veldig enkel
    • binær bunke: O(1) gjennomsnitt, dermed verre enn koblet liste. har mer generell innsettingsposisjon.
• søk: O(n) for begge

Et brukstilfelle for dette er når nøkkelen til dyngen er det nåværende tidsstempelet: i så fall vil nye oppføringer alltid gå til begynnelsen av listen. Så vi kan til og med glemme den nøyaktige tidsstempelet helt, og bare holde posisjonen i listen som prioritet.

Dette kan brukes til å implementere en LRU-cache . Akkurat som for haugapplikasjoner som Dijkstra , vil du beholde en ekstra hashmap fra nøkkelen til den tilsvarende noden på listen, for å finne hvilken node du vil oppdatere raskt .

Sammenligning av forskjellig balansert BST

Selv om den asymptotiske setter inn og finner ganger for alle datastrukturer som ofte er klassifisert som «Balanserte BSTs» som jeg har sett så langt, er de samme, har forskjellige BBSTs forskjellige avveininger. Jeg har ikke studert dette helt, men det ville være bra å oppsummere disse kompromissene her:

• Rød-svart tre . Ser ut til å være den mest brukte BBST fra og med 2019, f.eks. det er den som brukes av GCC 8.3.0 C ++ implementering
• AVL-treet . Ser ut til å være litt mer balansert enn BST, så det kan være bedre å finne ventetid, på bekostning av litt dyrere funn.Wiki oppsummerer: «AVL-trær sammenlignes ofte med rød-svarte trær fordi begge støtter det samme settet med operasjoner og tar [samme] tid for de grunnleggende operasjonene. For oppslagsintensive applikasjoner er AVL-trær raskere enn rød-svarte trær fordi de er strengere balansert. I likhet med rød-svarte trær er AVL-trær høydebalansert. Begge er generelt ikke vektbalansert eller mu-balansert for noen mu < 1 / 2; det vil si at søskenoder kan ha veldig forskjellige etterkommere. «
• WAVL . originalpapiret nevner fordelene med den versjonen når det gjelder grensene for ombalansering og rotasjonsoperasjoner.

Se også

Lignende spørsmål på CS: Hva ' er forskjellen mellom et binært søketre og en binær dyng?

Kommentarer

• Flott svar . Vanlig anvendelse av dyngen er median, k min, top k-elementer. Fjern min og sett inn for denne vanligste operasjonen (vanligvis har vi en liten haug med få rene innsatsoperasjoner). Så virker som i praksis, for disse algoritmene overgår den ikke BST.
• Eksepsjonelt svar !!! Ved å bruke deque som underliggende haugstruktur, kan du redusere størrelsestiden dramatisk, selv om det fremdeles er O (n) i verste fall, siden det trenger å omfordele (mindre) utvalg av pekere til biter.

Både binære søketrær og binære dynger er trebaserte datastrukturer.

Hauger krever at nodene prioriteres foran barna sine. I en maks bunke må hvert nodes barn være mindre enn seg selv. Dette er det motsatte for en min bunke:

Binære søketrær (BST) følger en bestemt rekkefølge (forhåndsbestilling, ordre, etterbestilling) blant søskenoder. Treet må sorteres, i motsetning til dynger:

BST har gjennomsnittet $ O (\ log n) $ for innsetting, sletting og søk.
Binære dynger har gjennomsnitt $ O (1) $ for findMin / findMax og $ O (\ log n) $ for innsetting og sletting.

Kommentarer

• @FrankW Utvinning er $ O (\ log n) $, nei?

På toppen av de forrige svarene må haugen ha haugstrukturegenskapen ; treet må være fullt, og det nederste laget, som ikke alltid kan være fullt, må fylles til venstre til høyre uten hull.