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