Goldberg a Cherkassky (REF) si v¹imli, ¾e ve~víceúrovòových pøihrádkových strukturách
platíme pøíli¹ mnoho za~úrovnì, ve~kterých se za~dobu jejich existence objeví jen malé
mno¾ství prvkù. Navrhli tedy ukládat prvky z~\uv{malých} úrovní do~spoleèné haldy.
-Výsledné struktuøe se øíká HOT (Heap-on-Top) Queue.
+Výsledné struktuøe se øíká HOT (Heap-on-Top) Queue. My si pøedvedeme její upravenou
+variantu (v~té pùvodní se skrývá nìkolik chyb).
-Poøídíme si tedy haldu, øeknìme Fibonacciho, a~navíc ke~ka¾dé úrovni poèítadlo udávající,
+Poøídíme si haldu, øeknìme Fibonacciho, a~navíc ke~ka¾dé úrovni poèítadlo udávající,
kolik prvkù z~této úrovnì jsme ulo¾ili do~haldy. Dokud toto poèítadlo nepøeroste nìjaký
parametr~$H$, pøihrádky nebudeme zakládat a prvky poputují do~haldy. Èas $\O(B)$ na
zalo¾ení úrovnì a její procházení tedy mù¾eme rozpoèítat mezi~$H$ prvkù, které se musely
vùbec nevadí -- poèítadlo pouze hlídá, aby se úroveò nevytvoøila pøíli¹ brzy a abychom
mìli dost prvkù k~rozúètování èasu.)
-\<Insert> tedy pøed zaøazením na pøíslu¹nou úroveò zvý¹í poèítadlo a pokud je
-stále men¹í ne¾~$H$, vlo¾í prvek do~haldy. Jinak prvek vlo¾í do~pøíslu¹né pøihrádky
-(pokud je¹tì pøihrádky neexistují, zalo¾í je).
+Promìnnou~$\mu$ necháme ukazovat na~místo, kde jsme se pøi hledání minima v~pøihrádkách
+zastavili. Souèasné globální minimum struktury tedy mù¾e být ni¾¹í, kdy¾ se minimum
+zrovna nachází v~haldì, ale stále je zaruèeno, ¾e pøed~$\mu$ se ji¾ nenachází ¾ádná
+neprázdná pøihradka.
-\<Decrease> se podívá, zda je prvek v~haldì nebo v~pøihrádce (to si o~nìm pamatuje).
-Pokud v~haldì, pøedá øízení operaci \<Decrease> haldy. Pokud v~pøihrádce, pøevede se
-na smazání a \<Insert>. S~poèítadly sám nehýbe.
+Operace budou fungovat takto:
-\<ExtractMin> funguje jako pøedtím, pouze se musí poka¾dé podívat na~minimum haldy
+\>\<Insert>:
+\algo
+\:Spoèítáme, do~které úrovnì~$i$ ma prvek padnout.
+\:Pokud je poèítadlo této úrovnì men¹í ne¾~$K$, zvý¹íme ho, vlo¾íme prvek do~haldy a skoèíme.
+\:Nebyly-li je¹tì pro tuto úroveò zalo¾eny pøihrádky, vyrobíme je (prázdné).
+\:Vlo¾íme prvek do~pøíslu¹né pøihrádky.
+\endalgo
+
+\>\<Decrease>:
+\algo
+\:Pokud se prvek nachází v~haldì (to si u~ka¾dého prvku pamatujeme), provedeme
+ \<Decrease> v~haldì a skonèíme.
+\:Sma¾eme prvek z~jeho pøihrádky a provedeme \<Insert> s~novou hodnotou.
+\endalgo
+
+\>\<ExtractMin>:
+\algo
+\:Dokud je~$\mu$ men¹í ne¾ aktuální minimum haldy, opakujeme:
+\::Najdeme pøihrádku odpovídající hodnotì~$\mu$.
+\::Je-li tato pøihrádka prázdná, pøejdeme na~dal¹í (upravíme~$\mu$). Jsme-li na konci úrovnì, pak o~úroveò vý¹.
+\::Rozprostøeme tuto pøihrádku o~úroveò ní¾ (stejným zpùsobem, jako pøi \<Insert>u,
+ tak¾e prvních~$H$ prvkù vlo¾íme do~haldy).
+\:Sma¾eme minimum z~haldy a vrátíme ho jako výsledek.
+\endalgo
+
+\>Pustíme se do~analýzy slo¾itosti. Jako parametry si zvolíme poèet hladin~$d$ (tak¾e
+poèet pøihrádek~$B$ na jedné úrovni je roven $L^{1/d}$) a \uv{haldovou konstantu}~$H$.
-FIXME
+Nejprve si v¹imneme, ¾e ne¾ poèítadlo nìjaké úrovnì vynulujeme, jsou bezpeènì
+z~haldy pryè v¹echny prvky patøící do~této úrovnì. Celkem se tedy v~haldì
+vyskytuje nejvý¹e $\O(dH)$ prvkù. \<ExtractMin> v~haldì tedy trvá $\O(\log(dH))$,
+ostatní haldové operace $\O(1)$.
-XXX: odhad na velikost haldy
+Nyní rozúètujeme èas operací mezi jednotlivé prvky (opìt si v¹e pøedplatíme
+v~\<Insert>u a ostatní operace pobì¾í v~amortizovanì konstantním èase):
+
+\itemize\ibull
+\:Ka¾dý prvek mù¾e být nejvý¹e jednou za~dobu svého ¾ivota vlo¾en do~haldy
+ a nejvý¹e jednou z~ní vyjmut. Na~obojí dohromady pøispìje $\O(\log dH)$.
+\:Prvek se úèastní nejvý¹e~$d$ pøehození do~ni¾¹í úrovnì. Pokud byl pøihozen
+ do~haldy, u¾ tam setrvá, jinak poka¾dé zaplatí $\O(1)$ za~zaøazení do~pøihrádky,
+ celkem tedy $\O(d)$ na prvek.
+\:Vytvoøení, projití a smazání pøihrádek na~jedné úrovni nastane a¾ tehdy, co bylo
+ $H$~prvkù patøících do~této úrovnì vlo¾eno do~haldy. Staèí tedy, aby ka¾dý
+ prvek pøispìl èasem $\O(B/H) = \O(L^{1/d}/H)$.
+\endlist
-XXX: proè je~$B$ velké, ale~$d$ malé?
+\>Ka¾dý prvek tedy platí $\O(d + \log dH + L^{1/d}/H) = \O(d + \log H + L^{1/d}/H)$.
+Pojïme najít nastavení parametrù, abychom tento výraz minimalizovali.
+Nejprve zvolme~$H$ tak, aby se~$d$ vyrovnalo s~$L^{1/d}/H$. Tedy $H = L^{1/d}/d$.
+Celý výraz tím zjednodu¹íme na $\O(d + \log\,(L^{1/d}/d))$ =
+$\O(d + 1/d\cdot\log L - \log d) = \O(d + 1/d\cdot\log L)$. Dále zvolíme~$d$
+tak, aby se oba výrazy vyrovnaly, èili $d=\sqrt{\log L}$.
-XXX: prvek pøispìje $d + T(H) + dL^{1/d}/H$.
+HOT Queue tedy zvládne \<Insert> amortizovanou èasovou slo¾itostí $\O(\sqrt{\log L})$
+a ostatní operace v~èase amortizovanì konstantním. Pou¾ijeme-li tuto strukturu
+v~Dijkstrovì algoritmu, spoète vzdálenosti v~èase $\O(m + n\sqrt{\log L})$.
%\references
\bye
projects / ga.git / blobdiff