\def\msb{{\rm MSB}}
\def\rank{{\rm Rank}}

\def\pnromanp{(\nroman)}
\def\pnromanap{(\nroman ')}

\input ../sgr.tex

\prednaska{8}{Q-Heaps}{}

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.

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é.

\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{Word-Encoded B-Tree}

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})$ -- 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

\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
\: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

\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:

\itemize\ibull
\:$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 R':} $\rank_X(x)$ lze spoèítat v~konstantním èase~z:
\numlist\pnromanap
\:funkce $C$,
\:hodnot $x_1,\ldots,x_r$,
\:$x[B]$ -- hodnot bitù na~\uv{zajímavých} pozicích v~èísle~$x$.
\endlist

\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
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
\:$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 r$ bitech),
\:pøedpoèítané tabulky pro rùzné funkce.
\endlist

\>Nyní ji¾ uká¾eme, jak provádìt jednotlivé operace:

\>$\<Find>(x):$

\algo
\:$i \leftarrow \rank_X(x)$.
\:Pokud $x_i=x$, odpovíme {\sc ano,} jinak {\sc ne.}
\endalgo

\>$\<Insert>(x):$

\algo
\:$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
