Care este ' diferența dintre un arbore de căutare binar și un morman binar?

Heap garantează doar că elementele de la niveluri superioare sunt mai mari (pentru max-heap) sau mai mici (pentru min-heap) decât elementele de la niveluri inferioare, în timp ce BST garantează ordinea (de la „stânga” la „dreapta”) . Dacă doriți elemente sortate, mergeți cu BST. de Dante nu este un geek

Heap este mai bun la findMin / findMax (O ( 1)), în timp ce BST este bun la toate descoperirile (O (logN)). Insertul este O (logN) pentru ambele structuri. Dacă vă pasă doar de findMin / findMax (de exemplu, legate de prioritate), mergeți cu heap. Dacă doriți totul sortat, mergeți cu BST.

de xysun

Comentarii

• Cred că BST este mai bun în findMin & findMax stackoverflow .com / a / 27074221/764592
• Cred că aceasta este doar o comunicare pe concepție greșită. Un arbore binar poate fi ușor modificat pentru a găsi min și max așa cum a indicat Yeo. Aceasta este de fapt o restricție a heap-ului: numai găsirea eficientă este min sau max. Adevăratul avantaj al heap-ului este O (1) insert mediu așa cum explic: stackoverflow.com/a/29548834/895245
• Conform acest videoclip , puteți avea valori mai mari la un nivel inferior, atâta timp cât cel mai mare nu este descendent al celui inferior.
• Heap este sortat rădăcină în frunză și BST este sortat de la stânga la dreapta.
• ce se întâmplă dacă vreau să găsesc mediana în timp constant și să elimin mediană în timp logaritmic? pentru ce structură de date ar trebui să merg? va funcționa implementarea MinHeap? vă rugăm să sugerați.

Rezumat

 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) 

Toate timpurile medii de pe acest tabel sunt aceleași cu cele mai grave perioade ale acestora, cu excepția Insert.

• *: peste tot în acest răspuns, BST == BST echilibrat, deoarece neechilibrat este de rahat asimptotic
• **: folosind o modificare banală explicată în acest răspuns
• ***: log(n) pentru heapul arborelui pointer, n pentru heap din matrice dinamică

Avantajele heap-ului binar peste un BST

• timpul mediu de inserare într-o grămadă binară este O(1), pentru că BST este O(log(n)). Această este caracteristica ucigașă a grămezilor.

  Există și alte grămezi care ajung la O(1) amortizat (mai puternic) ca Heap Fibonacci și chiar cel mai rău caz, cum ar fi Coadă brodală , deși este posibil să nu fie practice din cauza performanței non-asimptotice: https://stackoverflow.com/questions/30782636/are-fibonacci-heaps-or-brodal-queues-used-in-practice-anywhere

• grămezile binare pot fi implementate eficient pe lângă matrice dinamice sau arborii bazate pe pointer, numai BST copaci pe bază de pointer. Deci, pentru heap, putem alege implementarea mai eficientă a spațiului, dacă ne permitem latențe ocazionale de redimensionare.

• crearea de heap binare este O(n) cel mai rău caz , O(n log(n)) pentru BST.

Avantajul BST față de stiva binară

• căutarea elementelor arbitrare este O(log(n)). Această este caracteristica ucigașă a BST-urilor.

  Pentru heap, este O(n) în general, cu excepția celui mai mare element care este O(1).

Avantajul „fals” al heap-ului față de BST

• heap este O(1) pentru a găsi maxim, BST O(log(n)).

  este o concepție greșită obișnuită, deoarece este banal să modificați un BST pentru a ține evidența celui mai mare element și să-l actualizați ori de câte ori acel element poate fi schimbat: la inserarea unui swap mai mare, la eliminare găsiți al doilea ca mărime. https://stackoverflow.com/questions/7878622/can-we-use-binary-search-tree-to-simulate-heap-operation (menționat de Yeo ).

  De fapt, aceasta este o limitare a grămezilor comparativ cu BST-urile: numai căutarea eficientă este cea pentru cel mai mare element.

Inserția medie a heap-ului binar este O(1)

Surse:

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

Argument intuitiv:

• nivelurile arborelui inferior au exponențial mai multe elemente decât nivelurile superioare, astfel încât elementele noi sunt aproape sigure că vor merge în partea de jos
• inserarea heap începe de jos , BST trebuie să înceapă de sus

Într-o grămadă binară, creșterea valorii la un indice dat este, de asemenea, O(1) din același motiv. Dar dacă doriți să faceți acest lucru, este probabil că veți dori să mențineți un index suplimentar actualizat la operațiunile heap https://stackoverflow.com/questions/17009056/how-to-implement-ologn-decrease-key-operation-for-min-heap-based-priority-queu de ex pentru Dijkstra. Posibil fără cost suplimentar.

Bibliotecă standard GCC C ++ să insereze etalon pe hardware real

Am comparat C ++ std::set ( copac roșu-negru BST ) și std::priority_queue ( heap din matrice dinamică ) inserare pentru a vedea dacă am avut dreptate în ceea ce privește orele de inserare și asta am obținut:

• cod de referință
• script de complot
• date grafic
• testat pe Ubuntu 19.04, GCC 8.3.0 într-un laptop Lenovo ThinkPad P51 cu CPU: CPU Intel Core i7-7820HQ (4 nuclee / 8 fire) , Bază 2,90 GHz, 8 MB cache), RAM: 2x Samsung M471A2K43BB1-CRC (2x 16GiB, 2400 Mbps), SSD: Samsung MZVLB512HAJQ-000L7 (512GB, 3.000 MB / s)

Așa de clar:

• insertul teanc ime este practic constantă.

  Putem vedea clar punctele de redimensionare a matricei dinamice. Întrucât facem media la fiecare 10k inserții pentru a putea vedea ceva mai presus de zgomotul sistemului , aceste vârfuri sunt de fapt de aproximativ 10k ori mai mari decât se arată! >

  Graficul mărit exclude în esență doar punctele de redimensionare a matricei și arată că aproape toate inserțiile se încadrează sub 25 de nanosecunde.

• BST este logaritmic. Toate inserțiile sunt mult mai lente decât media inserției heap.

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

Bibliotecă standard GCC C ++ pentru standardul de referință inserat pe gem5

gem5 este un simulator complet de sistem și, prin urmare, oferă un ceas infinit de precis cu m5 dumpstats. Așa că am încercat să-l folosesc pentru a estima temporizările pentru inserții individuale.

Interpretare:

• stiva este încă constantă, dar acum vedem mai detaliat că există câteva linii și fiecare linie superioară este mai rar .

  Acest lucru trebuie să corespundă latențelor de acces la memorie care se fac pentru inserții din ce în ce mai mari.

• TODO Nu pot interpreta cu adevărat BST-ul pe deplin ca nu arată atât de logaritmic și ceva mai constant.

  Cu acest detaliu mai mare, cu toate acestea, putem vedea, de asemenea, putem vedea câteva linii distincte, dar nu sunt sigur ce reprezintă: aș aștepta ca linia de jos să să fie mai subțire, deoarece inserăm partea de jos jos?

Analizat cu această configurare Buildroot pe un aarch64 CPU HPI .

BST nu poate fi implementat eficient pe o matrice

Heap operațiile trebuie doar să baloneze în sus sau în jos o singură ramură de copac, deci O(log(n)) cel mai rău caz swap, O(1) medie.

Păstrarea unui BST echilibrat necesită rotații de copac, care pot schimba elementul de sus cu altul și ar necesita deplasarea întregului tablou în jur (O(n)).

Heap-urile pot fi implementate eficient pe o matrice

Indicii părinți și copii pot fi calculați din indexul actual așa cum se arată aici .

Nu există operațiuni de echilibrare precum BST.

Ștergerea min este cea mai îngrijorătoare operație, deoarece trebuie să fie de sus în jos. Dar se poate face întotdeauna „percolând” o singură ramură a heap-ului așa cum este explicat aici . Acest lucru duce la cel mai rău caz O (log (n)), deoarece heap-ul este întotdeauna bine echilibrat.

Dacă introduceți un singur nod pentru fiecare pe care îl eliminați, atunci pierdeți avantajul asimptoticului O (1) inserție medie pe care o furnizează grămezile, deoarece ștergerea ar domina și s-ar putea să utilizați și un BST. Cu toate acestea, Dijkstra actualizează nodurile de mai multe ori pentru fiecare eliminare, deci suntem bine.

Heap-uri dinamice ale matricei comparativ cu cumulurile arborelui indicatorului

Heap-urile pot fi implementate eficient pe partea de sus a teancurilor de pointer: https://stackoverflow.com/questions/19720438/is-it-possible-to-make-efficient-pointer-based-binary-heap-implementations

Implementarea matricei dinamice este mai eficientă din punct de vedere spațial. Să presupunem că fiecare element heap conține doar un pointer către un struct:

• implementarea arborelui trebuie să stocheze trei indicatori pentru fiecare element: părinte, copil stâng și copil drept. Deci, utilizarea memoriei este întotdeauna 4n (3 indicatori de arbore + 1 struct indicator).

  Arborele BST ar fi, de asemenea, au nevoie de informații suplimentare de echilibrare, de exemplu negru-roșu-ness.

• implementarea matricei dinamice poate avea dimensiunea 2n imediat după o dublare. Deci, în medie, va fi 1.5n.

Pe de altă parte, grămada de copac are o inserție mai bună în cel mai rău caz, deoarece copierea matricei dinamice de back-up pentru a-și dubla dimensiunea necesită O(n) cel mai rău caz, în timp ce grămada de copac face doar alocări mici pentru fiecare nod.

Totuși, backing-ul dublarea matricei este O(1) amortizată, deci se reduce la o latență maximă. Menționat aici .

Filosofie

• BST-urile mențin o proprietate globală între un părinte și toți descendenții (stânga mai mică, dreapta mai mare).

  Nodul superior al unui BST este elementul de mijloc , care necesită cunoștințe globale pentru întreținere (știind câte elemente sunt din ce în ce mai mici).

  Această proprietate globală este mai scumpă de întreținut (log n insert), dar oferă căutări mai puternice (log n search) .

• Heap-urile mențin o proprietate locală între părinți și copii direcți (părinte> copii).

  Nota de vârf a unui heap este elementul cel mai important, care necesită doar cunoștințe locale pentru a le menține (cunoașterea părintelui).

Compararea BST vs Heap vs Hashmap:

• BST: poate fi fie rezonabil:

  • set neordonat (o structură care determină dacă un element a fost inserat anterior sau nu). Dar hashmap-ul tinde să fie mai bun datorită inserției amortizate O (1).
  • mașină de sortare. Dar heap-ul este, în general, mai bun în acest sens, motiv pentru care heapsort este mult mai cunoscut decât sortarea copacilor

• heap: este doar o mașină de sortat. Nu poate fi un set eficient neordonat, deoarece puteți verifica rapid cel mai mic / cel mai mare element.

• hartă hash: poate fi doar un set neordonat, nu o mașină de sortare eficientă, deoarece hashingul amestecă orice comandă.

Listă dublă legată

O listă dublă legată poate fi văzută ca subset al heap-ului unde primul element are cea mai mare prioritate, așa că să le comparăm și aici:

• inserare:
  • poziție:
    • listă dublă legată: elementul inserat trebuie să fie primul sau ultimul, deoarece avem doar indicii către acele elemente.
    • heap binar: elementul inserat poate ajunge în orice poziție. Mai puțin restrictivă decât lista legată.
  • timp:
    • listă dublă legată: O(1) cel mai rău caz, deoarece avem indicii către elemente, iar actualizarea este foarte simplă
    • heap binar: O(1) medie, deci mai rău decât lista conectată. având o poziție de inserție mai generală.
• căutare: O(n) pentru ambele

Un caz de utilizare pentru aceasta este atunci când cheia heap-ului este marca de timp curentă: în acest caz, noile intrări vor merge întotdeauna la începutul listei. Deci, putem chiar să uităm cu exactitate marca de timp exactă și să păstrăm poziția din listă ca prioritate.

Aceasta poate fi utilizată pentru a implementa o cache LRU . La fel ca pentru aplicațiile heap precum Dijkstra , veți dori să păstrați un hashmap suplimentar de la cheie la nodul corespunzător al listei, pentru a găsi ce nod să actualizați rapid .

Compararea diferitelor BST echilibrate

Deși inserarea asimptotică și găsiți ori pentru toate structurile de date care sunt clasificate în mod obișnuit ca „BST echilibrate” pe care „le-am văzut până acum este același, BBST-uri diferite au compromisuri diferite. Nu am studiat încă pe deplin acest lucru, dar ar fi bine să rezumăm aceste compromisuri aici:

• copac roșu-negru . Se pare că este cel mai frecvent utilizat BBST începând cu 2019, de ex. este cel folosit de implementarea GCC 8.3.0 C ++
• arborele AVL . Pare să fie ceva mai echilibrat decât BST, deci ar putea fi mai bine pentru a găsi latența, cu prețul descoperirilor puțin mai scumpe.Wiki rezumă: „Arborii AVL sunt adesea comparați cu arborii roșu-negri, deoarece ambii acceptă același set de operații și necesită [același] timp pentru operațiunile de bază. Pentru aplicații intensive de căutare, arborii AVL sunt mai rapizi decât copacii roșii-negri, deoarece sunt mai strict echilibrați. Asemănător copacilor roșu-negri, arborii AVL sunt echilibrați în înălțime. Ambii nu sunt, în general, nici echilibrați în greutate, nici mu-echilibrați pentru orice mu < 1 / 2; adică nodurile frați pot avea un număr foarte mare de descendenți. „
• WAVL . lucrarea originală menționează avantajele acelei versiuni în ceea ce privește limitele operațiunilor de reechilibrare și rotație.

Vezi și

Întrebare similară pe CS: Ce reprezintă diferența dintre un arbore de căutare binar și un heap binar?

Comentarii

• Răspuns excelent . Aplicația obișnuită a heap-ului este mediană, k min, top k elemente. Pentru aceste operații cele mai frecvente, eliminați min, apoi introduceți (de obicei avem o grămadă mică, cu puține operații de inserare pură). Așa se pare că în practică, pentru acești algoritmi nu depășește BST.
• Răspuns excepțional !!! Folosind deque ca structură heap subiacentă, puteți reduce dramatic timpii de redimensionare, deși este în continuare cel mai rău caz O (n), deoarece trebuie să realocați o serie (mai mică) de indicatori către bucăți.

Ambele copaci binari de căutare și grămezi binare sunt structuri de date bazate pe copaci.

Grămezile necesită ca nodurile să aibă prioritate față de copiii lor. Într-o grămadă maximă, copiii fiecărui nod trebuie să fie mai mici decât el însuși. Acest lucru este opus pentru o grămadă minimă:

Arborii de căutare binari (BST) urmează o anumită ordonare (precomandă, în ordine, post-comandă) între nodurile frate. Arborele trebuie să fie sortat, spre deosebire de grămezi:

BST au o medie de $ O (\ log n) $ pentru inserare, ștergere și căutare.
Binary Heaps au o medie $ O (1) $ pentru findMin / findMax și $ O (\ log n) $ pentru inserare și ștergere.

Comentarii

• @FrankW Extracția este $ O (\ log n) $, nu?