Mikä on ' ero binäärisen hakupuun ja binäärisen kasan välillä?

Heap vain takaa, että ylemmän tason elementit ovat suurempia (max-kasa) tai pienempiä (min-kasa) kuin matalammat elementit, kun taas BST takaa järjestyksen (”vasemmalta” oikealle ”) . Jos haluat lajiteltuja elementtejä, valitse BST. by Dante ei ole nörtti

Kasa on parempi osoitteessa findMin / findMax (O ( 1)), kun taas BST on hyvä kaikissa löydöissä (O (logN)). Insert on O (logN) molemmille rakenteille. Jos välität vain findMin / findMaxista (esim. Prioriteettiin liittyvä), mene kasaan. Jos haluat kaikki lajiteltu, mene BST: n kanssa.

kirjoittanut xysun

Kommentit

• Mielestäni BST on parempi findMin & findMax pinoamisvirta .com / a / 27074221/764592
• Tämä on mielestäni vain komm väärinkäsityksestä. Binaaripuuta voidaan helposti muokata löytämään min ja max, kuten Yeo huomauttaa. Tämä on itse asiassa kasan rajoitus : tehokas vain -haku on minimi tai max. Kasan todellinen etu on O (1) keskimääräinen lisäys kun selitän: stackoverflow.com/a/29548834/895245
• tämän videon mukaan sinulla voi olla suurempia arvoja alemmalla tasolla, kunhan suurempi ei ole alemman jälkeläinen.
• Kasa lajitellaan juuresta lehteen ja BST lajitellaan vasemmalta oikealle.
• Entä jos haluan löytää mediaanin jatkuvana aikana ja poistaa mediaanin logaritmisessa ajassa? mihin tietorakenteeseen minun pitäisi mennä? toimiiko MinHeapin käyttöönotto? ehdottaa.

Yhteenveto

 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) 

Kaikki tämän taulukon keskimääräiset ajat ovat samat kuin pahin ajat paitsi Insert.

• *: kaikkialla tässä vastauksessa, BST == Tasapainoinen BST, koska epätasapainoinen imee asymptoottisesti
• **: käyttämällä tässä vastauksessa selitettyä triviaalia muunnosta.
• ***: log(n) osoitinpuun kasalle, n dynaamista matriisikokoa varten

Binaarisen kasan edut BST: n yli

• keskimääräinen lisäys aika binäärikasaan on O(1), BST on O(log(n)). Tämä on kasojen tappajaominaisuus.

  On myös muita kasoja, jotka saavuttavat O(1) amortizoitu (vahvempi) kuten Fibonacci-kasa , ja jopa pahimmassa tapauksessa, kuten Brodal-jono , vaikka ne eivät välttämättä ole käytännöllisiä asymptoottisen suorituskyvyn takia: https://stackoverflow.com/questions/30782636/are-fibonacci-heaps-or-brodal-queues-used-in-practice-anywhere

• binaariset kasat voidaan toteuttaa tehokkaasti joko dynaamisten taulukoiden tai osoitinpohjaisten puiden päällä, vain BST osoitinpohjaiset puut. Joten kasaan voimme valita tilaa tehokkaamman taulukon toteutuksen, jos meillä on varaa satunnaisiin koon viiveisiin.

• binaarisen kasan luominen on O(n) pahin tapaus , O(n log(n)) BST: lle.

BST: n etu binaariseen kasaan verrattuna

• mielivaltaisten elementtien haku on O(log(n)). Tämä on BST-tiedostojen tappajaominaisuus.

  Kasaan se on O(n) yleensä lukuun ottamatta suurinta elementtiä, joka on O(1).

”kasan” väärä etu BST: hen nähden

• kasa on O(1) löytääksesi enimmäisarvon, BST O(log(n)).

  Tämä on yleinen väärinkäsitys, koska on triviaalia muuttaa BST: tä suurimman elementin seuraamiseksi ja päivittää se aina, kun kyseistä elementtiä voidaan muuttaa: kun lisätään suurempi vaihto, poistettaessa löydetään toiseksi suurin. https://stackoverflow.com/questions/7878622/can-we-use-binary-search-tree-to-simulate-heap-operation (Yeo mainitsi ).

  Itse asiassa tämä on kasojen rajoitus verrattuna BST: iin: ainoa tehokas haku on suurin elementti.

Binaarisen kasan keskimääräinen lisäys on O(1)

Lähteet:

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

Intuitiivinen argumentti:

• alemman puun tasoilla on eksponentiaalisesti enemmän elementtejä kuin ylimmillä tasoilla, joten uudet elementit menevät melkein varmasti alaosaan
• kasan lisäys alkaa alhaalta , BST on aloitettava ylhäältä

Binaarisessa kasassa arvon lisääminen tietyllä indeksillä on myös O(1) samasta syystä. Mutta jos haluat tehdä sen, on todennäköistä, että haluat pitää ylimääräisen hakemiston ajan tasalla kasaoperaatioista https://stackoverflow.com/questions/17009056/how-to-implement-ologn-decrease-key-operation-for-min-heap-based-priority-queu esim joukkueelle Dijkstra. Mahdollinen ilman ylimääräisiä aikakustannuksia.

GCC: n C ++ -standardikirjaston lisäys vertailuarvo todelliselle laitteistolle

Vertailin C ++ std::set ( punamusta puu BST ) ja std::priority_queue ( dynaaminen matriisipino ) -lisälaite nähdäksesi, olenko oikeassa lisäaikojen suhteen, ja tämän sain:

• vertailukoodi
• juonetiedosto
• piirtotiedot
• testattu Ubuntu 19.04, GCC 8.3.0: lla Lenovo ThinkPad P51 -kannettavalla, jossa on CPU: Intel Core i7-7820HQ CPU (4 ydintä / 8 säiettä , 2,90 GHz: n kanta, 8 Mt: n välimuisti), RAM-muistia: 2x Samsung M471A2K43BB1-CRC (2x 16GiB, 2400 Mbps), SSD: Samsung MZVLB512HAJQ-000L7 (512 Gt, 3000 MB / s)

Niin selkeästi:

• kasan lisäys t ime on pohjimmiltaan vakio.

  Voimme selvästi nähdä dynaamisen matriisin koon pisteet. Koska keskimäärin 10 k: n insertit pystytään näkemään mitään järjestelmän melun yläpuolella , nämä huiput ovat itse asiassa noin 10 000 kertaa suurempia kuin on esitetty!

  Suurennettu kaavio sulkee pois lähinnä vain matriisin kokopisteet ja osoittaa, että melkein kaikki lisäykset jäävät alle 25 nanosekunnin päähän.

• BST on logaritminen. Kaikki lisäykset ovat paljon hitaampia kuin keskimääräinen kasan lisäys.

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

GCC C ++ -sovelluksen vakiokirjasto lisää vertailuarvon gem5-tiedostoon

gem5 on täysi järjestelmäsimulaattori, ja tarjoaa siten äärettömän tarkan kellon, jossa on m5 dumpstats. Joten yritin käyttää sitä arvioimaan yksittäisten inserttien ajoituksia.

Tulkinta:

• kasa on edelleen vakio, mutta nyt näemme tarkemmin, että rivejä on muutama, ja jokainen ylempi rivi on harvempi .

  Tämän on vastattava muistin käyttöviiveitä, jotka tehdään yhä korkeammille lisäyksille.

• TODO En voi tulkita BST: tä täysin sellaisenaan ei näytä niin logaritmiselta ja jonkin verran tasaisemmalta.

  Tällä yksityiskohdalla voimme kuitenkin nähdä myös muutaman erillisen rivin, mutta en ole varma, mitä ne edustavat: Odotan, että alarivin olla ohuempi, koska asetamme yläosan?

Verrataanko tähän koontisivun kokoonpanoon aarch64 HPI-suoritin .

BST ei voida toteuttaa tehokkaasti taulukossa

Kasa toimintojen on kuplittava vain ylös tai alas yksittäinen puun oksa, joten O(log(n)) pahimmassa tapauksessa vaihdetaan, O(1) keskiarvo.

BST: n pitäminen tasapainossa vaatii puukierroksia, jotka voivat vaihtaa ylimmän elementin toiseen, ja vaatisi koko matriisin siirtämisen ympäri (O(n)).

Joukot voidaan tehokkaasti toteuttaa taulukossa

Vanhempien ja lasten indeksit voidaan laskea nykyisestä hakemistosta kuten tässä on esitetty .

BST: n kaltaisia tasapainotusoperaatioita ei ole.

Minimin poistaminen on huolestuttavin toiminto, koska se täytyy olla ylhäältä alas. Mutta se voidaan aina tehdä ”suodattamalla alas” yksi kasan haara kuten täällä selitetään . Tämä johtaa pahimpaan O (log (n)) -tapaukseen, koska kasa on aina hyvin tasapainossa.

Jos lisäät yhden solmun jokaiselle poistamallesi, menetät asymptoottisen edun O (1) keskimääräinen lisäys, jonka kasat tarjoavat, koska poisto dominoi, ja voit yhtä hyvin käyttää BST: tä. Dijkstra kuitenkin päivittää solmut useita kertoja kustakin poistosta, joten olemme kunnossa.

Dynaamiset matriisihondit vs. osoitinpuupohjat

Kasat voidaan toteuttaa tehokkaasti osoittimien päällä: https://stackoverflow.com/questions/19720438/is-it-possible-to-make-efficient-pointer-based-binary-heap-implementations

Dynaaminen taulukon toteutus on tilaa säästävämpi. Oletetaan, että jokainen kasan elementti sisältää vain osoittimen struct:

• puupohjan toteutuksessa on tallennettava kolme osoitinta kullekin elementille: parent, vasen lapsi ja oikea lapsi. Joten muistin käyttö on aina 4n (3 puun osoitinta + 1 struct osoitin).

  Myös puun BST: t tarvitsevat lisää tasapainotietoja, esim musta-punainen-ei.

• dynaamisen matriisin toteutus voi olla kooltaan 2n heti tuplauksen jälkeen. Joten keskimäärin se tulee olemaan 1.5n.

Toisaalta puun kasalla on parempi huonompi tapa, koska dynaamisen taustalevyn kopioiminen sen koon kaksinkertaistamiseksi vaatii O(n) pahimman tapauksen, kun taas puun kasa tekee vain uusia pieniä allokaatioita kullekin solmulle.

Tausta taulukon kaksinkertaistaminen on O(1) amortisoitu, joten se tulee maksimi latenssiarvioon. Mainittu tässä .

Filosofia

• BST: t ylläpitävät globaalia ominaisuutta vanhemman ja kaikkien jälkeläisten välillä (vasemmalla pienempi, oikealla isompi).

  BST: n yläsolmu on keskielementti , jonka ylläpito vaatii globaalia tietoa (tietäen kuinka monta pienempää ja suurempaa elementtiä on).

  Tätä globaalia ominaisuutta on kalliimpi ylläpitää (log n insert), mutta antaa tehokkaampia hakuja (log n search) .

• Joukot ylläpitävät paikallista omaisuutta vanhempien ja suorien lasten (vanhempi> lapset) välillä.

  Kasan päätuote on iso elementti, joka vaatii vain paikallista tietämystä ylläpitää (tuntemalla vanhempasi).

Vertaamalla BST vs Heap vs Hashmap:

• BST: voi olla joko kohtuullinen:

  • järjestämätön joukko (rakenne, joka määrittää, onko elementti lisätty aiemmin vai ei). Mutta hashmap on yleensä parempi O (1) amortisoidun insertin ansiosta.
  • lajittelukone. Mutta kasa on yleensä siinä parempi, minkä vuoksi heapsort tunnetaan paljon laajemmin kuin puulajittelu

• kasa: on vain lajittelukone. Ei voi olla tehokas järjestämätön joukko, koska voit tarkistaa vain pienimmän / suurimman elementin nopeasti.

• hash-kartta: voi olla vain järjestämätön sarja, ei tehokas lajittelukone, koska hajautus sekoittaa kaikki järjestykset.

Kaksinkertaisesti linkitetty luettelo

Kaksinkertaisesti linkitetyn luettelon voidaan nähdä kasan alijoukkona, jossa ensimmäisellä kohteella on suurin prioriteetti, joten verrataan niitä myös tähän:

• lisäys:
  • sijainti:
    • kaksoislinkitetty luettelo: lisätyn kohteen on oltava joko ensimmäinen tai viimeinen, koska meillä on vain viitteitä näihin elementteihin.
    • binaarinen kasa: lisätty kohde voi päätyä mihin tahansa sijaintiin. Vähemmän rajoittava kuin linkitetty luettelo.
  • aika:
    • kaksoislinkitetty luettelo: O(1) pahin tapaus, koska meillä on viitteitä kohteisiin, ja päivitys on todella yksinkertaista
    • binaarinen kasa: O(1) keskiarvo, mikä on huonompi kuin linkitetty luettelo. jolla on yleisempi lisäysasento.
• etsi: O(n) molemmille

Tällöin käyttötapa on, kun kasan avain on nykyinen aikaleima: tällöin uudet merkinnät menevät aina luettelon alkuun. Joten voimme jopa unohtaa tarkan aikaleiman kokonaan ja pitää vain luettelon sijainti ensisijaisena.

Tätä voidaan käyttää LRU-välimuistin toteuttamiseen. . Aivan kuten kasan sovelluksille, kuten Dijkstra , kannattaa pitää ylimääräinen hashmap avaimesta luettelon vastaavaan solmuun, jotta löydettäisiin päivitettävä solmu nopeasti .

Erilaisten tasapainotettujen BST-tietojen vertailu

Vaikka asymptoottinen lisäys ja haku kertaa kaikilla tietorakenteilla, jotka luokitellaan yleisesti ”tasapainotetuiksi BST: ksi”, jotka olen tähän mennessä nähnyt, ovat samat, erilaisilla BBST: llä on erilaiset kompromissit. En ole vielä tutkinut tätä täysin, mutta olisi hyvä tehdä yhteenveto nämä kompromissit täällä:

• Punainen-musta puu . Näyttää olevan yleisimmin käytetty BBST vuodesta 2019 lähtien, esim. sitä käyttää GCC 8.3.0 C ++ -toteutus
• AVL-puu . Näyttää olevan hieman tasapainoisempi kuin BST, joten se voi olla parempi löytää viive, hieman kalliimpien löytöjen kustannuksella.Wiki tiivistää: ”AVL-puita verrataan usein puna-mustiin puihin, koska molemmat tukevat samoja toimintoja ja vievät [saman] ajan perustoimintoihin. Haun vaativissa sovelluksissa AVL-puut ovat nopeammin kuin punaiset-mustat puut, koska ne ovat tarkemmin tasapainossa. AVL-puut ovat tasapainossa puna-mustien puiden tavoin. Molemmat eivät yleensä ole painon tai tasapainon mukaisia minkään mu < 1 / 2; ts. Sisarus-solmuilla voi olla hyvin erilainen määrä jälkeläisiä. ”
• WAVL . alkuperäisessä artikkelissa mainitaan kyseisen version edut tasapainotus- ja kiertotoimintojen rajojen suhteen.

Katso myös

Samanlainen kysymys CS: ssä: Mikä ' s binäärisen hakupuun ja binäärisen kasan välinen ero?

Kommentit

• Hyvä vastaus . Kasan yleinen käyttö on mediaani, k min, ylin k elementti. Näitä yleisimpiä toimintoja varten poista min ja lisää sitten (yleensä meillä on pieni kasa, jossa on vain vähän puhdasta lisäystä). Joten näyttää käytännössä, näille algoritmeille se ei ylitä BST: tä.
• Poikkeuksellinen vastaus !!! Käyttämällä dequea taustalla olevana kasan rakenteena voit lyhentää kokoaikoja dramaattisesti, vaikka se onkin O (n) pahin tapaus, koska sen on kohdennettava (pienempi) joukko osoittimia paloiksi.

Sekä binaariset hakupuut että binaariset kasat ovat puupohjaisia tietorakenteita.

Joukot edellyttävät, että solmuilla on etusija lapsiaan kohtaan. Suurimmassa kasassa jokaisen solmun lasten on oltava pienempiä kuin itsensä. Tämä on päinvastoin min-kasalle:

Binaarihakupuut (BST) seuraavat tiettyä järjestystä (ennakkotilaus, järjestys, jälkitilaus) sisarussolmujen välillä. Puun on oltava lajiteltava, toisin kuin kasat:

BST: n keskiarvo on $ O (\ log n) $ lisäystä, poistamista ja hakua varten.
Binaarikasoissa on keskimäärin $ O (1) $ for findMin / findMax ja $ O (\ log n) $ lisäykseen ja poistamiseen.

Kommentit

• @FrankW Pura on $ O (\ log n) $, ei?

Edellisten vastausten lisäksi kasalla on oltava kasan rakenne-ominaisuus ; puun on oltava täynnä, ja alimman kerroksen, joka ei aina voi olla täynnä, on täytettävä vasemmasta vasemmalle oikealle ilman aukkoja.