Binární hromada - Binary heap - Wikipedia

Příklad úplné binární max-haldy

Příklad úplné binární haldy min

A binární hromada je halda datová struktura který má podobu a binární strom. Binární hromady jsou běžným způsobem implementace prioritní fronty.^{[1]:162–163} Binární hromadu představil J. W. J. Williams v roce 1964 jako datová struktura pro heapsort.^[2]

Binární halda je definována jako binární strom se dvěma dalšími omezeními:^[3]

• Vlastnost Shape: binární halda je a kompletní binární strom; to znamená, že všechny úrovně stromu, s výjimkou poslední (nejhlubší), jsou plně vyplněny, a pokud není poslední úroveň stromu úplná, jsou uzly této úrovně vyplněny zleva doprava.
• Vlastnost haldy: klíč uložený v každém uzlu je podle některých buď větší nebo roven (≥) nebo menší nebo roven (≤) klíčům v podřízených uzlech celková objednávka.

Hromady, kde je nadřazený klíč větší nebo roven (≥) dětským klíčům, jsou volány maximální hromady; volají se ti, kde je menší nebo roven (≤) hromady min. Efektivní (logaritmický čas ) jsou známy algoritmy pro dvě operace potřebné k implementaci prioritní fronty na binární haldě: vložení prvku a odebrání nejmenšího nebo největšího prvku z min-haldy, respektive max-haldy. Binární hromady se také běžně používají v heapsort třídicí algoritmus, což je algoritmus na místě, protože binární hromady lze implementovat jako implicitní datová struktura, ukládání klíčů do pole a použití jejich relativních pozic v tomto poli k reprezentaci vztahů dítě-rodič.

Haldy operace

Operace vložení a odebrání nejprve upraví haldu tak, aby vyhovovala vlastnosti shape, přidáním nebo odebráním z konce haldy. Potom se vlastnost haldy obnoví procházením haldy nahoru nebo dolů. Obě operace trvají O (log n) čas.

Vložit

Chcete-li přidat prvek do haldy, můžeme provést tento algoritmus:

1. Přidejte prvek do spodní úrovně haldy v otevřeném prostoru nejvíce vlevo.
2. Porovnejte přidaný prvek s jeho nadřazeným prvkem; pokud jsou ve správném pořadí, přestaňte.
3. Pokud ne, vyměňte prvek za nadřazený a vraťte se k předchozímu kroku.

Kroky 2 a 3, které obnoví vlastnost haldy porovnáním a případně zaměněním uzlu s jeho nadřazeným prvkem, se nazývají hromada provoz (také známý jako vybublat, perkoleje, prosít, dotek, vyplavat, heapify-upnebo kaskádovitě).

Počet požadovaných operací závisí pouze na počtu úrovní, které musí nový prvek zvýšit, aby vyhověl vlastnosti haldy. Operace vložení má tedy nejhorší časovou složitost O (log n). Pro náhodnou hromadu a pro opakované vložení má operace vložení průměrnou složitost O (1).^[4][5]

Jako příklad vložení binární haldy řekněme, že máme haldu max

a chceme přidat haldu číslo 15. Nejprve umístíme 15 na pozici označenou X. Vlastnost haldy je však od té doby porušena 15 > 8, takže musíme vyměnit 15 a 8. Takže máme hromadu vypadající takto po první výměně:

Vlastnost haldy je však od té doby stále porušována 15 > 11, takže musíme znovu vyměnit:

což je platná max. hromada. Po tomto posledním kroku není třeba kontrolovat levé dítě: na začátku byla platná max-heap, což znamená, že kořen byl již větší než jeho levé dítě, takže nahrazení kořene ještě větší hodnotou zachová vlastnost, kterou každý uzel je větší než jeho podřízené (11 > 5; -li 15 > 11, a 11 > 5, pak 15 > 5, kvůli tranzitivní vztah ).

Výpis

Postup pro odstranění kořene z haldy (efektivní extrakce maximálního prvku v haldě max nebo minimálního prvku v haldě) při zachování vlastnosti haldy je následující:

1. Nahraďte kořen haldy posledním prvkem na poslední úrovni.
2. Porovnejte nový kořen s jeho dětmi; pokud jsou ve správném pořadí, přestaňte.
3. Pokud ne, vyměňte prvek za jednu z jeho podřízených položek a vraťte se k předchozímu kroku. (Zaměňte své menší dítě za hromadu min a větší dítě za hromadu max.)

Kroky 2 a 3, které obnovují vlastnost haldy porovnáním a případně zaměněním uzlu s jednou z jejích podřízených jednotek, se nazývají hromada (také známý jako bublina dolů, perkolátkové peří, prosít dolů, potopit, stékat, heapify-down, kaskádově dolů, extrakt-min nebo extrakt-maxnebo jednoduše heapify) úkon.

Takže pokud máme stejnou hromádku jako předtím

Odstraníme 11 a nahradíme ji 4.

Vlastnost haldy je nyní porušena, protože 8 je větší než 4. V tomto případě je pro obnovení vlastnosti haldy dostačující výměna dvou prvků, 4 a 8, a nemusíme dále zaměňovat prvky:

Uzel pohybující se dolů je zaměněn za větší jejích dětí v max-haldě (v min-haldě by byla vyměněna za své menší dítě), dokud nesplní vlastnost haldy na své nové pozici. Této funkce je dosaženo pomocí Max-Heapify funkce, jak je definováno níže v pseudo kód pro pole -zálohovaná hromada A délky délka(A). Všimněte si, že A je indexován od 1.

// Provedení operace haldy dolů nebo heapify dolů pro maximální hromadu // A: pole představující haldu, indexované od 1 // i: index, od kterého se začíná při hromadění dolůMax-Heapify(A, i):    vlevo, odjet ← 2×i    že jo ← 2×i + 1    největší ← i        -li vlevo, odjet ≤ délka(A) a A[vlevo, odjet]> A [největší] pak:        největší ← vlevo, odjet
    -li že jo ≤ délka(A) a A[že jo] > A[největší] pak:        největší ← že jo        -li největší ≠ i pak:        vyměnit A[i] a A[největší]        Max-Heapify(A, největší)

Pro výše uvedený algoritmus správně re-heapify pole, žádné uzly kromě uzlu v indexu i a jeho dvě přímé děti mohou porušit vlastnost haldy. Operaci down-heap (bez předchozího swapu) lze také použít k úpravě hodnoty kořene, i když prvek není odstraněn.

V nejhorším případě musí být nový kořen vyměněn za své dítě na každé úrovni, dokud nedosáhne spodní úrovně haldy, což znamená, že operace odstranění má časovou složitost vzhledem k výšce stromu, nebo O (log n).

Vložte a extrahujte

Vložení prvku a potom extrahování z haldy lze provést efektivněji než jednoduše volat funkce vložení a extrakce definované výše, což by zahrnovalo operaci upheap i downheap. Místo toho můžeme provést pouze downheap operaci, a to následovně:

1. Porovnejte, zda je položka, kterou tlačíme, nebo vykukovaný vrchol hromady, větší (za předpokladu maximální hromady)
2. Pokud je kořen haldy větší:
   1. Nahraďte kořen novou položkou
   2. Down-heapify počínaje kořenem
3. Jinak vraťte položku, kterou tlačíme

Krajta poskytuje takovou funkci pro vložení a potom extrakci s názvem „heappushpop“, která je níže parafrázována.^[6][7] Předpokládá se, že pole haldy má svůj první prvek v indexu 1.

// Zatlačte novou položku na haldu (max) a poté extrahujte kořen výsledné haldy. // halda: pole představující haldu, indexované na 1 // položka: element to insert // Vrátí větší ze dvou mezi položka a kořen halda.Push-Pop(halda: Seznam , položka: T) -> T: -li halda není prázdný a halda [1]> položka pak: // vyměnit halda[1] a položka        _ dolů (halda počínaje indexem 1) vrátit se položka

Podobnou funkci lze definovat pro vyskakování a následné vkládání, které se v Pythonu nazývá „heapreplace“:

// Extrahujte kořen haldy a vložte novou položku // halda: pole představující haldu, indexované na 1 // položka: element k vložení // Vrátí aktuální kořen haldaNahradit(halda: Seznam , položka: T) -> T: vyměnit halda[1] a položka    _ dolů (halda počínaje indexem 1) vrátit se položka

Vyhledávání

Nalezení libovolného prvku zabere O (n) čas.

Vymazat

Odstranění libovolného prvku lze provést následovně:

1. Najděte index ${ displaystyle i}$ prvku, který chceme odstranit
2. Zaměňte tento prvek za poslední prvek
3. Down-heapify nebo up-heapify pro obnovení vlastnosti haldy. V max-heap (min-heap) je up-heapify vyžadován pouze v případě, že je nový klíč elementu ${ displaystyle i}$ je větší (menší) než předchozí, protože by mohla být porušena pouze vlastnost haldy nadřazeného prvku. Za předpokladu, že vlastnost haldy byla platná mezi prvkem ${ displaystyle i}$ a jeho děti před výměnou prvků, nemůže být porušeno nyní větší (menší) hodnotou klíče. Když je nový klíč menší (větší) než předchozí, je vyžadován pouze down-heapify, protože vlastnost haldy může být porušena pouze v podřízených prvcích.

Snižte nebo zvyšte klíč

Operace snížení klíče nahradí hodnotu uzlu danou hodnotou nižší hodnotou a operace zvýšení klíče provede totéž, ale s vyšší hodnotou. To zahrnuje vyhledání uzlu s danou hodnotou, změnu hodnoty a následné down-heapifying nebo up-heapifying k obnovení vlastnosti haldy.

Snížení klíče lze provést následujícím způsobem:

1. Najděte index prvku, který chceme upravit
2. Snižte hodnotu uzlu
3. Down-heapify (za předpokladu maximální haldy) k obnovení vlastnosti haldy

Klíč pro zvýšení lze provést následujícím způsobem:

1. Najděte index prvku, který chceme upravit
2. Zvyšte hodnotu uzlu
3. Up-heapify (za předpokladu maximální haldy) k obnovení vlastnosti haldy

Budování hromady

Budování hromady z řady n vstupní prvky lze provést spuštěním prázdné hromady a následným vložením každého prvku. Tento přístup, nazývaný Williamsovou metodou po vynálezci binárních hromad, je snadno viditelný Ó(n log n) čas: provádí n inzerce na Ó(log n) stojí každý.^[A]

Williamsova metoda je však neoptimální. Rychlejší metoda (kvůli Floyd^[8]) začíná libovolným umístěním prvků na binární strom, respektující vlastnost tvaru (strom může být reprezentován polem, viz níže). Pak počínaje od nejnižší úrovně a pohybující se nahoru, prosévejte kořen každého podstromu dolů jako v algoritmu odstraňování, dokud není obnovena vlastnost haldy. Přesněji, pokud všechny podstromy začínají v nějaké výšce ${ displaystyle h}$ již byly „heapified“ (nejnižší úroveň odpovídající ${ displaystyle h = 0}$), stromy ve výšce ${ displaystyle h + 1}$ mohou být heapified odesláním jejich root dolů podél cesty maximálně hodnotných dětí při budování max-haldy, nebo minimálně hodnotných dětí při budování min-haldy. Tento proces trvá ${ displaystyle O (h)}$ operace (swapy) na uzel. U této metody probíhá většina heapifikace v nižších úrovních. Protože výška hromady je ${ displaystyle lfloor log n rfloor}$, počet uzlů ve výšce ${ displaystyle h}$ je ${ displaystyle leq { frac {2 ^ { lfloor log n rfloor}} {2 ^ {h}}} leq { frac {n} {2 ^ {h}}}}$. Náklady na heapifikaci všech podstromů jsou tedy:

${ displaystyle { begin {aligned} sum _ {h = 0} ^ { lfloor log n rfloor} { frac {n} {2 ^ {h}}} O (h) & = O left (n sum _ {h = 0} ^ { lfloor log n rfloor} { frac {h} {2 ^ {h}}} right) & = O left (n sum _ { h = 0} ^ { infty} { frac {h} {2 ^ {h}}} vpravo) & = O (n) end {zarovnáno}}}$

To využívá skutečnost, že daný nekonečno série ${ textstyle sum _ {i = 0} ^ { infty} i / 2 ^ {i}}$ konverguje.

Je známo, že přesná hodnota výše uvedeného (nejhorší počet srovnání během výstavby haldy) se rovná:

${ displaystyle 2n-2s_ {2} (n) -e_ {2} (n)}$,^[9][b]

kde s₂(n) je součet všech číslic binární reprezentace z n a E₂(n) je exponent 2 v primární faktorizaci n.

Průměrný případ je složitější analyzovat, ale lze prokázat asymptoticky 1.8814 n - 2 záznamy₂n + Ó(1) srovnání.^[10][11]

The Build-Max-Heap následující funkce převede pole A který ukládá kompletníbinární strom s n uzly na maximální hromadu opakovaným používáním Max-Heapify (down-heapify pro maximální haldu) způsobem zdola nahoru. prvky pole indexované podlepodlaha (n/2) + 1, podlaha(n/2) + 2, ..., njsou všechny listy stromu (za předpokladu, že indexy začínají na 1) - každý je tedy halda s jedním prvkem a není třeba ji heapifikovat dolů. Build-Max-Heap běžíMax-Heapify na každém ze zbývajících uzlů stromu.

Build-Max-Heap (A):    pro každého index i z podlaha(délka(A)/2) dolů 1 dělat:        Max-Heapify(A, i)

Haldy implementace

Malý kompletní binární strom uložený v poli

Porovnání binární haldy a implementace pole.

Hromady jsou běžně implementovány pomocí pole. Do pole lze uložit libovolný binární strom, ale protože binární halda je vždy úplný binární strom, lze jej uložit kompaktně. Není potřeba žádný prostor ukazatele; místo toho lze rodiče a děti každého uzlu najít aritmetikou na indexech pole. Díky těmto vlastnostem je tato implementace haldy jednoduchým příkladem implicitní datová struktura nebo Ahnentafel seznam. Podrobnosti závisí na kořenové pozici, což může záviset na omezeních a programovací jazyk použitý pro implementaci nebo preference programátora. Konkrétně je někdy kořen umístěn na indexu 1, aby se zjednodušila aritmetika.

Nechat n být počet prvků v haldě a i být libovolný platný index pole ukládající hromadu. Pokud je kořen stromu na indexu 0, s platnými indexy 0 až n - 1, pak každý prvek A na indexu i má

• děti v indexech 2i + 1 a 2i + 2
• jeho nadřazený v indexu podlaha ((i − 1) ∕ 2).

Alternativně, pokud je kořen stromu na indexu 1, s platnými indexy 1 až n, pak každý prvek A na indexu i má

• děti v indexech 2i a 2i +1
• jeho nadřazený v indexu podlaha (já ∕ 2).

Tato implementace se používá v heapsort algoritmus, kde umožňuje opětovné použití prostoru ve vstupním poli k uložení haldy (tj. algoritmus je hotový na místě ). Implementace je také užitečná pro použití jako Prioritní fronta kde použití a dynamické pole umožňuje vložení neomezeného počtu položek.

Operace upheap / downheap lze potom určit z hlediska pole takto: Předpokládejme, že vlastnost haldy obsahuje indexy b, b+1, ..., E. Funkce sift-down rozšiřuje vlastnost haldy na b−1, b, b+1, ..., EPouze index i = b−1 může porušit vlastnost haldy j být indexem největšího dítěte z A[i] (pro maximální hromadu nebo nejmenší dítě pro minimální hromadu) v rozsahu b, ..., E(Pokud takový index neexistuje, protože 2i > E pak vlastnost haldy platí pro nově rozšířený rozsah a není třeba nic dělat.) Výměnou hodnot A[i] a A[j] vlastnost haldy pro pozici i V tomto okamžiku je jediným problémem to, že vlastnost haldy nemusí obsahovat index jJe použita funkce sift-down ocas rekurzivně indexovat j dokud není pro všechny prvky vytvořena vlastnost haldy.

Funkce sift-down je rychlá. V každém kroku potřebuje pouze dvě srovnání a jeden swap. Hodnota indexu, kde pracuje, se v každé iteraci zdvojnásobuje, takže se nanejvýš přihlásí₂ E jsou vyžadovány kroky.

Pro velké hromady a používání virtuální paměť, ukládání prvků do pole podle výše uvedeného schématu je neefektivní: (téměř) každá úroveň je v jiné strana. B-hromady jsou binární hromady, které udržují podstromy na jedné stránce, což snižuje počet stránek přístupných až desetkrát.^[12]

Operace sloučení dvou binárních hromád trvá Θ (n) pro hromady stejné velikosti. To nejlepší, co můžete udělat, je (v případě implementace pole) jednoduše zřetězení dvou polí haldy a vytvoření hromady výsledku.^[13] Hromadu n prvky lze sloučit s hromadou k prvky používající O (log n log k) srovnání klíčů, nebo v případě implementace založené na ukazateli, v O (log n log k) čas.^[14] Algoritmus pro rozdělení hromady n prvky na dvě hromady k a n-k prvků, respektive na základě nového pohledu na hromady, protože byla představena uspořádaná sbírka podsvětí.^[15] Algoritmus vyžaduje O (log n * log n) srovnání. Pohled také představuje nový a koncepčně jednoduchý algoritmus pro slučování hromad. Když je sloučení běžným úkolem, doporučuje se implementace jiné haldy, například binomické hromady, které lze sloučit v O (log n).

Navíc lze binární haldu implementovat s tradiční datovou strukturou binárního stromu, ale při přidávání prvku existuje problém s vyhledáním sousedního prvku na poslední úrovni na binární haldě. Tento prvek lze určit algoritmicky nebo přidáním dalších dat do uzlů, které se nazývají „navlékání“ stromu - namísto pouhého ukládání odkazů na děti ukládáme v pořádku nástupce uzlu.

Je možné upravit strukturu haldy tak, aby umožňovala extrakci jak nejmenšího, tak největšího prvku v ${ displaystyle O}$${ displaystyle ( log n)}$ čas.^[16] Za tímto účelem se řádky střídají mezi haldy min a max. Haldy. Algoritmy jsou zhruba stejné, ale v každém kroku je třeba vzít v úvahu střídavé řádky se střídavými porovnáními. Výkon je zhruba stejný jako u běžné haldy s jedním směrem. Tuto myšlenku lze zobecnit na min-max-medián hromady.

Odvození indexových rovnic

V haldě založené na poli mohou být podřízené a nadřazené položky uzlu umístěny pomocí jednoduché aritmetiky na indexu uzlu. Tato část odvozuje příslušné rovnice pro hromady s jejich kořenem v indexu 0, s dalšími poznámkami o hromadách s jejich kořenem v indexu 1.

Abychom předešli nejasnostem, definujeme úroveň uzlu jako jeho vzdálenost od kořene, takže samotný kořen zaujímá úroveň 0.

Podřízené uzly

Pro obecný uzel umístěný v indexu ${ displaystyle i}$ (počínaje od 0) nejdříve odvodíme index jejího pravého potomka, ${ displaystyle { text {right}} = 2i + 2}$.

Nechejte uzel ${ displaystyle i}$ být umístěn v úrovni ${ displaystyle L}$, a nezapomeňte, že na jakékoli úrovni ${ displaystyle l}$ obsahuje přesně ${ displaystyle 2 ^ {l}}$ uzly. Kromě toho existují přesně ${ displaystyle 2 ^ {l + 1} -1}$ uzly obsažené ve vrstvách až po vrstvu včetně ${ displaystyle l}$ (přemýšlejte o binární aritmetice; 0111 ... 111 = 1000 ... 000 - 1). Protože kořen je uložen na 0, ${ displaystyle k}$tento uzel bude uložen v indexu ${ displaystyle (k-1)}$. Spojením těchto pozorování se získá následující výraz pro index posledního uzlu ve vrstvě l.

${ displaystyle { text {poslední}} (l) = (2 ^ {l + 1} -1) -1 = 2 ^ {l + 1} -2}$

Ať tam bude ${ displaystyle j}$ uzly za uzlem ${ displaystyle i}$ ve vrstvě L, takhle

${ displaystyle { begin {alignedat} {2} i = & quad { text {last}} (L) -j = & quad (2 ^ {L + 1} -2) -j end {alignedat}}}$

Každý z těchto ${ displaystyle j}$ uzly musí mít přesně 2 děti, takže tam musí být ${ displaystyle 2j}$ oddělující uzly ${ displaystyle i}$pravé dítě od konce jeho vrstvy (${ displaystyle L + 1}$).

${ displaystyle { begin {alignedat} {2} { text {right}} = & quad { text {last (L + 1)}} - 2j = & quad (2 ^ {L + 2 } -2) -2j = & quad 2 (2 ^ {L + 1} -2-j) +2 = & quad 2i + 2 end {alignedat}}}$

Podle potřeby.

Bereme na vědomí, že levé dítě kteréhokoli uzlu je vždy 1 místo před jeho pravým dítětem, dostaneme ${ displaystyle { text {left}} = 2i + 1}$.

Pokud je kořen umístěn na indexu 1 místo 0, poslední uzel v každé úrovni je místo na indexu ${ displaystyle 2 ^ {l + 1} -1}$. Pomocí tohoto v celém výnosu ${ displaystyle { text {left}} = 2i}$ a ${ displaystyle { text {right}} = 2i + 1}$ pro hromady s kořenem na 1.

Nadřazený uzel

Každý uzel je buď levým nebo pravým dítětem svého rodiče, takže víme, že platí některá z následujících možností.

1. ${ displaystyle i = 2 krát ({ text {parent}}) + 1}$
2. ${ displaystyle i = 2 krát ({ text {parent}}) + 2}$

Proto,

${ displaystyle { text {parent}} = { frac {i-1} {2}} ; { textrm {or}} ; { frac {i-2} {2}}}$

Nyní zvažte výraz ${ displaystyle left lfloor { dfrac {i-1} {2}} right rfloor}$.

Pokud uzel ${ displaystyle i}$ je levé dítě, to dává výsledek okamžitě, ale dává také správný výsledek, pokud je uzel ${ displaystyle i}$ je správné dítě. V tomto případě, ${ displaystyle (i-2)}$ musí být rovnoměrné, a proto ${ displaystyle (i-1)}$ musí být liché.

${ displaystyle { begin {alignedat} {2} left lfloor { dfrac {i-1} {2}} right rfloor = & quad left lfloor { dfrac {i-2} {2 }} + { dfrac {1} {2}} right rfloor = & quad { frac {i-2} {2}} = & quad { text {parent}} end {alignedat}}}$

Proto bez ohledu na to, zda je uzel levým nebo pravým dítětem, lze jeho rodiče najít výrazem:

${ displaystyle { text {parent}} = left lfloor { dfrac {i-1} {2}} right rfloor}$

Související struktury

Vzhledem k tomu, že vlastnost haldy neurčuje pořadí sourozenců v haldě, lze dva potomky jednoho uzlu volně zaměňovat, pokud to neporuší vlastnost tvaru (porovnejte s šlapat ). Všimněte si však, že v běžné haldě založené na poli může jednoduše výměna podřízených také vyžadovat přesun uzlů podřízených podřízených pro zachování vlastnosti haldy.

Binární halda je speciální případ hromada d-ary ve kterém d = 2.

Shrnutí provozních časů

Tady jsou časové složitosti^[17] různých haldy datových struktur. Názvy funkcí předpokládají minimální hromadu. Ve smyslu „Ó(F)" a "Θ(F) „viz Velká O notace.

Viz také

• Halda
• Heapsort

Reference

externí odkazy

• Otevřené datové struktury - Oddíl 10.1 - BinaryHeap: Implicitní binární strom, Pat Morin
• Implementace binární maximální haldy v C. Robin Thomas
• Implementace binární min haldy v C. Robin Thomas