Disse to virker meget ens og har næsten en identisk struktur. Hvad er forskellen? Hvad er tidskompleksiteten for forskellige operationer for hver?
Svar
Heap garanterer bare, at elementer på højere niveauer er større (for max-heap) eller mindre (for min-bunke) end elementer på lavere niveauer, mens BST garanterer orden (fra “venstre” til “højre”) . Hvis du vil have sorterede elementer, skal du gå med BST. af Dante er ikke en nørd
Heap er bedre til findMin / findMax (O ( 1)), mens BST er god til alle fund (O (logN)). Insert er O (logN) for begge strukturer. Hvis du kun er interesseret i findMin / findMax (f.eks. Prioritetsrelateret), skal du gå med heap. Hvis du vil alt sorteret, gå med BST.
Kommentarer
- Jeg synes BST er bedre i findMin & findMax stackoverflow .com / a / 27074221/764592
- Jeg tror, det er bare et komm om misforståelse. Et binært træ kan let ændres for at finde min og max som peget af Yeo. Dette er faktisk en begrænsning af bunken: det eneste effektive fund er min eller maks. Den virkelige fordel ved bunken er O (1) gennemsnitlig indsats som jeg forklarer: stackoverflow.com/a/29548834/895245
- I henhold til denne video kan du have større værdier på et lavere niveau, så længe den største ikke stammer fra den nederste.
- Bunke sorteres rod til blad og BST sorteres fra venstre til højre.
- hvad hvis jeg vil finde medianen i konstant tid og fjerne medianen i logaritmisk tid? hvilken datastruktur skal jeg gå efter? fungerer implementering af MinHeap? foreslå det.
Svar
Oversigt
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 gennemsnitstider på denne tabel er de samme som deres værste tidspunkter undtagen Insert.
-
*: overalt i dette svar, BST == Balanceret BST, da ubalanceret suger asymptotisk -
**: ved hjælp af en triviel ændring forklaret i dette svar -
***:log(n)til pointertræbunke,ntil dynamisk array-heap
Fordele ved binær heap i forhold til en BST
-
gennemsnitstidsindsættelse i en binær bunke er
O(1), for BST erO(log(n)). Denne er dræberfunktionen i dynger.Der er også andre dynger, der når
O(1)amortiseret (stærkere) ligesom Fibonacci Heap , og endda i værste fald som Brodal kø , selvom de muligvis ikke er praktiske på grund af ikke-asymptotisk præstation: https://stackoverflow.com/questions/30782636/are-fibonacci-heaps-or-brodal-queues-used-in-practice-anywhere -
binære dynger kan implementeres effektivt oven på enten dynamiske arrays eller markørbaserede træer, kun BST pointerbaserede træer. Så for bunken kan vi vælge den mere pladseffektive arrayimplementering, hvis vi har råd til lejlighedsvis størrelse på latenstider.
-
oprettelse af binær bunke er
O(n)worst case ,O(n log(n))for BST.
Fordelen ved BST i forhold til binær heap
-
søgning efter vilkårlige elementer er
O(log(n)). Denne er dræberfunktionen i BSTer.For heap er det
O(n)generelt, bortset fra det største element, der erO(1).
“Falsk” fordel ved bunke i forhold til BST
-
bunke er
O(1)for at finde max, BSTO(log(n)).Dette er en almindelig misforståelse, fordi det er trivielt at ændre en BST for at holde styr på det største element og opdatere det, når dette element kunne ændres: ved indsættelse af en større swap, ved fjernelse, find den næststørste. https://stackoverflow.com/questions/7878622/can-we-use-binary-search-tree-to-simulate-heap-operation (nævnt af Yeo ).
Faktisk er dette en begrænsning af dynger sammenlignet med BSTer: den eneste effektive søgning er den for det største element.
Gennemsnitlig binær bunkeindsats er O(1)
Kilder:
- Papir: http://i.stanford.edu/pub/cstr/reports/cs/tr/74/460/CS-TR-74-460.pdf
- WSU-dias: http://www.eecs.wsu.edu/~holder/courses/CptS223/spr09/slides/heaps.pdf
Intuitivt argument:
- Træniveauer i bunden har eksponentielt flere elementer end topniveauer, så nye elementer er næsten sikre på at gå i bunden
- bunkeindsættelse starter fra bunden , BST skal starte fra toppen
I en binær bunke er øgning af værdien ved et givet indeks også O(1) af samme grund. Men hvis du vil gøre det, er det sandsynligt, at du vil holde et ekstra indeks opdateret om bunkeoperationer https://stackoverflow.com/questions/17009056/how-to-implement-ologn-decrease-key-operation-for-min-heap-based-priority-queu f.eks til Dijkstra. Mulig uden ekstra omkostninger.
GCC C ++ standardbibliotek indsætter benchmark på ægte hardware
Jeg benchmarkede C ++ std::set ( Rød-sort træ BST ) og std::priority_queue ( dynamisk array-bunke ) indsæt for at se, om jeg havde ret i indsættelsestiderne, og det er hvad jeg fik:
- benchmark kode
- plot script
- plotdata
- testet på Ubuntu 19.04, GCC 8.3.0 i en Lenovo ThinkPad P51 bærbar computer med CPU: Intel Core i7-7820HQ CPU (4 kerner / 8 tråde , 2,90 GHz base, 8 MB cache), RAM: 2x Samsung M471A2K43BB1-CRC (2x 16GiB, 2400 Mbps), SSD: Samsung MZVLB512HAJQ-000L7 (512 GB, 3.000 MB / s)
Så klart:
-
bunkeindsats t ime er grundlæggende konstant.
Vi kan tydeligt se dynamiske array-størrelsesændringspunkter. Da vi beregner et gennemsnit på hver 10.000 indsatser for overhovedet at kunne se noget over systemstøj , er disse toppe faktisk ca. 10.000 gange større end vist!
Den zoomede graf udelukker i det væsentlige kun array-størrelsesstørrelsespunkterne og viser, at næsten alle indsatser falder under 25 nanosekunder.
-
BST er logaritmisk. Alle indsatser er meget langsommere end den gennemsnitlige bunkeindsats.
-
BST vs hashmap detaljeret analyse ved: https://stackoverflow.com/questions/18414579/what-data-structure-is-inside-stdmap-in-c/51945119#51945119
GCC C ++ standardbibliotek indsæt benchmark på gem5
gem5 er en komplet systemsimulator og giver derfor et uendeligt nøjagtigt ur med m5 dumpstats. Så jeg forsøgte at bruge det til at estimere tidspunkter for individuelle indsatser.
Fortolkning:
-
bunken er stadig konstant, men nu ser vi mere detaljeret, at der er et par linjer, og hver højere linje er mere sparsom .
Dette skal svare til hukommelsesadgangsforsinkelser for højere og højere indsatser.
-
TODO Jeg kan ikke rigtig fortolke BST fuldt ud som den ser ikke så logaritmisk og noget mere konstant ud.
Med denne større detalje kan vi dog se kan også se et par forskellige linjer, men jeg er ikke sikker på, hvad de repræsenterer: Jeg forventer, at bundlinjen til være tyndere, da vi indsætter øverste bund?
Benchmarked med denne Buildroot-opsætning på en aarch64 HPI CPU .
BST kan ikke implementeres effektivt på et array
Bunke handlinger behøver kun at boble op eller ned ad en enkelt gren, så O(log(n)) worst case swaps, O(1) gennemsnit.
At holde en BST-afbalanceret kræver trærotationer, som kan ændre topelementet til en anden, og det ville kræve, at hele arrayet flyttes rundt (O(n)). div id = “0503d5884c”>
Heaps kan effektivt implementeres på et array
Forældre- og børneindeks kan beregnes ud fra det aktuelle indeks som vist her .
Der er ingen balanceringshandlinger som BST.
Slet min er den mest bekymrende handling, da den skal være ovenfra og ned. Men det kan altid gøres ved at “percolere ned” en enkelt gren af bunken som forklaret her . Dette fører til et O (log (n)) værste tilfælde, da bunken altid er velafbalanceret.
Hvis du indsætter en enkelt node for hver du fjerner, mister du fordelen ved den asymptotiske O (1) gennemsnitlig indsats, som dynger giver, da sletningen vil dominere, og du kan lige så godt bruge en BST. Dijkstra opdaterer dog noder flere gange for hver fjernelse, så vi har det godt.
Dynamiske array-dynger versus markørtræ-bunker
Bunker kan implementeres effektivt oven på markørbunker: https://stackoverflow.com/questions/19720438/is-it-possible-to-make-efficient-pointer-based-binary-heap-implementations
Den dynamiske arrayimplementering er mere pladseffektiv. Antag at hvert bunkeelement kun indeholder en markør til en struct:
-
træimplementeringen skal gemme tre markører for hvert element: overordnet, venstre barn og højre barn. Så hukommelsesforbruget er altid
4n(3 træmarkører + 1struct-markør).Træ-BSTer ville også har brug for yderligere balanceoplysninger, f.eks sort-rødhed.
-
den dynamiske arrayimplementering kan have størrelse
2nlige efter en fordobling. Så i gennemsnit bliver det1.5n.
På den anden side har træbunken bedre worst case insert, fordi det at kopiere det dynamiske array til understøttelse til at fordoble dets størrelse tager O(n) i værste fald, mens træbunken bare udfører nye små allokeringer for hver node.
Stadig, backing fordobling af array er O(1) amortiseret, så det kommer ned til en maksimal ventetid. Nævnt her .
Filosofi
-
BSTer opretholder en global egenskab mellem en forælder og alle efterkommere (venstre mindre, højre større).
Den øverste knude på en BST er det midterste element , som kræver global viden for at vedligeholde (at vide hvor mange mindre og større elementer der er).
Denne globale ejendom er dyrere at vedligeholde (log n indsæt), men giver mere kraftfulde søgninger (log n søgning) .
-
Bunke opretholder en lokal ejendom mellem forældre og direkte børn (forælder> børn).
Den øverste note i en bunke er det store element, som kræver kun lokal viden for at vedligeholde (at kende din forælder).
Sammenligning af BST vs Heap vs Hashmap:
-
BST: kan enten være enten en rimelig:
-
bunke: er bare en sorteringsmaskine. Kan ikke være et effektivt ikke-ordnet sæt, fordi du kun kan kontrollere det mindste / største element hurtigt.
-
hash-kort: kan kun være et ikke-ordnet sæt, ikke en effektiv sorteringsmaskine, fordi hashing blander enhver ordre.
Dobbeltkoblet liste
En dobbeltkoblet liste kan ses som en delmængde af bunken, hvor det første element har størst prioritet, så lad os også sammenligne dem her:
- indsættelse:
- position:
- dobbeltkoblet liste: det indsatte element skal være enten det første eller det sidste, da vi kun har pegepunkter til disse elementer.
- binær bunke: det indsatte element kan ende i en hvilken som helst position. Mindre restriktiv end linket liste.
- tid:
- dobbeltkædet liste:
O(1)worst case, da vi har henvisninger til varerne, og opdateringen er virkelig enkel - binær bunke:
O(1)gennemsnit, dermed værre end sammenkædet liste. har en mere generel indsættelsesposition.
- dobbeltkædet liste:
- position:
- søgning:
O(n)for begge
En brugssag til dette er, når nøglen til bunken er det aktuelle tidsstempel: i så fald vil nye poster altid gå til begyndelsen af listen. Så vi kan endda glemme det nøjagtige tidsstempel helt og bare holde positionen på listen som prioritet.
Dette kan bruges til at implementere en LRU-cache . Ligesom til bunkapplikationer som Dijkstra , vil du beholde en ekstra hashmap fra nøglen til den tilsvarende node på listen for at finde ud af, hvilken node der hurtigt skal opdateres .
Sammenligning af forskellige afbalancerede BST
Selvom den asymptotiske indsætter og finder gange for alle datastrukturer, der almindeligvis er klassificeret som “Balancerede BSTer”, som jeg hidtil har set, er de samme, har forskellige BBSTer forskellige afvejninger. Jeg har ikke studeret dette endnu, men det ville være godt at opsummere disse kompromiser her:
- Rød-sort træ . Ser ud til at være den mest anvendte BBST fra og med 2019, f.eks. det er den, der bruges af GCC 8.3.0 C ++ implementeringen
- AVL-træ . Ser ud til at være lidt mere afbalanceret end BST, så det kan være bedre at finde ventetid på bekostning af lidt dyrere fund.Wiki opsummerer: “AVL-træer sammenlignes ofte med rød-sorte træer, fordi begge understøtter det samme sæt operationer og tager [samme] tid til de grundlæggende operationer. Til opslagsintensive applikationer er AVL-træer hurtigere end rød-sorte træer, fordi de er mere strengt afbalancerede. I lighed med rød-sorte træer er AVL-træer højdeabalancerede. Begge er generelt hverken vægtafbalancerede eller mu-afbalancerede for enhver mu < 1 / 2; det vil sige, at søskendeknuder kan have meget forskellige efterkommere. “
- WAVL . originalt papir nævner fordelene ved denne version med hensyn til grænser for genbalancering og rotation.
Se også
Lignende spørgsmål om CS: Hvad ‘ er forskellen mellem et binært søgetræ og en binær bunke?
Kommentarer
- Fantastisk svar . Almindelig anvendelse af dyngen er median, k min, top k-elementer. Fjern til min mest derefter indsæt til disse mest almindelige operationer (normalt har vi en lille bunke med få rene indsætningsoperationer). Så det virker som i praksis, for disse algoritmer overgår det ikke BST.
- Enestående svar !!! Ved at bruge deque som underliggende bunkestruktur kan du dramatisk reducere størrelsestiden, selvom det stadig er O (n) i værste tilfælde, da det er nødvendigt at omfordele (mindre) vifte af pekere til bidder.
Svar
Både binære søgetræer og binære dynger er træbaserede datastrukturer.
Bunker kræver, at knudepunkterne prioriteres over deres børn. I en maksimal bunke skal hvert nodes børn være mindre end sig selv. Dette er det modsatte for en min bunke:
Binære søgetræer (BST) følger en bestemt rækkefølge (forudbestilling, i rækkefølge, efterbestilling) blandt søskendeknuder. Træet skal sorteres i modsætning til dynger:
BST har et gennemsnit på $ O (\ log n) $ til indsættelse, sletning og søgning.
Binære dynger har gennemsnit $ O (1) $ for findMin / findMax og $ O (\ log n) $ til indsættelse og sletning.
Kommentarer
- @FrankW Extraction er $ O (\ log n) $, nej?
Svar
Med datastrukturen skal man skelne mellem bekymringsniveauer.
-
De abstrakte datastrukturer (objekter gemt, deres operationer) i dette q Uestion er forskellige. Den ene implementerer en prioritetskø, den anden et sæt. En prioritetskø er ikke interesseret i at finde et vilkårligt element, kun det med den største prioritet.
-
Den konkrete implementering af strukturer. Her ved første øjekast er begge (binære) træer, men med forskellige strukturelle egenskaber. Både den relative rækkefølge af nøglerne og de mulige globale strukturer er forskellige. (Noget upræcist, i en
BSTtaster bestilles fra venstre mod højre, i en bunke bestilles de ovenfra og ned.) Som IPlant korrekt bemærker, skal en bunke også være “komplet” . -
Der er en endelig forskel i implementering på lavt niveau . Et (ubalanceret) binært søgetræ har en standardimplementering ved hjælp af pekere. En binær bunke til det modsatte har en effektiv implementering ved hjælp af en matrix (netop på grund af den begrænsede struktur).
Svar
Oven på de tidligere svar skal bunken have egenskaben bunkestruktur ; træet skal være fuldt, og det nederste lag, som ikke altid kan være fuldt, skal udfyldes længst til venstre til højre uden huller.