Q-haldy: Jeste jedna zmena formatu vektoru.

[ga.git] / 8-qheap / 8-qheap.tex

diff --git a/8-qheap/8-qheap.tex b/8-qheap/8-qheap.tex
index 46ebdc5e19d2e50de93d6e9f2d60f746e010262a..5ca980a82b90a351085986ad3c5293715d836e92 100644 (file)
--- a/8-qheap/8-qheap.tex
+++ b/8-qheap/8-qheap.tex
@@ -93,9 +93,9 @@ nesouvisej
 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.
 
-\ss{Pøíklad:}
-\figure{trie.eps}{Trie. Ohodnocení hran je pouze pro názornost, není
-souèástí struktury.}{\hsize}
+\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
@@ -125,17 +125,19 @@ R
 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_n$
+\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_n$ v~poøadí zleva doprava.
+stromù), hodnoty v~listech jsou $x_1,\ldots,x_r$ v~poøadí zleva doprava.
 
-Kdykoliv chceme indexovat tvarem stromu, mù¾eme tedy indexovat pøímo vektorem
-$(c_1,\ldots,c_n)$, který má pouze $k\log w=\O(k^2)$ bitù. Pro zjednodu¹ení ostatních
-operací ale zvolíme trochu jinou, ekvivalentní reprezentaci:
+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: B[C(i)]=c_i$.
+\:$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:
@@ -171,9 +173,9 @@ po
 \:$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 r$ bitech),
+  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),
+\:$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