\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 \& Union-Find problem}{zapsali Cyril Strejc a Ale¹
©nupárek}

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



\h{Union-Find problem}
Na Uion-Find problem (UF) mù¾eme nahlí¾et ze více stran (udr¾ování ekvivalencí, 
inkrementální souvislost grafu). K èemu je to dobré? 
Napøíklad v Kruskalovì algoritmu pro hledání minimálních koster v grafu.
\h{Udr¾ování tøíd ekvivalence }
Mìjme nìjakou mno¾inu M, která se dá rozlo¾it na k ekvivalentních podmon¾in (tøídy ekvivalence). Na mno¾iòe M chceme provádìt 
dvì operace: jsou p,q z M ekvivalentní (ve stejné tøídì ekvivalence)? (find(p,q)) Dále chceme umìt spojit dvì tøídy ekvivalence do jedné (union(p,q)).
\h{Inkrementální idr¾ování komponent souvislosti grafu}
Jedná se o pøipad podobný udr¾ování tøíd ekvivalence. Tentokrát mnou¾inou M bude mno¾ina vrcholù V grafu G (V,E). 
Za »øídy ekvivalence budou jednotlivé komponenty souvislosti grafu G. Operace find nám øekne o dvou vrcholech nachází-li
se ve stejné komponen»e, èi nikoliv. Operace union nám spojí dvì komponenty do jedné pøidáním hrany. Pokud pøipustíme mazání hran, 
øe©ení problému je výraznì te¾¹í.

\h{Bì¾ná implementace }
Ka¾dé tøídì ekvivalence pøiøadíme unikátní barvu, kterou obarvíme její prvky. Pro operaci find staèí porovnat barvy prvkù. 
Pro operaci union dvou komponent je nutné pøebarvit obì na stejnou barvu. Budeme pøebarvovat 
v¾dy tu men¹í pak celková operace union bude trvat $\O(n\log(n) + m)$. (Ka¾dé pøebarvení minimálnì zdvojnásobí velikost nové komponenty.)
\h {Chytøej¹í implementace }
Budeme-li prvky za stejné tøídy reprezentovat ve jednom stromì (synové mají ukazatel svého otce), operaci find
provedeme prùchodem ze zadaných prvkù do koøene. Prvky jsou ve stejné komponentì souvislosti, pokud mají stejného otce.
Operace union bude spojení dvou stromù do jednoho (otec jednoho stromu se zavìsí pod listy druhého). 
Takto definovaný union nemusí garantovat logaritmickou slo¾itost pro find, 
v extrémním pøipadì mù¾e strom mít lineární hloubku vzhledem k poètu vrcholù.

Degeneraci stromu lze zabránit pøidánim podmínky urèující, jaký strom bude dole.
První mmo¾nost (union by size) je povìsit dolu vìtsí strom.
Druhá mo¾nost (union by rank) je ka¾dému vrcholu nastavit na zaèátku nìjaký rank (tøeba 1). Pokud je $r1<r2$ pak strom s r1 povìsíme dolu.
Pokud $r1=r2$ pak ve slouèeném stromù zvý¹íme v koøeni rank o 1. Informace o ranku nám zabere ménì pamìti ne¾ o velikosti stromu.

Dal¹i mo¾nost pro zkrácení vý¹ky stromu je path compression. Pøi operaci find si pamatujeme pro¹lé vrcholy a pøesmìrujeme 
jejich ukazatele na otce na koøen.

\s{Vìta: } UF s Union by size nebo Union by rank s path compression mají amortizovanì 
slo¾itost $\O(n\alpha(n))$, kde $\alpha(n)$ je inverzní funkce k Ackermanovì funkci. ($\alpha(poèet atomù ve vesmíru)=5$)

\h {Microtree/Macrotree decomposition}

\s{Otázka: } Je mo¾né provádìt UF v lep¹ím èase kdy¾ bude pøedem znám výsledný strom?

Cíl: UF lze za pomoci preprocesingu v èase $\O(n)$  zvládnout amortizovanì v èase $\O(1)$ na U,F.

\h{Clusterizace}
\s {Definice: } Nech» G je je graf kde $\forall v \in V(G): deg(v)<=3$ a $c \in N$ pak c-clusterizací grafu G je rozklad
G na podgrafy na podgrafy G1,G2 ... Gk s následujícimi vlastnostmi:
\itemize\ibull
\: $\forall v  \in V \exists !\ i: v \in C_i$
\: $\forall i\  C_i\leq C$
\: $\forall i$ vnìj¹i stupeò $C\leq3$, pokud $C_i=3$ pak $\|C_i\|=1$
\: ¾ádné dva sousední clustery nelze spojit
\endlist

Co udìlat se stromem, ve kterém existuje vrchol se stupnìm vìt¹im ne¾ 3? Pou¾ijeme French trick.
V¹echny vrcholy s vy¹¹im stupnìm jak 3, rozdìlíme na více vrcholù se stupnìm 3 spojených cestou. 
Tato ùprava nám asymptoticky nezmìní èasovou slo¾itost UF o proti pùvodnímu stromu.


\s{Lemma: } Pro ka¾dou C-clusterizaci n-vrcholového stromu je  $\O(n/C)$ clusterù.

\s{Vìta: } Pro ka¾dé C lze C-clusterizaci (splòujíci pøedchozí lemma) najít v èase $\O(n)$.

\s{Dùkaz: } za pomoci DFS ...
\h{Jednodu¹¹í clusterizace}
Pøedpokládejme, ¾e máme zakoøeòené stromy
\s{Definice: } Koøeny makrostromù jsou nejvy¹¹i vrcholy, pod kterými je maximálnì $\log(n)$ listù.
Celá clusterizace se nám rozpadne na následujíci pøipady: 
\itemize\ibull
\:N-strom: (má stupeò 1)
\:M-strom: (má stupeò 2)
\:cestu: ka¾dá cesta se popí¹e bitovým polem, jednotlivé úseky se poí¹í jednotlivými slovy
\endlist
poèet listù v makrostromu je maximálnì $n/\log(n)$ z toho vyplývá, ¾e vý¹ka makrostromu $\O(n/log(n))$

\s{Co si potøebujeme pamatovat}
\itemize\ibull
\: $\log(n)$ na clusterizaci
\: makrostrom  G s $C_i$ zkontrahovanými pro deg 1,3 do vrcholu a deg 2 do hrany, jeho velikost je $\O(n/\log(n))$
\:mikrostromy, bitovì popsány
\endlist

\h{Makrostromy}
V makrostromu jsou takové hrany, které vedly v pùvodním stromu mezi clustery, vrcholy budou hranièní
vrcholy pøislu¹ných clusterù, cluster stupnì 1 je v novém stromì list, cluster stupnì 2 nahradíme 
hranou mezi hranièními vrcholy a cluster stupòe 3 má jeden vnìj¹í vrchol, který je také v novém stromì.

\s{find(x,y)}
\algo
nech» $i,j: x \in C_i, y \in C_j$
\:pokud $i=j$, ptáme se v $C_i$ (mikro-find(i,j))
\:pokud $i\not = j$, najdeme hranièní vrcholy pøíslu¹ných clusterù, tj. $h_i \in C_i, h_j \in C_j$ a provedeme makro-find($h_i$,$h_j$)
	find($i$,$j$):=makro-find($h_i$,$h_j$) and mikro-find($i$,$h_i$) and mikro-find($j$,$h_j$);
\endalgo

\s{delete(x,y)}
\algo
\: pokud $x,y$ je makro-hrana, sma¾eme ji
\: pokud $x,y \in C_i$  pak mikro-delete v $C_i$, pokud je $deg(C_i)=2$ a find($h_1$,$h_2$)==FALSE ($h_1, h_2$hranièní vrcholy), 
pak makro-delete hrany odpovýdajíci $C_i$. ($C_i$ je neprùchodná)
\endalgo
\h{Mikrostromy}
\itemize\ibull
\: strom zakoøením a oèísluji mu hrany $0..h <  \log(n)$
\: pamatujeme si: \itemize\ibull  
  \:$\forall v \in C_i$ mno¾inu hran $P_v$ na cestì do koøene v (bitový vektor)
  \:mon¾inu smazaných hran, operace delete pøidá hranu do mno¾iny
  \:hranièní vrcholy
  \endlist
\: $P_x \oplus  P_y$ je cesta z x do y
\endlist
\bye

