Wat is ' is het verschil tussen een binaire zoekboom en een binaire heap?

Heap garandeert alleen dat elementen op hogere niveaus groter (voor max-heap) of kleiner (voor min-heap) zijn dan elementen op lagere niveaus, terwijl BST de volgorde garandeert (van “links” naar “rechts”) . Als je gesorteerde elementen wilt, ga dan voor BST. door Dante is geen nerd

Heap is beter in findMin / findMax (O ( 1)), terwijl BST goed is voor alle vondsten (O (logN)). Invoegen is O (logN) voor beide structuren. Als je alleen om findMin / findMax geeft (bijv. Prioriteit-gerelateerd), ga dan met heap. Als je wilt alles gesorteerd, ga met BST.

door xysun

Reacties

• Ik denk dat BST beter is in findMin & findMax stackoverflow .com / a / 27074221/764592
• Ik denk dat dit maar een comm op misvatting. Een binaire boom kan eenvoudig worden aangepast om min en max te vinden zoals aangegeven door Yeo. Dit is eigenlijk een beperking van de heap: de enige efficiënte zoekopdracht is min of max. Het echte voordeel van de heap is O (1) gemiddelde invoeging zoals ik uitleg: stackoverflow.com/a/29548834/895245
• Volgens deze video kun je hogere waarden hebben op een lager niveau, zolang de grotere niet afstamt van de lagere.
• Heap wordt van wortel tot blad gesorteerd en BST wordt van links naar rechts gesorteerd.
• Wat moet ik doen als ik de mediaan in constante tijd wil vinden en mediaan in logaritmische tijd wil verwijderen? voor welke datastructuur moet ik gaan? werkt het implementeren van MinHeap? stel alstublieft voor.

Samenvatting

 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 gemiddelde tijden op deze tabel zijn hetzelfde als hun slechtste tijden behalve Invoegen.

• *: overal in dit antwoord, BST == Evenwichtige BST, aangezien ongebalanceerd asymptotisch zuigt
• **: gebruikmakend van een triviale wijziging uitgelegd in dit antwoord
• ***: log(n) voor pointer tree heap, n voor dynamische arrayheap

Voordelen van binaire heap ten opzichte van een BST

• gemiddelde tijd tussen invoegen in een binaire heap is O(1), voor BST is O(log(n)). Deze is de dodelijke eigenschap van hopen.

  Er zijn ook andere hopen die O(1) afgeschreven (sterker) zoals de Fibonacci Heap , en zelfs in het ergste geval, zoals de Brodal-wachtrij , hoewel ze misschien niet praktisch zijn vanwege niet-asymptotische prestaties: https://stackoverflow.com/questions/30782636/are-fibonacci-heaps-or-brodal-queues-used-in-practice-anywhere

• binaire hopen kunnen efficiënt worden geïmplementeerd bovenop dynamische arrays of op aanwijzers gebaseerde bomen, alleen BST op aanwijzer gebaseerde bomen. Dus voor de heap kunnen we de meer ruimte-efficiënte array-implementatie kiezen, als we het ons kunnen veroorloven om af en toe latenties te wijzigen.

• creatie van binaire heap is O(n) worst case , O(n log(n)) voor BST.

Voordeel van BST ten opzichte van binaire heap

• zoeken naar willekeurige elementen is O(log(n)). Dit is de geweldige eigenschap van BSTs.

  Voor heap is het O(n) in het algemeen, behalve het grootste element dat O(1) is.

“False” voordeel van heap ten opzichte van BST

• heap is O(1) om max, BST te vinden O(log(n)).

  Dit is een veel voorkomende misvatting, omdat het triviaal is om een BST te wijzigen om het grootste element bij te houden, en het bij te werken wanneer dat element zou kunnen worden gewijzigd: bij het invoegen van een grotere wissel, zoek bij verwijdering het op een na grootste. https://stackoverflow.com/questions/7878622/can-we-use-binary-search-tree-to-simulate-heap-operation (genoemd door Yeo ).

  Eigenlijk is dit een beperking van hopen vergeleken met BSTs: de enige efficiënte zoekopdracht is die voor het grootste element.

Gemiddelde invoegen van binaire heap is O(1)

Bronnen:

• Papier: 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

Intuïtief argument:

• onderste boomniveaus hebben exponentieel meer elementen dan hoogste niveaus, dus nieuwe elementen zullen vrijwel zeker onderaan gaan
• heap insertion begint vanaf de onderkant , BST moet vanaf de bovenkant beginnen

In een binaire heap is het verhogen van de waarde bij een bepaalde index ook O(1) om dezelfde reden. Maar als u dat wilt doen, is het waarschijnlijk dat u een extra index up-to-date wilt houden over heap-bewerkingen https://stackoverflow.com/questions/17009056/how-to-implement-ologn-decrease-key-operation-for-min-heap-based-priority-queu bijv voor Dijkstra. Mogelijk zonder extra tijdskosten.

GCC C ++ standaard benchmark voor bibliotheekinvoer op echte hardware

Ik heb de C ++ std::set ( Rood-zwarte boom BST ) en std::priority_queue ( dynamic array heap ) insert om te zien of ik gelijk had over de invoegtijden, en dit is wat ik kreeg:

• benchmarkcode
• plot-script
• plotgegevens
• getest op Ubuntu 19.04, GCC 8.3.0 in een Lenovo ThinkPad P51-laptop met CPU: Intel Core i7-7820HQ CPU (4 cores / 8 threads , 2,90 GHz basis, 8 MB cache), RAM: 2x Samsung M471A2K43BB1-CRC (2x 16GiB, 2400 Mbps), SSD: Samsung MZVLB512HAJQ-000L7 (512 GB, 3.000 MB / s)

Dus duidelijk:

• heap insert t ime is in principe constant.

  We kunnen duidelijk de punten voor het wijzigen van de dynamische matrix zien. Aangezien we elke 10k inserts gemiddeld nemen om ook maar iets te kunnen zien boven systeemruis , zijn die pieken in feite ongeveer 10.000 keer groter dan getoond!

  De ingezoomde grafiek sluit in wezen alleen de array-resize-punten uit, en laat zien dat bijna alle inserts onder de 25 nanoseconden vallen.

• BST is logaritmisch. Alle invoegingen zijn veel langzamer dan de gemiddelde heap-invoeging.

• BST versus gedetailleerde hashmapanalyse op: https://stackoverflow.com/questions/18414579/what-data-structure-is-inside-stdmap-in-c/51945119#51945119

GCC C ++ standaard benchmark voor bibliotheekinvoeging op gem5

gem5 is een volledige systeemsimulator en biedt daarom een oneindig nauwkeurige klok met m5 dumpstats. Dus ik probeerde het te gebruiken om timings te schatten voor individuele inserts.

Interpretatie:

• heap is nog steeds constant, maar nu zien we in meer detail dat er een paar regels zijn, en elke hogere regel is schaarser .

  Dit moet overeenkomen met de latenties voor geheugentoegang die worden gedaan voor steeds hogere inserts.

• TODO Ik kan de BST niet echt volledig interpreteren, aangezien het ziet er niet zo logaritmisch en iets constanter uit.

  Met dit meer detail kunnen we echter ook een paar duidelijke regels zien, maar ik weet niet zeker wat ze vertegenwoordigen: ik zou verwachten dat de onderste regel dunner zijn, aangezien we boven en onder invoegen?

Benchmarking met deze Buildroot-setup op een aarch64 HPI CPU .

BST kan niet efficiënt worden geïmplementeerd op een array

Heap bewerkingen hoeven maar een enkele boomtak omhoog of omlaag te bellen, dus O(log(n)) worst case swaps, O(1) gemiddeld.

Om een BST gebalanceerd te houden, zijn boomrotaties nodig, waardoor het bovenste element kan worden vervangen door een ander, en zou de hele array moeten worden verplaatst (O(n)).

Heaps kunnen efficiënt worden geïmplementeerd op een array

Ouder- en onderliggende indexen kunnen worden berekend uit de huidige index zoals hier getoond .

Er zijn geen balanceringsoperaties zoals BST.

Min verwijderen is de meest verontrustende operatie omdat het moet van boven naar beneden zijn. Maar het kan altijd worden gedaan door een enkele tak van de heap naar beneden te “percoleren”, zoals hier wordt uitgelegd . Dit leidt tot een O (log (n)) worst case, aangezien de heap altijd goed uitgebalanceerd is.

Als je een enkel knooppunt invoegt voor elke knoop die je verwijdert, verlies je het voordeel van de asymptotische O (1) gemiddelde insertie die door de hoop wordt geleverd, aangezien de verwijdering zou domineren, en je kunt net zo goed een BST gebruiken. Dijkstra werkt de knooppunten echter meerdere keren bij voor elke verwijdering, dus het gaat goed.

Dynamische arrayheaps versus pointer treeheaps

Heaps kunnen efficiënt worden geïmplementeerd bovenop pointerhopen: https://stackoverflow.com/questions/19720438/is-it-possible-to-make-efficient-pointer-based-binary-heap-implementations

De dynamische array-implementatie is ruimtebesparend. Stel dat elk heap-element slechts een pointer bevat naar een struct:

• de tree-implementatie moet drie pointers voor elk element opslaan: parent, linker kind en rechter kind. Het geheugengebruik is dus altijd 4n (3 boomaanwijzers + 1 struct aanwijzer).

  Boom-BSTs zouden ook verdere afwegingsinformatie nodig hebben, bijv black-red-ness.

• de implementatie van de dynamische array kan de grootte 2n hebben net na een verdubbeling. Dus gemiddeld wordt het 1.5n.

Aan de andere kant heeft de tree heap een betere worst case insert, omdat het kopiëren van de ondersteunende dynamische array om zijn grootte te verdubbelen O(n) in het ergste geval nodig heeft, terwijl de boomhoop alleen nieuwe kleine toewijzingen voor elk knooppunt doet.

Toch array-verdubbeling wordt O(1) afgeschreven, dus het komt neer op een maximale latentie. Hier genoemd .

Filosofie

• BSTs behouden een globale eigenschap tussen een ouder en alle nakomelingen (links kleiner, rechts groter).

  Het bovenste knooppunt van een BST is het middelste element , die globale kennis vereist om te onderhouden (weten hoeveel kleinere en grotere elementen er zijn).

  Deze globale eigenschap is duurder om te onderhouden (log n invoegen), maar geeft krachtigere zoekopdrachten (log n zoeken) .

• Heaps onderhouden een lokale eigenschap tussen ouder en directe kinderen (ouder> kinderen).

  De belangrijkste noot van een hoop is het grote element, dat vereist alleen lokale kennis om te onderhouden (uw ouder kennen).

BST versus Heap versus Hashmap vergelijken:

• BST: kan ofwel redelijk zijn:

  • ongeordende set (een structuur die bepaalt of een element eerder is ingevoegd of niet). Maar hashmap heeft de neiging om beter te zijn vanwege O (1) geamortiseerde insert.
  • sorteermachine. Maar heap is daar over het algemeen beter in, en daarom is heapsort veel bekender dan boomsortering

• heap: is slechts een sorteermachine. Kan geen efficiënte ongeordende set zijn, omdat je alleen snel kunt controleren op het kleinste / grootste element.

• hash-map: kan alleen een ongeordende set zijn, geen efficiënte sorteermachine, omdat de hashing elke volgorde door elkaar haalt.

Dubbel gelinkte lijst

Een dubbel gelinkte lijst kan worden gezien als een subset van de hoop waar het eerste item de grootste prioriteit heeft, dus laten we ze hier ook vergelijken:

• insertion:
  • positie:
    • dubbel gelinkte lijst: het ingevoegde item moet het eerste of het laatste zijn, aangezien we alleen naar die elementen verwijzen.
    • binaire heap: het ingevoegde item kan in elke positie terechtkomen. Minder beperkend dan gelinkte lijst.
  • tijd:
    • dubbel gelinkte lijst: O(1) worst case omdat we verwijzingen naar de items hebben, en de update is heel eenvoudig
    • binaire heap: O(1) gemiddeld, dus slechter dan de gekoppelde lijst. Afweging voor met meer algemene invoegpositie.
• zoeken: O(n) voor beide

Een use case hiervoor is wanneer de sleutel van de heap de huidige tijdstempel is: in dat geval zullen nieuwe items altijd naar het begin van de lijst gaan. We kunnen dus zelfs het exacte tijdstempel helemaal vergeten en gewoon de positie in de lijst als prioriteit behouden.

Dit kan worden gebruikt om een LRU-cache te implementeren . Net als voor heap-applicaties zoals Dijkstra , wilt u een extra hashmap van de sleutel naar het corresponderende knooppunt van de lijst bewaren om te vinden welk knooppunt u snel wilt bijwerken .

Vergelijking van verschillende gebalanceerde BST

Hoewel de asymptotische invoeging en vind tijden voor alle gegevensstructuren die gewoonlijk worden geclassificeerd als gebalanceerde BSTs die ik tot nu toe heb gezien, is hetzelfde, verschillende BBSTs hebben verschillende afwegingen. Ik heb dit nog niet volledig bestudeerd, maar het zou goed zijn om samen te vatten deze afwegingen hier:

• Rood-zwarte boom . Lijkt de meest gebruikte BBST te zijn vanaf 2019, b.v. het is degene die wordt gebruikt door de GCC 8.3.0 C ++ -implementatie
• AVL-structuur . Lijkt wat evenwichtiger te zijn dan BST, dus het zou beter kunnen zijn voor zoeklatentie, ten koste van iets duurdere vondsten.Wiki vat samen: “AVL-bomen worden vaak vergeleken met rood-zwarte bomen omdat beide dezelfde reeks bewerkingen ondersteunen en [dezelfde] tijd kosten voor de basisbewerkingen. Voor opzoekintensieve toepassingen zijn AVL-bomen sneller dan rood-zwarte bomen, omdat ze zijn strikter in balans. Net als bij rood-zwarte bomen, zijn AVL-bomen in hoogte gebalanceerd. Beide zijn in het algemeen niet gebalanceerd of mu-gebalanceerd voor een mu < 1 / 2; dat wil zeggen, knooppunten tussen broers en zussen kunnen enorm verschillende aantallen nakomelingen hebben. “
• WAVL . Het originele artikel vermeldt de voordelen van die versie in termen van grenzen aan herbalancering en rotatiebewerkingen.

Zie ook

Vergelijkbare vraag over CS: Wat ' is het verschil tussen een binaire zoekboom en een binaire heap?

Reacties

• Goed antwoord . Veel voorkomende toepassingen van heap zijn mediaan, k min, top k elementen. Voor deze meest voorkomende bewerkingen verwijdert u min en invoegt u (meestal hebben we een kleine hoop met weinig pure invoegbewerkingen). Zo lijkt het in de praktijk, voor deze algoritmen presteert het niet beter dan BST.
• Uitzonderlijk antwoord !!! Door deque als onderliggende heap-structuur te gebruiken, kunt u de tijden voor het wijzigen van de grootte drastisch verminderen, hoewel het nog steeds O (n) in het ergste geval is, aangezien het een (kleinere) reeks aanwijzers moet herverdelen aan brokken.

Zowel binaire zoekbomen als binaire hopen zijn boomgebaseerde datastructuren.

Heaps vereisen dat de knooppunten voorrang hebben op hun kinderen. In een max heap moeten de kinderen van elk knooppunt kleiner zijn dan zichzelf. Dit is het tegenovergestelde voor een min heap:

Binaire zoekbomen (BST) volgen een specifieke volgorde (pre-order, in-order, post-order) tussen knooppunten op hetzelfde niveau. De boom moet worden gesorteerd, in tegenstelling tot hopen:

BST heeft een gemiddelde van $ O (\ log n) $ voor invoegen, verwijderen en zoeken.
Binaire Heaps hebben een gemiddelde $ O (1) $ voor findMin / findMax en $ O (\ log n) $ voor invoegen en verwijderen.

Opmerkingen

• @FrankW Extractie is $ O (\ log n) $, nee?

Bovenop de vorige antwoorden moet de heap de eigenschap heap-structuur hebben ; de boom moet vol zijn, en de onderste laag, die niet altijd vol kan zijn, moet helemaal van links naar rechts worden gevuld zonder hiaten.