Jaký je ' rozdíl mezi binárním vyhledávacím stromem a binární hromadou?

Halda pouze zaručuje, že prvky na vyšších úrovních jsou větší (pro max. hromadu) nebo menší (pro min. hromadu) než prvky na nižších úrovních, zatímco BST zaručuje pořadí (od „zleva“ po „doprava“) . Pokud chcete seřazené prvky, použijte BST. od Dante není geek

Halda je lepší v findMin / findMax (O ( 1)), zatímco BST je dobrý ve všech nálezech (O (logN)). Vložit je O (logN) pro obě struktury. Pokud vám záleží jen na findMin / findMax (např. Související s prioritou), jděte s hromadou. Pokud chcete vše seřazeno, přejděte na BST.

od xysun

Komentáře

• Myslím, že BST je lepší v findMin & findMax stackoverflow .com / a / 27074221/764592
• Myslím, že je to jen komunikace o mylné představě. Binární strom lze snadno upravit tak, aby našel min a max, jak ukazuje Yeo. Toto je vlastně omezení hromady: pouze efektivní hledání je min. Nebo max. Skutečnou výhodou haldy je O (1) průměrná vložka , jak vysvětluji: stackoverflow.com/a/29548834/895245
• Podle tohoto videa můžete mít vyšší hodnoty na nižší úrovni, pokud větší není potomkem nižší.
• Halda je řazena od kořene k listu a BST je řazena zleva doprava.
• co když chci najít medián v konstantním čase a odstranit medián v logaritmickém čase? po jaké datové struktuře bych měl jít? bude implementace MinHeap fungovat? prosím navrhněte.

Shrnutí

 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) 

Všechny průměrné časy v této tabulce jsou stejné jako jejich nejhorší časy kromě přílohy.

• *: všude v této odpovědi BST == Balanced BST, protože nevyvážený saje asymptoticky
• **: použití triviální úpravy vysvětlené v této odpovědi
• ***: log(n) pro haldu stromu ukazatele, n pro haldu dynamického pole

Výhody binární haldy oproti BST

• průměrná doba vložení do binární haldy je O(1), pro BST je O(log(n)). Toto je zabijácká funkce hromad.

  Existují i další hromady, které dosahují O(1) amortizované (silnější) jako halda Fibonacci , a v nejhorším případě jako Brodal fronta , i když nemusí být praktické kvůli neasyymotickému výkonu: https://stackoverflow.com/questions/30782636/are-fibonacci-heaps-or-brodal-queues-used-in-practice-anywhere

• binární hromady lze efektivně implementovat buď na dynamických polích nebo na stromech založených na ukazatelích, pouze BST stromy založené na ukazatelích. Takže pro haldu si můžeme vybrat prostorově efektivnější implementaci pole, pokud si můžeme dovolit příležitostné latence změny velikosti.

• vytvoření binární haldy je O(n) nejhorší případ , O(n log(n)) pro BST.

Výhoda BST oproti binární haldě

• vyhledávání libovolných prvků je O(log(n)). Toto je zabijácká funkce BST.

  U haldy je to O(n) obecně, s výjimkou největšího prvku, kterým je O(1).

„Falešná“ výhoda haldy oproti BST

• halda je O(1) k vyhledání maxima, BST O(log(n)).

  je běžná mylná představa, protože je triviální upravit BST, aby bylo možné sledovat největší prvek, a aktualizovat jej, kdykoli lze tento prvek změnit: při vložení většího swapu, při odstranění najděte druhý největší. https://stackoverflow.com/questions/7878622/can-we-use-binary-search-tree-to-simulate-heap-operation (uvedeno společností Yeo ).

  Ve skutečnosti se jedná o omezení hromad v porovnání s BST: pouze efektivní vyhledávání je hledání největšího prvku.

Průměrná binární halda je O(1)

Zdroje:

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

Intuitivní argument:

• dolní úrovně stromu mají exponenciálně více prvků než nejvyšší úrovně, takže je téměř jisté, že nové prvky budou umístěny dole
• vkládání haldy začíná zdola , BST musí začínat shora

V binární haldě je zvýšení hodnoty v daném indexu také O(1) ze stejného důvodu. Pokud to ale chcete udělat, je pravděpodobné, že budete chtít udržovat aktuální index o operacích haldy https://stackoverflow.com/questions/17009056/how-to-implement-ologn-decrease-key-operation-for-min-heap-based-priority-queu např pro Dijkstra. Možné bez dalších časových nákladů.

Standard GCC C ++ standardní měřítko pro vložení na skutečný hardware

Porovnal jsem C ++ std::set ( červeno-černý strom BST ) a std::priority_queue ( halda dynamického pole ) vložte, abyste zjistili, zda jsem měl pravdu ohledně časů vložení, a toto mám:

• srovnávací kód
• vykreslovací skript
• vykreslování dat
• testováno na Ubuntu 19.04, GCC 8.3.0 v notebooku Lenovo ThinkPad P51 s CPU: CPU Intel Core i7-7820HQ (4 jádra / 8 vláken , 2,90 GHz základna, 8 MB mezipaměti), RAM: 2x Samsung M471A2K43BB1-CRC (2x 16GiB, 2400 Mbps), SSD: Samsung MZVLB512HAJQ-000L7 (512GB, 3 000 MB / s)

Takže jasně:

• halda vložte t ime je v podstatě konstantní.

  Můžeme jasně vidět body změny velikosti dynamického pole. Jelikož zprůměrujeme každých 10 tis. Vložek , abychom mohli vidět cokoli nad šumem systému , jsou tyto vrcholy ve skutečnosti asi 10krát větší, než je znázorněno!

  Zvětšený graf vylučuje v podstatě pouze body pro změnu velikosti pole a ukazuje, že téměř všechny vložky spadají pod 25 nanosekund.

• BST je logaritmický. Všechny vložky jsou mnohem pomalejší než průměrná vložka haldy.

• Podrobná analýza BST vs hashmap na adrese: https://stackoverflow.com/questions/18414579/what-data-structure-is-inside-stdmap-in-c/51945119#51945119

standardní měřítko pro vložení knihovny GCC C ++ na gem5

gem5 je úplný systémový simulátor, a proto poskytuje nekonečně přesné hodiny s m5 dumpstats. Zkusil jsem to tedy použít k odhadu časování pro jednotlivé vložky.

Interpretace:

• halda je stále konstantní, ale nyní vidíme podrobněji, že existuje několik řádků a každý vyšší řádek je řídčí .

  To musí odpovídat latenci přístupu do paměti, která se provádí u vyšších a vyšších vložení.

• TODO Nemohu opravdu plně interpretovat BST, protože nevypadá tak logaritmicky a poněkud konstantněji.

  S tímto větším detailem však můžeme vidět i několik odlišných řádků, ale nejsem si jistý, co představují: očekával bych, že spodní řádek být tenčí, protože vložíme horní dolní část?

Srovnáváno s tímto nastavením Buildroot na aarch64 CPU HPI .

BST nelze efektivně implementovat do pole

Halda operace potřebují pouze bublinu nahoru nebo dolů v jedné větvi stromu, takže O(log(n)) nejhorší swapy, O(1) průměr.

Udržování vyváženého BST vyžaduje rotace stromů, které mohou změnit vrchní prvek za jiný, a vyžadovalo by přesun celého pole (O(n)).

Hromady lze efektivně implementovat do pole

Rodičovské a podřízené indexy lze vypočítat z aktuálního indexu jak je znázorněno zde .

Neexistují žádné vyrovnávací operace jako BST.

Smazání min je nejobávanější operací musí být shora dolů. Vždy to ale lze provést „prosakováním“ jedné větve haldy , jak je vysvětleno zde . To vede k nejhoršímu případu O (log (n)), protože hromada je vždy dobře vyvážená.

Pokud vkládáte jeden uzel pro každý odebraný, ztratíte výhodu asymptotiky O (1) průměrná vložka, kterou hromady poskytují, protože mazání bude dominovat, a můžete také použít BST. Dijkstra však aktualizuje uzly několikrát pro každé odstranění, takže jsme v pořádku.

Haldy dynamického pole vs hromady stromů ukazatelů

Haldy lze efektivně implementovat nad hromadou ukazatele: https://stackoverflow.com/questions/19720438/is-it-possible-to-make-efficient-pointer-based-binary-heap-implementations

Implementace dynamického pole je prostorově efektivnější. Předpokládejme, že každý prvek haldy obsahuje pouze ukazatel na struct:

• implementace stromu musí ukládat tři ukazatele pro každý prvek: rodič, levé a pravé dítě. Využití paměti je tedy vždy 4n (3 stromové ukazatele + 1 struct ukazatel).

  Stromové BST by také potřebujete další vyrovnávací informace, např black-red-ness.

• implementace dynamického pole může mít velikost 2n hned po zdvojnásobení. V průměru to tedy bude 1.5n.

Na druhou stranu má halda stromu lepší vložení pro nejhorší případ, protože kopírování dynamického pole zálohy na dvojnásobek jeho velikosti trvá O(n) nejhorší případ, zatímco halda stromu dělá pro každý uzel nové malé alokace.

Přesto podpora zdvojnásobení pole je O(1) amortizováno, takže jde o zvážení maximální latence. Zmíněno zde .

Filozofie

• BST udržují globální vlastnost mezi rodičem a všemi potomky (vlevo menší, vpravo větší).

  Horní uzel BST je prostřední prvek , což vyžaduje udržování globálních znalostí (vědět, kolik menších a větších prvků se tam nachází).

  Udržování této globální vlastnosti je nákladnější (log n insert), ale poskytuje výkonnější vyhledávání (log n search) .

• Hromady udržují místní vlastnost mezi nadřazenými a přímými podřízenými (nadřazené> podřízené).

  Horní nota haldy je velký prvek, který vyžaduje pouze místní znalosti k udržení (znalost vašeho rodiče).

Porovnání BST vs Heap vs Hashmap:

• BST: může být buď rozumný:

  • neuspořádaná sada (struktura, která určuje, zda byl prvek dříve vložen nebo ne). Ale hashmap má tendenci být lepší kvůli O (1) amortizované vložce.
  • třídícímu stroji. Ale hromada je v tom obecně lepší, a proto je heapsort mnohem známější než třídění stromů

• halda: je pouze třídicí stroj. Nemůže to být efektivní neuspořádaná sada, protože rychle můžete zkontrolovat pouze nejmenší / největší prvek.

• hash mapa: může to být pouze neuspořádaná sada, ne efektivní třídicí stroj, protože zatřiďování mísí veškeré objednávky.

Seznam s dvojnásobným propojením

Dvojitě propojený seznam lze považovat za podmnožinu haldy, kde má první položka největší prioritu, takže je zde také porovnejte:

• vložení:
  • pozice:
    • dvojnásobně propojený seznam: vložená položka musí být buď první, nebo poslední, protože na tyto prvky máme pouze ukazatele.
    • binární halda: vložená položka může skončit na jakékoli pozici. Méně omezující než propojený seznam.
  • čas:
    • dvojnásobně propojený seznam: O(1) nejhorší případ, protože máme ukazatele na položky a aktualizace je opravdu jednoduchá
    • binární halda: O(1) průměr, tedy horší než propojený seznam. mít obecnější pozici pro vložení.
• hledat: O(n) pro oba

Případem použití je, když klíčem haldy je aktuální časové razítko: v takovém případě nové položky vždy přejdou na začátek seznamu. Můžeme tedy dokonce úplně zapomenout na přesné časové razítko a ponechat pozici v seznamu jako prioritu.

To lze použít k implementaci mezipaměti LRU . Stejně jako pro haldy aplikací, jako je Dijkstra , budete si chtít ponechat další hashmapu z klíče k odpovídajícímu uzlu seznamu, abyste zjistili, který uzel se má rychle aktualizovat .

Porovnání různých vyvážených BST

Ačkoli asymptotické vložení a hledání časy pro všechny datové struktury, které jsou běžně klasifikovány jako „Vyvážené BST“, které jsem zatím viděl, jsou stejné, různé BBST mají různé kompromisy. Ještě jsem to úplně neštudoval, ale bylo by dobré shrnout tyto kompromisy zde:

• Červeno-černý strom . Od roku 2019 se jeví jako nejčastěji používaný BBST, např. je to ten, který používá implementace GCC 8.3.0 C ++
• strom AVL . Zdá se, že je o něco vyváženější než BST, takže by mohlo být lepší najít latenci nálezu za cenu o něco dražších nálezů.Wiki shrnuje: „Stromy AVL jsou často srovnávány s červeno-černými stromy, protože oba podporují stejnou sadu operací a základní operace vyžadují [stejný] čas. U aplikací náročných na vyhledávání jsou stromy AVL rychlejší než červeno-černé stromy, protože jsou přísněji vyvážené. Podobně jako červeno-černé stromy jsou stromy AVL výškově vyvážené. Oba nejsou obecně vyvážené podle hmotnosti ani u žádného mu < 1 / 2; to znamená, že sourozenecké uzly mohou mít velmi odlišný počet potomků. “
• WAVL . původní práce zmiňuje výhody této verze, pokud jde o meze operací vyvážení a rotace.

Viz také

Podobná otázka pro CS: Co ' je rozdíl mezi binárním vyhledávacím stromem a binární hromadou?

Komentáře

• Skvělá odpověď . Běžnou aplikací haldy jsou medián, k min, top k prvků. U těchto nejběžnějších operací odeberte min then insert (obvykle máme malou haldu s několika operacemi čistého vložení). V praxi to tedy vypadá, že u těchto algoritmů nepřekoná BST.
• Výjimečná odpověď !!! Použitím deque jako podkladové struktury haldy můžete dramaticky zkrátit časy změny velikosti, i když je to stále O (n) nejhorší případ, protože je potřeba přerozdělit (menší) pole ukazatelů na bloky.

Oba binární vyhledávací stromy a binární hromady jsou datové struktury založené na stromech.

Hromady vyžadují, aby uzly měly přednost před svými dětmi. Na maximální haldě musí být děti každého uzlu menší než on sám. U minimální haldy je to naopak:

Binární vyhledávací stromy (BST) sledují konkrétní pořadí (předobjednávky, v pořadí, poobjednávky) mezi sourozenskými uzly. Strom musí být tříděny, na rozdíl od hromad:

BST mají průměr $ O (\ log n) $ pro vkládání, mazání a vyhledávání.
Binární hromady mají průměr $ O (1) $ pro findMin / findMax a $ O (\ log n) $ pro vkládání a mazání.

Komentáře

• Extrakce @FrankW je $ O (\ log n) $, ne?

Kromě předchozích odpovědí musí halda obsahovat vlastnost struktury haldy ; strom musí být plný a nejspodnější vrstva, která nemůže být vždy plná, musí být vyplněna zleva doprava úplně bez mezer.