Mi a ' különbség a bináris keresőfa és a bináris halom között?

A halom csak azt garantálja, hogy a magasabb szintű elemek nagyobbak (max-halom esetén) vagy kisebbek (min-halomnál), mint az alacsonyabb szinteken lévő elemek, míg a BST a rendet (balról jobbra) jobbra garantálja. . Ha rendezett elemeket szeretne, akkor lépjen a BST-re. by Dante nem geek

A halom jobb a findMin / findMax (O ( 1)), míg a BST minden találatnál jó (O (logN)). Az Insert O (logN) mindkét struktúrához. Ha csak a findMin / findMax érdekli (pl. Prioritással kapcsolatos), halmozzon halmot. minden rendezve, járjon a BST-szel.

írta: xysun

Megjegyzések

• szerintem a BST jobb a findMin & findMax stackoverflow-ban .com / a / 27074221/764592
• szerintem ez csak egy komm a tévhitről. A bináris fa könnyen módosítható, hogy megtalálja a min és max értékeket, amire Yeo mutat. Ez valójában a halom korlátozása : a csak hatékony találat min vagy max. A kupac valódi előnye az O (1) átlagos beszúrás , amint elmagyarázom: stackoverflow.com/a/29548834/895245
• ez a videó szerint alacsonyabb szinten nagyobb értékeket adhat meg, amennyiben a nagyobbik nem az alsó leszármazottja.
• A halom gyökérről levélre, a BST pedig balról jobbra van rendezve.
• Mi van, ha állandó mediánban szeretném megtalálni a mediánt, és logaritmikus időben eltávolítani a mediánt? melyik adatstruktúrára kell mennem? működik a MinHeap megvalósítása? kérjük, javasoljon.

Összegzés

 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) 

A táblázat összes átlagos ideje megegyezik a legrosszabb időkkel, kivéve az Insert elemet.

• *: ebben a válaszban mindenhol BST == Kiegyensúlyozott BST, mivel a kiegyensúlyozatlan aszimptotikusan szar
• **: a válaszban kifejtett triviális módosítás használata
• ***: log(n) a mutatófa halomhoz, n dinamikus tömbhalomba

A bináris halom előnyei a BST-vel szemben

• A bináris halomba történő átlagos beszúrási idő O(1), a BST esetében O(log(n)). Ez az a halmok gyilkos jellemzője.

  Vannak más halmok is, amelyek elérik a O(1) amortizálódott (erősebb), mint a Fibonacci kupac , és még a legrosszabb esetben is, például a Brodal várólista , bár előfordulhat, hogy nem aszimptotikus teljesítményük miatt praktikusak: https://stackoverflow.com/questions/30782636/are-fibonacci-heaps-or-brodal-queues-used-in-practice-anywhere

• a bináris halmokat hatékonyan lehet megvalósítani akár dinamikus tömbök , akár mutatóalapú fák tetején, csak BST mutató alapú fák. Tehát a kupac számára választhatjuk a helytakarékos tömb megvalósítást, ha megengedhetjük magunknak az időnkénti átméretezési késleltetéseket.

• bináris halom létrehozása O(n) legrosszabb eset , O(n log(n)) a BST esetében.

A BST előnye a bináris halommal szemben

• tetszőleges elemek keresése O(log(n)). Ez az a BST-k gyilkos funkciója.

  Halom esetében ez O(n) általában, kivéve a legnagyobb elemet, amely O(1).

“Hamis” előnye a kupacnak a BST-vel szemben

• a halom O(1) a max, BST megtalálásához O(log(n)).

  Ez Ez egy általános tévhit, mert triviális egy BST módosítása a legnagyobb elem nyomon követése érdekében, és mindig frissíteni kell, amikor az elem megváltoztatható: egy nagyobb swap beillesztésekor, eltávolításkor megtalálja a második legnagyobbat. https://stackoverflow.com/questions/7878622/can-we-use-binary-search-tree-to-simulate-heap-operation ( említette Yeo ).

  Valójában ez a halmok korlátozása a BST-ekhez képest: a csak hatékony keresés a legnagyobb elemre.

A bináris halom átlagos betétje O(1)

Források:

• Papír: http://i.stanford.edu/pub/cstr/reports/cs/tr/74/460/CS-TR-74-460.pdf
• WSU diák: http://www.eecs.wsu.edu/~holder/courses/CptS223/spr09/slides/heaps.pdf

Intuitív érvelés:

• az alsó fa szintek exponenciálisan több elemet tartalmaznak, mint a legfelső szintek, így az új elemek szinte biztosan alul fognak menni
• halom beszúrás alulról indul , a BST-nek felülről kell indulnia

Egy bináris halomban az érték növelése egy adott indexnél is O(1) ugyanezen okból. De ha ezt meg akarja tenni, akkor valószínűleg egy extra indexet naprakészen szeretne tartani a halomműveletekről https://stackoverflow.com/questions/17009056/how-to-implement-ologn-decrease-key-operation-for-min-heap-based-priority-queu pl Dijkstra számára. Különleges időköltség nélkül lehetséges.

A GCC C ++ szabványos könyvtárbeillesztési pontja valódi hardveren

Összehasonlítottam a C ++ std::set ( Vörös-fekete fa BST ) és std::priority_queue ( dinamikus tömbhalom ) beszúrás, hogy lássam, igazam volt-e a beszúrási időkhöz képest, és ezt kaptam:

• benchmark kód
• plot script
• ábra adatai
• Ubuntu 19.04, GCC 8.3.0 verzión tesztelve egy Lenovo ThinkPad P51 laptopon CPU-val: Intel Core i7-7820HQ CPU (4 mag / 8 szál , 2,90 GHz-es alap, 8 MB gyorsítótár), RAM: 2x Samsung M471A2K43BB1-CRC (2x 16GiB, 2400 Mbps), SSD: Samsung MZVLB512HAJQ-000L7 (512GB, 3000 MB / s)

Olyan egyértelműen:

• kupacbetét t Az ime alapvetően állandó.

  Világosan láthatjuk a dinamikus tömb átméretezési pontjait. Mivel minden 10 ezer betétet átlagolunk, hogy a rendszerzaj felett egyáltalán bármit is láthassunk , ezek a csúcsok valójában körülbelül 10 000-szer nagyobbak, mint az ábrán látható!

  A nagyított grafikon lényegében csak a tömb átméretezési pontjait zárja ki, és azt mutatja, hogy szinte az összes beszúrás 25 nanoszekundum alá esik.

• A BST logaritmikus. Minden betét sokkal lassabb, mint az átlagos kupacbetét.

• BST vs hashmap részletes elemzés: https://stackoverflow.com/questions/18414579/what-data-structure-is-inside-stdmap-in-c/51945119#51945119

GCC C ++ szabványos könyvtár beszúrási referenciaérték a gem5-en

gem5 egy teljes rendszerszimulátor, ezért végtelenül pontos órát biztosít a m5 dumpstats. Ezért megpróbáltam becsülni az egyes betétek időzítését.

Értelmezés:

• a kupac még mindig állandó, de most részletesebben látjuk, hogy van néhány sor, és minden magasabb sor ritkább .

  Ennek meg kell felelnie annak a memóriaelérési késleltetésnek, amelyet magasabb és magasabb betétek esetén végeznek.

• A TODO nem igazán tudom értelmezni a BST-t úgy, ahogyan nem tűnik annyira logaritmikusnak és valamivel állandóbbnak.

  Ezzel a nagyobb részletességgel láthatunk néhány különálló sort is, de nem vagyok biztos abban, hogy mit képviselnek: azt várnám, hogy az alsó sor legyél vékonyabb, mivel a felső alját illesztjük be?

Ezzel az Buildroot beállítással egy ararch64 HPI CPU .

A BST nem valósítható meg hatékonyan egy tömbön

Halom a műveleteknek csak egyetlen faágat kell felfelé vagy lefelé buborékolniuk, tehát O(log(n)) legrosszabb esetben felcserélnek, O(1) átlagot.

A BST kiegyensúlyozott állapotának megőrzése fát igényel, ami megváltoztathatja a legfelső elemet egy másikra, és a teljes tömb mozgatását igényelné (O(n)).

A halmok hatékonyan implementálhatók egy tömbön

A szülők és a gyermekek indexei kiszámíthatók az aktuális indexből az itt látható módon .

Nincsenek olyan kiegyensúlyozó műveletek, mint a BST.

A min törlése a legaggasztóbb művelet, mivel felülről lefelé kell lennie. De ez mindig megtehető a halom egyetlen ágának “leszivárgásával” , ahogyan itt kifejtjük . Ez O (log (n)) legrosszabb esethez vezet, mivel a kupac mindig jól kiegyensúlyozott.

Ha minden csomóponthoz egyetlen csomópontot illeszt be, akkor elveszíti az aszimptotikus előnyeit Az O (1) átlagos betét, amelyet a halmok adnak, mivel a törlés dominál, és Ön is használhat BST-t. Dijkstra azonban többször is frissíti a csomópontokat minden eltávolításhoz, így jól vagyunk.

Dinamikus tömbhalmok vs mutatófa halmok

A halmok hatékonyan megvalósíthatók a mutatóhalmok tetején: https://stackoverflow.com/questions/19720438/is-it-possible-to-make-efficient-pointer-based-binary-heap-implementations

A dinamikus tömb megvalósítása helytakarékos. Tegyük fel, hogy minden kupac elem csak egy struct mutatót tartalmaz:

• a fa implementációnak három mutatót kell tárolnia minden elemhez: szülő, bal gyermek és jobb gyermek. Tehát a memóriahasználat mindig 4n (3 fa mutató + 1 struct mutató).

  A fa BST-k szintén további kiegyensúlyozó információkra van szükségük, pl fekete-piros-nesz.

• a dinamikus tömb megvalósítása 2n méretű lehet, közvetlenül duplázás után. Tehát átlagosan 1.5n lesz.

Másrészt a fa halomnak jobb a legrosszabb betétje, mert a dinamikus támogató tömb másolása a duplájára a O(n) legrosszabb esetet veszi igénybe, míg a fa halom csak új kis kiosztásokat végez minden csomópontnál.

Ennek ellenére a háttér a tömb duplázása O(1) amortizálódik, tehát maximális késleltetési megfontolásnak számít. Itt megemlítve .

Filozófia

• A BST-k globális tulajdonságot tartanak fenn egy szülő és az összes leszármazott között (balra kisebb, jobbra nagyobb).

  A BST felső csomópontja a középső elem , amelynek fenntartásához globális tudásra van szükség (annak ismerete, hogy hány kisebb és nagyobb elem van).

  Ez a globális tulajdonság fenntartása drágább (log n insert), de erőteljesebb kereséseket ad (log n search) .

• A kupacok helyi tulajdonságot tartanak fenn a szülő és a közvetlen gyermekek (szülő> gyermekek) között.

  A kupac fő hangja a nagy elem, amely csak a helyismeretet igényli a fenntartása (a szülő ismerete).

A BST vs Heap vs Hashmap összehasonlítása:

• BST: vagy ésszerű lehet:

  • rendezetlen halmaz (olyan struktúra, amely meghatározza, hogy egy elemet korábban beillesztettek-e vagy sem). De a hashmap általában jobb az O (1) amortizált betét miatt.
  • válogatógép. A halom azonban általában jobb ebben, ezért a heapsort sokkal szélesebb körben ismert, mint a fa rendezése

• kupac: csak válogató gép. Nem lehet hatékony rendezetlen készlet, mert csak a legkisebb / legnagyobb elemet ellenőrizheti gyorsan.

• hash map: csak rendezetlen halmaz lehet, nem hatékony válogató gép, mert a kivonat keveri az esetleges sorrendeket.

Kétszer linkelt lista

A kétszeresen összekapcsolt lista a halom azon részhalmazának tekinthető, ahol az első elemnek van a legnagyobb prioritása, ezért hasonlítsuk össze őket itt is:

• beillesztés:
  • pozíció:
    • duplán linkelt lista: a beillesztett elemnek vagy az elsőnek, vagy az utolsónak kell lennie, mivel csak ezekre az elemekre mutatunk mutatókat. bármilyen helyzetbe kerülhet. Kevésbé korlátozó, mint a linkelt lista.
  • idő:
    • kettős linkelésű lista: O(1) legrosszabb esetben, mivel vannak mutatóink az elemekre, és a frissítés nagyon egyszerű
    • bináris kupac: O(1) átlag, tehát rosszabb, mint a linkelt lista. általánosabb beszúrási pozícióval rendelkezik.
• keresés: O(n) mindkettőhöz

Ilyen esetben a halom kulcsa az aktuális időbélyeg: ebben az esetben az új bejegyzések mindig a lista elejére kerülnek. Így akár a pontos időbélyegzőt is teljesen elfelejthetjük, és csak a listán lévő pozíciót tartjuk prioritásként.

Ez egy LRU gyorsítótár megvalósításához használható. . Csakúgy, mint az olyan halom alkalmazásoknál, mint a Dijkstra , itt is meg kell őriznie egy további hashmap-ot a kulcstól a lista megfelelő csomópontjáig, hogy megtalálja a gyorsan frissítendő csomópontot. .

Különböző kiegyensúlyozott BST összehasonlítása

Bár az aszimptotikus beszúrás és megtalálás az összes olyan adatstruktúra esetében, amelyet általában “kiegyensúlyozott BST-ként” minősítenek, és amelyeket eddig láttam, a különböző BBST-k eltérő kompromisszumokkal rendelkeznek. Ezt még nem tanulmányoztam teljes mértékben, de jó lenne összefoglalni ezek a kompromisszumok itt:

• Vörös-fekete fa . Úgy tűnik, hogy 2019-től a leggyakrabban használt BBST, pl. ezt használja a GCC 8.3.0 C ++ implementációja
• AVL fa . Úgy tűnik, hogy kissé kiegyensúlyozottabb, mint a BST, ezért jobb lehet a késleltetés megtalálása, valamivel drágább leletek árán.A Wiki összefoglalja: “Az AVL fákat gyakran hasonlítják össze a vörös-fekete fákkal, mert mindkettő ugyanazt a műveletsort támogatja, és [ugyanazt] időt veszi igénybe az alapműveleteknél. A keresésigényes alkalmazásoknál az AVL fák gyorsabbak, mint a vörös-fekete fák, mert szigorúbban kiegyensúlyozottak. A vörös – fekete fákhoz hasonlóan az AVL fák magasságkiegyensúlyozottak. Mindkettő általában nem súly- és mu-kiegyensúlyozott semmilyen mu < 1 / 2; vagyis a testvér csomópontok rendkívül eltérő számú utódot számlálhatnak. “
• WAVL . Az eredeti cikk megemlíti ennek a változatnak az előnyeit a kiegyensúlyozási és forgatási műveletek korlátai tekintetében.

Lásd még:

Hasonló kérdés a CS-n: Mi ' s a különbség a bináris keresőfa és a bináris halom között?

Megjegyzések

• Remek válasz . A halom gyakori alkalmazása: medián, k min, felső k elem. Ehhez a leggyakoribb művelethez távolítsa el a min-t, majd helyezze be (általában van egy kis kupacunk, kevés tiszta betétművelettel). Úgy tűnik tehát, mint a gyakorlatban, ezeknél az algoritmusoknál nem haladja meg a BST-t.
• Kivételes válasz !!! Ha a deque-et halom struktúraként használjuk, drámai módon csökkentheti az átméretezési időket, bár ez még mindig O (n) legrosszabb eset, mivel újra (kisebb) mutató tömböt kell átcsoportosítania darabokra.

Mind a bináris keresési fák , mind a bináris halmok faalapú adatszerkezetek.

A halmok megkövetelik, hogy a csomópontok prioritást élvezzenek gyermekeikkel szemben. Max. Kupacban minden csomópont gyermekének kisebbnek kell lennie, mint ő maga. Ez fordított ellentétes egy min kupac esetében:

A bináris keresési fák (BST) meghatározott sorrendet követnek (előrendelés, sorrend, utólagos sorrend) a testvér csomópontok között. A fának sorrendje a halmokkal ellentétben:

A BST átlaga $ O (\ log n) $ a beszúráshoz, törléshez és kereséshez.
A bináris halmok átlagos $ O (1) $ értékűek a findMin / findMax és $ O (\ log n) $ beszúráshoz és törléshez.

Megjegyzések

• A @FrankW kibontása $ O (\ log n) $, nem?

Az előző válaszok mellett a kupacnak rendelkeznie kell a kupac struktúra tulajdonsággal ; a fának teljesnek kell lennie, és a legalsó réteget, amely nem mindig lehet teljes, balról jobbra kell kitölteni, hézagok nélkül.