-\def\X{{\cal X}}
-\def\B{{\cal B}}
-\def\and{\ \&\ }
\def\msb{{\rm MSB}}
\def\rank{{\rm Rank}}
\def\pnromanp{(\nroman)}
\def\pnromanap{(\nroman ')}
-% Vlozeni obrazku {obrazek}{popisek}
-\def\nosizefigure#1#2{\bigskip\vbox{\centerline{\epsfbox{#1}}\smallskip\centerline{#2}}\bigskip}
-
\input ../sgr.tex
-\prednaska{8}{Q-Heaps}{zapsal Cyril Strejc}
+\prednaska{8}{Q-Heaps}{}
-Na minulém semináøi jsme si mimo jiné ukázali výpoèetní model RAM a nahlédli
-jsme, ¾e pomocí RAMu mù¾eme celkem snadno (v konstatním èase) simulovat
-vektorový poèítaè. A kdy¾ u¾ máme vektorový poèítaè, pojïme si ukázat, jaké
-datové struktury bychom s ním mohli vytváøet. Vektor ukládáme v $\O(w)$ slovech.
-V dal¹ím budeme BÚNO
-pøedpokládat, ¾e hodnoty, které do stuktur ukládáme, jsou rùzné. Svým sna¾ením
-smìrujeme ke strukturám, které zvládnou operace {\it Insert} a {\it Delete} v
-kostantním èase s rozumnou konstantou.
+V~minulé kapitole jsme zavedli výpoèetní model RAM a nahlédli jsme,
+¾e na~nìm mù¾eme snadno simulovat vektorový poèítaè s~vektorovými operacemi pracujícími v~konstantním èase.
+Kdy¾ u¾ máme takový poèítaè, pojïme si ukázat, jaké datové struktury na~nìm mù¾eme
+vytváøet.
-\s{Znaèení:}
-\itemize\ibull
-\: $w$, ¹íøka slova daného stroje (RAMu)
-\: $n$, velikost vstupu
-\endlist
-Abychom mohli indexovat vstup, dále pøedpokládejme, ¾e $w = \O(\log n)$.
+Svým sna¾ením budeme smìøovat ke~strukturám, které zvládnou operace \<Insert> a \<Delete>
+v~konstantním èase, pøièem¾ bude omezena buïto velikost èísel nebo maximální velikost
+struktury nebo obojí. Bez újmy na~obecnosti budeme pøedpokládat, ¾e hodnoty, které do~struktur
+ukládáme, jsou navzájem rùzné.
-\h{Word-Encoded B-Tree}
-V podstatì pùjde o obyèejný B-strom s daty v listech. Faktor stromu oznaème $B$.
-Ukládáme $k$-bitové hodnoty a chceme aby $Bk=\O(w)$ -- tehdy se nám uzel stromu
-vejde do vektoru a my budeme dostateènì rychle umìt operace s uzly, které do
-B-stromu potøebujeme, t.j. dìlení, spojování, vyhledávání. Té¾ ukládáme pointry
-na syny. Je tøeba si trochu rozmyslet, ¾e v ka¾dém uzlu se pointry na syny také
-povede ``scucnout'' do vektoru. Jen¾e poèet prvkù ($\vert T\vert$), které se do
-stromu vejdou je øádovì $B^h$, kde $h$ je hloubka stromu, a tudí¾ $\log\vert
-T\vert = \O(h)$. Proto se pointry do vektoru pìknì vejdou.
+\s{Znaèení:} $w$~bude v¾dy znaèit ¹íøku slova RAMu a $n$~velikost vstupu algoritmu,
+v~nìm¾ datovou strukturu vyu¾íváme (speciálnì tedy víme, ¾e $w\ge\log n$).
-\h{Q-Heaps}
+\h{Word-Encoded B-Tree}
-Q-Heap je teoreticky zajímavá datová struktura, v praxi neimplementovatelná.
-Narozdíl od Word-Encoded B-Tree není takové omezení na velikost ukládaného èísla
--- maximální velikost èísla odpovídá velikost slova.
+První strukturou, kterou popí¹eme, bude vektorová varianta B-stromu. Nemá je¹tì
+tak zajímavé parametry, ale odvozuje se snadno a jsou na~ní dobøe vidìt mnohé
+my¹lenky pou¾ívané ve~strukturách slo¾itìj¹ích.
+
+Pùjde o~obyèejný B-strom s daty v~listech, ov¹em kódovaný vektorovì. Do~listù
+stromu budeme ukládat $k$-bitové hodnoty, vnitøní vrcholy budou obsahovat pouze
+pomocné klíèe a budou mít nejvý¹e $B$ synù. Strom bude mít hloubku~$h$. Hodnoty
+v¹ech klíèù ve~vrcholu si budeme ukládat jako vektor, ukazatele na~jednotlivé
+syny jakbysmet.
+
+Se~stromem zacházíme jako s~klasickým B-stromem, pøitom operace s~vrcholy
+provádíme vektorovì: vyhledání pozice prvku ve~vektoru pomocí operace \<Rank>,
+rozdìlení a sluèování vrcholù pomocí bitových posuvù a maskování, to v¹e
+v~èase $\O(1)$. Stromové operace (\<Find>, \<FindNext>, \<Insert>, \<Delete>, \dots)
+tedy stihneme v~èase $\O(h)$.
+
+Zbývá si rozmyslet, co~musí splòovat parametry struktury, aby se v¹echny
+vektory ve¹ly do~konstantního poètu slov. Kvùli vektorùm klíèù musí platit
+$Bk=\O(w)$. Jeliko¾ strom má a¾~$B^h$ listù a nejvý¹e tolik vnitøních vrcholù,
+ukazatele zabírají $\O(h\log B)$ bitù, tak¾e pro vektory ukazatelù potøebujeme,
+aby bylo $Bh\log B=\O(w)$. Dobrá volba je napøíklad $B=k=\sqrt w$, $h=\O(1)$, èím¾
+získáme strukturu obsahující $w^{\O(1)}$ prvkù o~$\sqrt w$ bitech, která
+pracuje v~konstantním èase.
+
+\h{Q-Heap}
+
+Pøedchozí struktura má zajímavé vlastnosti, ale èasto je její pou¾ití
+znemo¾nìno omezením na~velikost èísel. Popí¹eme tedy o~nìco slo¾itìj¹í
+konstrukci od~Fredmana a Willarda \cite{fw90trans}, která doká¾e toté¾, ale s~a¾ $w$-bitovými èísly.
+Tato struktura má spí¹e teoretický význam (konstrukce je znaènì komplikovaná
+a skryté konstanty nemalé), ale pøekvapivì mnoho my¹lenek je pou¾itelných
+i prakticky.
\s{Znaèení:}
\itemize\ibull
-\: $k = \O(w^{1/4})$
-\: $r\le k$, poèet prvkù v Q-haldì
-\: $x_1 < \ldots < x_r$, prvky (o $w$ bitech) v Q-haldì
-\: $\X = (x_1,\ldots,x_r)$
-\: $c_i = \msb(x_i \oplus x_{i+1})$, nejvy¹¹í bit, na kterém se li¹í $x_i$ a
-$x_{i+1}$
-\: $\rank_\X(x)$, poèet prvkù mno¾iny $\X$, které jsou men¹í ne¾ $x$.
-Samotné $x$ ov¹em nemusí být prvek mno¾iny $\X$.
-\endlist
-
-Haldové operace budeme umìt v $\O(1)$, nicménì bude nutný preprocesing v èase
-$\O(2^{k^4})$, co¾ ov¹em není tak hrozné, jak na prní pohled vypadá, jeliko¾
-$k = \O(\root 4 \of {\log n})$, èili nakonec ho stihneme v lineárním èase.
-
-A jak to tedy vypadá? Prvky $x_1,\ldots,x_r$ budeme ukládat do tzv. trie.
-{\it Trie} je binární strom s prvky (daty) v listech, v na¹em pøípadì s
-hodnotami $x_1,\ldots,x_r$. Popí¹u konstrukci trie. Oznaèím $c = \max(c_i)$.
-Mno¾inu $\X$ rozdìlíme na dvì mno¾iny, podle hodnot prvkù na $c$-tém bitu v
-binárním zápisu: $$ \X_0 = \{ x_i \vert x_i \in \X\and x_i[c]=0 \}$$
-$$ \X_1 = \{x_i \vert x_i \in \X\and x_i[c]=1\}$$
-
-Tedy $$\forall x \in \X_1, \forall y \in \X_2: x < y$$
-
-Èíslo $c$ -- øíkejme mu znaèka -- vlo¾íme do koøene právì budovaného (pod)stromu
-a jako levý podstrom pøipojím strom, který vznikne stejnou oparací na mno¾inì
-$\X_ 0$, prièem¾ $c$ vybíráme jen pøes prvky $\X_0$. Pravý podstrom vznikne
-stejnì z mno¾iny $\X_1$. Pokud je ji¾ mno¾ina pouze jednoprvková, dále
-nepokraèujeme v dìlení a zbývající prvek vlo¾íme jako list. Hodnoty (data) jsou
-tak ulo¾eny v listech a ve vnitøích uzlech jsou znaèky.
-
-\s{Pøíklad:}
-
-\nosizefigure{trie.eps}{Trie. Ohodnocení hran je pouze pro názornost -- není
-souèástí trie.}
-
-\>Pozorování:
-\itemize\ibull
-\: Tvar stromu (oznaème ho $T$) je jednozaène urèen vektrorem
-$\vec c=(c_1,\ldots,c_r)$.
-\: Prvky jsou v trii umístìny vzestupnì zleva doprava.
+\:$k = \O(w^{1/4})$ -- omezení na~velikost haldy,
+\:$r\le k$ -- aktuální poèet prvkù v~haldì,
+\:$X=\{x_1, \ldots, x_r\}$ -- ulo¾ené $w$-bitové prvky, oèíslujeme si je tak, aby $x_1 < \ldots < x_r$,
+\:$c_i = \msb(x_i \oplus x_{i+1})$ -- nejvy¹¹í bit, ve~kterém se li¹í $x_i$ a
+$x_{i+1}$,
+\:$\rank_X(x)$ -- poèet prvkù mno¾iny~$X$, které jsou men¹í ne¾ $x$
+(pøièem¾ $x$ mù¾e le¾et i mimo~$X$).
\endlist
-To je sice v¹echno moc pìkné, ale pro aplikaci v Q-Heapech budeme muset umìt
-poèítat $\rank_\X(x)$ v konstatním èase. Jak tedy na to?
-
-\s{Lemma 1:} $\rank_\X(x)$ je urèen jednoznaènì:
+\s{Pøedvýpoèet:} Budeme ochotni obìtovat èas $\O(2^{k^4})$ na~pøedvýpoèet.
+To mù¾e znít hrozivì, ale ve~vìt¹inì aplikací bude $k=\log^{1/4} n$, tak¾e
+pøedvýpoèet stihneme v~èase $\O(n)$. V~takovém èase mimo jiné stihneme
+pøedpoèítat tabulku pro libovolnou funkci, která má vstup dlouhý $\O(k^3)$
+bitù a kterou pro ka¾dý vstup dovedeme vyhodnotit v~polynomiálním èase.
+Nadále tedy mù¾eme bezpeènì pøedpokládat, ¾e v¹echny takové funkce
+umíme spoèítat v~konstantním èase.
+
+\s{Iterování:} V¹imnìte si, ¾e jakmile doká¾eme sestrojit haldu s~$k$ prvky
+pracující v~konstantním èase, mù¾eme s~konstantním zpomalením sestrojit
+i haldu s~$k^{\O(1)}$ prvky. Staèí si hodnoty ulo¾it do~listù stromu
+s~vìtvením $k$ a konstantním poètem hladin a v~ka¾dém vnitøním vrcholu
+si pamatovat minimum podstromu a Q-Heap s~hodnotami jeho synù. Tak doká¾eme
+ka¾dé vlo¾ení i odebrání prvku pøevést na~konstantnì mnoho operací s~Q-Heapy.
+
+\s{Náèrt} fungování Q-Heapu:
+Nad~prvky $x_1,\ldots,x_r$ sestrojíme trii~$T$ a nevìtvící se cesty zkomprimujeme
+(nahradíme hranami). Listy trie budou jednotlivá $x_i$, vnitøní vrchol,
+který le¾í mezi $x_i$ a $x_{i+1}$, bude testovat $c_i$-tý bit èísla.
+Pokud budeme hledat nìkteré z~$x_i$, tyto vnitøní vrcholy (budeme jim
+øíkat {\I znaèky}\foot{tøeba turistické pro~orientaci v~lese}) nás správnì dovedou do~pøíslu¹ného listu. Pokud ale
+budeme hledat nìjaké jiné~$x$, zavedou nás do~nìjakého na~první pohled
+nesouvisejícího listu a teprve tam zjistíme, ¾e jsme zabloudili. K~na¹emu
+pøekvapení v¹ak to, kam jsme se dostali, bude staèit ke~spoèítání ranku
+prvku a z~rankù u¾ odvodíme i ostatní operace.
+
+\s{Pøíklad:} Trie pro zadanou mno¾inu èísel. Ohodnocení hran je pouze pro názornost, není
+souèástí struktury.
+\fig{trie.eps}{\hsize}
+
+\s{Lemma R:} $\rank_X(x)$ je urèen jednoznaènì kombinací:
\numlist\pnromanp
-\: stromem $T$
-\: èíslem $i$: x vede v $T$ do $x_i$
-\: vztahem mezi $x$ a $x_i$ -- my¹leno vzhledem k relacím $<,>,=$
-\: $\msb(x \oplus x_i)$
+\:tvaru stromu $T$,
+\:indexu $i$ listu $x_i$, do~kterého nás zavede hledání hodnoty~$x$ ve~stromu,
+\:vztahu mezi $x$ a $x_i$ ($x<x_i$, $x>x_i$ nebo $x=x_i$) a
+\:pozice $b=\msb(x \oplus x_i)$.
\endlist
-\s{Zdùvodnìní.} Pokud $x=x_i$, tak zjevnì $\rank_\X(x) = i$. Nech» tedy $x\neq
-x_i$. Hodnoty znaèek klesají ve smìru od koøene k
-listùm a na cestì od koøene k $x_i$ se v¹echny bity v $x_i$ na pozicích urèených
-znaèkami shodují s bity v $x$ -- tak jsme k danému $x$ ve (ii) vybrali $x_i$.
-Vezmeme do ruky $x$ a vydáme se na cestu od koøene do místa, kde bychom
-oèekávali $x$, kdyby v trii bylo. Jeliko¾ $\msb(x \oplus x_i)$ urèitì není
-znaèka na cestì z koøene do $x_i$ (v tom pøípadì by cesta podle znaèek nevedla
-do $x_i$ -- $x$ se na této pozici od $x_i$, vydali bychom se tedy do opaèné
-(shodující) vìtve), tak na této cestì je $\msb(x \oplus x_i)$ ostøe mezi
-nìjakými znaèkami, co¾ mi urèí hranu -- breakpoint, pod kterou u¾ jsou v¹echny
-hodnoty v listech buï men¹í (pokud $x>x_i$), nebo vìt¹í (pokud $x<x_i$), proto¾e
-na bitech vy¹¹ích, ne¾ je znaèka následující po breakpointu, mají v¹echny prvky
-v podstromì stejnou èíslici.
-
-\s{Pøíklad:} Vezmìme mno¾inu $\X=\{x_1,x_2,\ldots,x_6\}$ z pøedchozího pøíkladu
-a poèítejme $\rank_\X(011001)$. Bod zlomu -- breakpoint -- je oznaèen puntíkem.
-A $x>x_i$, tedy celý podstrom je men¹í ne¾ $x$ a tudí¾ $\rank_\X(011001)=4$.
+\proof Pokud $x=x_i$, je zjevnì $\rank_X(x) = i$. Pøedpokládejme tedy $x\ne x_i$.
+Hodnoty znaèek klesají ve~smìru od koøene k~listùm a na cestì od koøene k~$x_i$ se
+v¹echny bity v $x_i$ na~pozicích urèených znaèkami shodují s bity v $x$. Pøitom
+a¾ do~pozice $b$ se shodují i bity znaèkami netestované. Sledujme tuto cestu
+od~koøene a¾ po~$b$: pokud cesta odboèuje doprava, jsou v¹echny hodnoty
+v~levém podstromu men¹í ne¾~$x$, a~tedy se do~ranku zapoèítají. Pokud odboèuje
+doleva, jsou hodnoty v~pravém podstromu zaruèenì vìt¹í a nezapoèítají se.
+Pokud nastala neshoda a $x<x_i$ (tedy $b$-tý bit v~$x$ je nula, zatímco v~$x_i$
+je jednièkový), jsou v¹echny hodnoty pod touto hranou vìt¹í; pøi opaèné nerovnosti
+jsou men¹í.
+\qed
+
+\s{Pøíklad:} Vezmìme mno¾inu $X=\{x_1,x_2,\ldots,x_6\}$ z pøedchozího pøíkladu
+a poèítejme $\rank_X(011001)$. Místo první neshody je oznaèeno puntíkem.
+Platí $x>x_i$, tedy celý podstrom je men¹í ne¾ $x$, a~tak je $\rank_X(011001)=4$.
+
+Rádi bychom pøedchozí lemma vyu¾ili k~sestrojení tabulek, které podle uvedených
+hodnot vrátí rank prvku~$x$. K~tomu potøebujeme pøedev¹ím umìt indexovat tvarem
+stromu.
+
+\s{Pozorování:} Tvar trie je jednoznaènì urèen hodnotami $c_1,\ldots,c_{r-1}$
+(je to toti¾ kartézský strom nad tìmito hodnotami -- blí¾e viz kapitola o~dekompozicích
+stromù), hodnoty v~listech jsou $x_1,\ldots,x_r$ v~poøadí zleva doprava.
+
+Kdykoliv chceme indexovat tvarem stromu, mù¾eme místo toho pou¾ít pøimo vektor
+$(c_1,\ldots,c_r-1)$, který má $k\log w$ bitù. To se sice u¾ vejde do vektoru,
+ale pro indexování tabulek je to stále pøíli¹ (v¹imnìte si, ¾e $\log w$ smí být
+vùèi~$k$ libovolnì vysoký -- pro~$w$ známe pouze dolní mez). Proto reprezentaci
+je¹tì rozdìlíme na dvì èásti:
-\s{Znaèení:}
\itemize\ibull
-\: $\B = \{c_1,\ldots,c_k\}$
-\: $\varphi: \{1,\ldots,k\} \to \B, \varphi(i):=c_i$
+\:$B := \{c_1,\ldots,c_r\}$ (mno¾ina v¹ech pozic bitù, které trie testuje, ulo¾ená ve~vektoru setøídìnì),
+\:$C: \{1,\ldots,r\} \to B$ taková, ¾e $B[C(i)]=c_i$.
\endlist
-\s{Lemma 1':} $\rank_\X(x)$ lze spoèítat v konstatním èase z:
+\s{Lemma R':} $\rank_X(x)$ lze spoèítat v~konstantním èase~z:
\numlist\pnromanap
-\: $\B,\varphi$ -- tyto objekty urèují strom $T$
-\: $\equiv$ (ii), tj. èísla $i$: x vede v $T$ do $x_i$
-\: $\equiv$ (iii), tj. vztahu mezi $x$ a $x_i$ -- my¹leno vzhledem k relacím
-$<,>,=$
-\: $\rank_\B(\msb(x \oplus x_i))$
+\:funkce $C$,
+\:hodnot $x_1,\ldots,x_r$,
+\:$x[B]$ -- hodnot bitù na~\uv{zajímavých} pozicích v~èísle~$x$.
\endlist
-a v¹echny vý¹e uvedené body lze té¾ spoèítat v konstatním èase.
-\s{Zdùvodnìní.}
-
-\numlist\pnromanap
-\: Nic se nepoèítá, tak je strom ulo¾en.
-\:
+\proof Z~pøedchozího lemmatu:
+\numlist\pnromanp
+\:Tvar stromu závisí jen na~nerovnostech mezi polohami znaèek,
+ tak¾e je jednoznaènì urèený funkcí~$C$.
+\:Z~tvaru stromu a $x[B]$ jednoznaènì plyne list $x_i$ a tyto vstupy
+ jsou dostateènì krátké na~to, abychom mohli pøedpoèítat tabulku
+ pro prùchod stromem.
+\:Relaci zjistíme prostým porovnáním, jakmile známe~$x_i$.
+\:MSB umíme na~RAMu poèítat v~konstantním èase.
\endlist
-
-\>A teï konkrétnì, jak bude Q-Heap realizována:
-
-\>Pamatujeme si:
+Mezivýsledky (i)--(iv) jsou opìt dost krátké na~to, abychom jimi mohli
+indexovat tabulku.
+\qed
+
+\>Poèítání rankù je témìø v¹e, co potøebujeme k~implementaci operací
+\<Find>, \<Insert> a \<Delete>. Jedinou dal¹í pøeká¾ku tvoøí zatøiïování
+do~seznamu $x_1,\ldots,x_r$, který je moc velký na~to, aby se ve¹el
+do~$\O(1)$ slov. Proto si budeme pamatovat zvlá¹» hodnoty v~libovolném
+poøadí a zvlá¹» permutaci, která je setøídí -- ta se ji¾ do~vektoru vejde.
+Øeknìme tedy poøádnì, co~v¹e si bude struktura pamatovat:
+
+\s{Stav struktury:}
\itemize\ibull
-\: $\check x_1,\ldots,\check x_2$, hodnoty v libovolném poøadí
-\: $\rho:$ permutace na $\{1,\ldots,k\}$ urèující $x_i = \check x_{\rho(i)}$ pro
-$1 \le i \le r$, platí $x_1 < \ldots < x_r$
-\: $r$, poèet prvkù
-\: $B$, mno¾ina ``zajímavých'' bitových pozic, reprezentovaná jako vektor
-\: $R$, vektor popisující funkci $\varphi: \{1,\ldots,k\} \to \{1,\ldots,k\}$, t.¾.
-$B[\varphi(i)] = c_i$
+\:$k$, $r$ -- kapacita haldy a aktuální poèet prvkù (èísla),
+\:$X=\{x_1,\ldots,x_r\}$ -- hodnoty prvkù v libovolném poøadí (pole èísel),
+\:$\varrho$ -- permutace na~$\{1,\ldots,r\}$ taková, ¾e $x_i=X[\varrho(i)]$
+ a $x_1<x_2<\ldots<x_r$ (vektor o~$r\cdot\log k$ bitech),
+\:$B$ -- mno¾ina \uv{zajímavých} bitových pozic (setøídìný vektor o~$r\cdot\log w$ bitech),
+\:$C$ -- funkce popisující znaèky: $c_i=B[C(i)]$ (vektor o~$r\cdot\log k$ bitech),
+\:pøedpoèítané tabulky pro rùzné funkce.
\endlist
-\> A teï si ji¾ uká¾eme dvì základní operace -- {\it insert} a {\it delete}.
+\>Nyní ji¾ uká¾eme, jak provádìt jednotlivé operace:
-\s{Insert(x)}
+\>$\<Find>(x):$
\algo
-\: $i = \rank_\X(x)$
-\: porovnáme $x,x_i$
-\: zaøadíme $x$ do $x_1,\ldots,x_r, r++$
-\: spoèítáme $c_i',c_{i+1}'$
-\: update $B,R$
+\:$i \leftarrow \rank_X(x)$.
+\:Pokud $x_i=x$, odpovíme {\sc ano,} jinak {\sc ne.}
\endalgo
-\s{Delete(x)}
+\>$\<Insert>(x):$
\algo
-\: $i = \rank_\X(x)$, pøedpokládáme $x=x_i$, tedy ¾e prvek v haldì je
-\: sma¾eme $x_i$ (uvolnìní $\check x_{\rho(i)}$, se¹oupnutí $\rho$); $r--$
-\: rozhodneme, jestli zmizí $c_i$, nebo $c_{i+1}$
-\: update $B$ (dle výsledku pøedchozího kroku), update $R$ (se¹oupnutí)
+\:$i \leftarrow \rank_X(x)$.
+\:Pokud $x=x_i$, hodnota u¾ je pøítomna.
+\:Ulo¾íme $x$ do~$X[\mathop{{+}{+}}r]$ a vlo¾íme $r$ na~$i$-té místo v~permutaci~$\varrho$.
+\:Pøepoèítáme $c_{i-1}$ a $c_i$. Pro ka¾dou zmìnu $c_j$:
+\::Pokud je¹tì nová hodnota není v~$B$, pøidáme ji tam.
+\::Upravíme $C(j)$, aby ukazovalo na~tuto hodnotu.
+\::Pokud se na~starou hodnotu neodkazuje ¾ádné jiné $C(\cdot)$, sma¾eme ji z~$B$.
\endalgo
+\>$\<Delete>(x):$
+
+\algo
+\:$i \leftarrow \rank_X(x)$ (víme, ¾e $x_i=x$).
+\:Sma¾eme $x_i$ z~pole~$X$ (napøíklad prohozením s~posledním prvkem) a pøíslu¹nì upravíme~$\varrho$.
+\:Pøepoèítáme $c_{i-1}$ a $c_i$ a upravíme $B$ a $C$ jako pøi Insertu.
+\endalgo
+
+\s{Èasová slo¾itost:} V¹echny kroky operací po~výpoètu ranku trvají konstantní èas, rank
+samotný zvládneme spoèítat v~$\O(1)$ pomocí tabulek, pokud známe $x[B]$. Zde je ov¹em
+nalíèen háèek -- tuto operaci nelze na~Word-RAMu konstantním poètem instrukcí spoèítat.
+Pomoci si mù¾eme dvìma zpùsoby:
+
+\numlist\nalpha
+\:Vyu¾ijeme toho, ¾e operace $x[B]$ je v~${\rm AC}^0$, a vystaèíme si se strukturou pro ${\rm AC}^0$-RAM.
+Zde dokonce mù¾eme vytváøet haldy velikosti a¾ $w\log w$. Také pøi praktické implementaci mù¾eme vyu¾ít
+toho, ¾e souèasné procesory mají instrukce na~spoustu zajímavých ${\rm AC}^0$-operací, viz napø. pìkný
+rozbor v \cite{thorup:ac0}.
+\:Jeliko¾ $B$ se pøi jedné Q-Heapové operaci mìní pouze o~konstantní poèet prvkù, mù¾eme
+si udr¾ovat pomocné struktury, které budeme umìt pøi lokální zmìnì~$B$ v~lineárním èase
+pøepoèítat a pak pomocí nich indexovat. To pomocí Word-RAMu lze zaøídit, ale je to technicky
+dosti nároèné, tak¾e ètenáøe zvìdavého na~detaily odkazujeme na~èlánek \cite{fw90trans}.
+\endlist
+
+\h{Aplikace Q-Heapù}
+
+Jedním velice pìkným dùsledkem existence Q-Heapù je lineární algoritmus na~nalezení
+minimální kostry grafu ohodnoceného celými èísly. Získáme ho z~Fredmanovy a Tarjanovy
+varianty Jarníkova algoritmu (viz kapitoly o~kostrách) tak, ¾e v~první iteraci pou¾ijeme
+jako haldu Q-Heap velikosti $\log^{1/4} n$ a pak budeme pokraèovat s~pùvodní Fibonacciho
+haldou. Tak provedeme tolik prùchodù, kolikrát je potøeba zlogaritmovat $n$,
+aby výsledek klesl pod~$\log^{1/4} n$, a~to je konstanta. V¹imnìte si, ¾e by nám
+dokonce staèila halda velikosti $\Omega(\log^{(k)} n)$ s~operacemi v~konstantním èase
+pro nìjaké libovolné~$k$.
+
+\references
\bye
projects / ga.git / blobdiff