Stín hromady - Shadow heap

v počítačová věda, a stínová hromada je slučitelná hromada datová struktura který podporuje efektivní hromadění haldy v amortizovaný smysl. Konkrétněji, hromady stínu využít algoritmus stínového sloučení k dosažení vložení do Ó (F(n)) amortizovaný čas a výmaz v Ó((log n log log n)/F(n)) amortizovaná doba pro jakoukoli volbu 1 ≤ f (n) ≤ log log n.^[1]

V celém tomto článku se předpokládá, že A a B jsou binární hromady s |A| ≤ |B|.

Sloučení stínů

Sloučení stínů je algoritmus pro sloučení dvou binární hromady efektivně, pokud jsou tyto hromady implementovány jako pole. Konkrétně se doba chodu stínu sloučila na dvou hromadách ${ displaystyle A}$ a ${ displaystyle B}$ je ${ displaystyle O (| A | + min { log | B | log log | B |, log | A | log | B | })}$.

Algoritmus

Chtěli bychom sloučit dvě binární hromady ${ displaystyle A}$ a ${ displaystyle B}$. Algoritmus je následující:

1. Zřetězte pole ${ displaystyle A}$ na konci pole ${ displaystyle B}$ získat pole ${ displaystyle C}$.
2. Určete stín z ${ displaystyle A}$ v ${ displaystyle C}$; to znamená předkové posledního ${ displaystyle | A |}$ uzly v ${ displaystyle C}$ které zničí vlastnost haldy.
3. Určete následující dvě části stínu z ${ displaystyle C}$:
   • The cesta ${ displaystyle P}$: sada uzlů ve stínu, pro které jsou v libovolné hloubce maximálně 2 ${ displaystyle C}$;
   • The podstrom ${ displaystyle T}$: zbytek stínu.
4. Rozbalte a roztřiďte nejmenší ${ displaystyle | P |}$ uzly ze stínu do pole ${ displaystyle S}$.
5. Přeměnit ${ displaystyle S}$ jak následuje:
   • Li ${ displaystyle | S |> | C |}$, poté počínaje od nejmenšího prvku v seřazeném poli postupně vkládejte každý prvek z ${ displaystyle S}$ do ${ displaystyle C}$, nahradí je ${ displaystyle C}$nejmenší prvky.
   • Li ${ displaystyle | S | leq | C |}$, poté rozbalte a roztřiďte ${ displaystyle | P |}$ nejmenší prvky z ${ displaystyle C}$a sloučit tento seřazený seznam s ${ displaystyle S}$.
6. Vyměňte prvky ${ displaystyle S}$ do svých původních pozic v ${ displaystyle C}$.
7. Udělejte hromadu ${ displaystyle T}$.

Provozní doba

Opět nechte ${ displaystyle P}$ označit cestu a ${ displaystyle T}$ označte podstrom zřetězené hromady ${ displaystyle C}$. Počet uzlů v ${ displaystyle P}$ je maximálně dvojnásobná hloubka ${ displaystyle C}$, který je ${ displaystyle O ( log | B |)}$. Navíc počet uzlů v ${ displaystyle T}$ v hloubce ${ displaystyle d}$ je maximálně 3/4 počet uzlů v hloubce ${ displaystyle d + 1}$, takže podstrom má velikost ${ displaystyle O (| A |)}$. Protože na každé úrovni jsou maximálně 2 uzly ${ displaystyle P}$, pak číst nejmenší ${ displaystyle | P |}$ prvky stínu do seřazeného pole ${ displaystyle S}$ bere ${ displaystyle O ( log | B |)}$ čas.

Li ${ displaystyle | S |> | C |}$, pak kombinovat ${ displaystyle P}$ a ${ displaystyle C}$ stejně jako v kroku 5 výše vyžaduje čas ${ displaystyle O ( log | A | log | B |)}$. Jinak je čas potřebný v tomto kroku ${ displaystyle O (| A | + log | B | log log | B |)}$. Nakonec je hromada podstromu ${ displaystyle T}$ bere ${ displaystyle O (| A |)}$ čas. To se rovná celkové době chodu pro sloučení stínů ${ displaystyle O (| A | + min { log | A | log | B |, log | B | log log | B | })}$.

Struktura

Hromada stínů ${ displaystyle H}$ sestává z prahové funkce ${ displaystyle f (H)}$a pole pro které je implementováno obvyklé pole binární hromada vlastnost je potvrzena ve svých prvních položkách a pro kterou není vlastnost haldy nutně potvrzena v ostatních položkách. Stínová halda je tedy v podstatě binární halda ${ displaystyle B}$ sousedící s polem ${ displaystyle A}$. Chcete-li přidat prvek do haldy stínů, umístěte jej do pole ${ displaystyle A}$. Pokud se pole stane příliš velkým podle zadané prahové hodnoty, nejprve vytvoříme hromadu ${ displaystyle A}$ použitím Floydův algoritmus pro stavbu haldy,^[2] a poté sloučit tuto hromadu s ${ displaystyle B}$ pomocí stínového sloučení. Nakonec se sloučení hromád stínů jednoduše provede postupným vložením jedné hromady do druhé pomocí výše uvedeného postupu vložení.

Analýza

Dostali jsme hromadu stínů ${ displaystyle H = (B, A)}$, s prahovou funkcí ${ displaystyle log | H | leq f (H) leq log | H | log log | H |}$ jak je uvedeno výše. Předpokládejme, že prahová funkce je taková, že každá změna v ${ displaystyle | B |}$ nevyvolává větší změnu než v ${ displaystyle f (H)}$. Odvozujeme požadované hranice doby chodu pro slučitelná hromada operace pomocí potenciální metoda pro amortizovaná analýza. Potenciál ${ displaystyle Psi (H)}$ hromady je vybrán jako:

${ displaystyle Psi (H) = | A | (1+ min { log | B | log log | B |, log | B | log | A | } / f (H)) }$

Pomocí tohoto potenciálu můžeme získat požadované amortizované doby chodu:

vytvořit(H): inicializuje novou prázdnou haldu stínů ${ displaystyle H}$

Tady potenciál ${ displaystyle Psi}$ se nezmění, takže amortizovaná cena za vytvoření je ${ displaystyle O (1)}$skutečné náklady.

vložit(X, H): vložky ${ displaystyle x}$ do stínu hromady ${ displaystyle H}$

Existují dva případy:

• Pokud je sloučení použito, pak pokles potenciální funkce je přesně skutečná cena sloučení ${ displaystyle B}$ a ${ displaystyle A}$, takže amortizovaná cena je ${ displaystyle O (1)}$.
• Pokud sloučení neproběhne, pak je amortizovaná cena ${ displaystyle O (1+ min { log | B | log log | B |, log | B | log | A | } / f (H))}$

Volbou prahové funkce tak získáme, že amortizovaná cena vložení je:

${ displaystyle O ( log | H | log log | H | / f (H))}$

delete_min (H): odstraní prvek minimální priority z ${ displaystyle H}$

Nalezení a odstranění minima vyžaduje skutečný čas ${ displaystyle O (| A | + log | B |)}$. Kromě toho se potenciální funkce může po tomto smazání zvýšit pouze v případě, že hodnota ${ displaystyle f (H)}$ klesá. Podle volby ${ displaystyle f}$, máme, že amortizovaná cena této operace je stejná jako skutečná cena.

Související algoritmy a datové struktury

Naivní algoritmus sloučení binárních hald spojí dvě hromady ${ displaystyle A}$ a ${ displaystyle B}$ včas ${ displaystyle O (| B |)}$ jednoduchým zřetězením obou hromad a vytvořením hromady z výsledného pole pomocí Floydův algoritmus pro stavbu haldy. Alternativně lze hromady jednoduše sloučit postupným vkládáním každého prvku ${ displaystyle A}$ do ${ displaystyle B}$, čas ${ displaystyle O (| A | log | B |)}$.

Pytel a Strothotte navrhl algoritmus pro sloučení binárních hromad v ${ displaystyle O (| A | + log | A | log | B |)}$ čas.^[3] Je známo, že jejich algoritmus je efektivnější než výše popsané druhé naivní řešení, když ${ displaystyle | A |> log | B |}$. Stínové sloučení funguje asymptoticky lépe než jejich algoritmus, a to i v nejhorším případě.

Existuje několik dalších hromad, které podporují rychlejší časy sloučení. Například, Fibonacci se hromadí lze sloučit do ${ displaystyle O (1)}$ čas. Protože binární hromady vyžadují ${ displaystyle Omega (| A |)}$ čas na sloučení,^[4] sloučení stínů zůstává účinné.

Reference