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

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.

\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)$.

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

\h{Q-Heaps}

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. 

\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.
\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ì:
\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)$
\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$. 

\s{Znaèení:}
\itemize\ibull
\: $\B = \{c_1,\ldots,c_k\}$
\: $\varphi: \{1,\ldots,k\} \to \B, \varphi(i):=c_i$
\endlist

\s{Lemma 1':} $\rank_\X(x)$ lze spoèítat v konstatní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))$
\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.
\: 
\endlist

\>A teï konkrétnì, jak bude Q-Heap realizována:

\>Pamatujeme si:
\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$
\endlist

\> A teï si ji¾ uká¾eme dvì základní operace -- {\it insert} a {\it delete}.

\s{Insert(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$
\endalgo

\s{Delete(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í)
\endalgo

\bye
