\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.
+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Ä\8dÃtaÄ\8d, pojÄ\8fme si ukázat, jaké datové struktury na~nÄ\9bm 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é.
+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$).
+\s{Značení:} $w$~bude vždy značit šířku slova RAMu a $n$~velikost vstupu algoritmu,
+v~nÄ\9bmž datovou strukturu využÃváme (speciálnÄ\9b 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.
+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é
+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)$.
+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.
+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Å\99Ãklad $B=k=\sqrt w$, $h=\O(1)$, Ä\8dÃ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
+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í:}
+\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
+\:$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$).
+\:$\rank_X(x)$ -- poÄ\8det prvků množiny~$X$, které jsou menÅ¡Ã než $x$
+(pÅ\99iÄ\8demž $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.
+\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Ä\9b, ale ve~vÄ\9btÅ¡inÄ\9b 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Ä\9bte 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í:
+\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,
+\: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¹í.
+\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$.
+\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
+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.
+\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:
+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$.
+\:$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:
+\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$.
+\:$x[B]$ -- hodnot bitů na~\uv{zajímavých} pozicích v~čísle~$x$.
\endlist
-\proof Z~pøedchozího lemmatu:
+\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.
+\: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
+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:
+\>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Å\99adà a zvlášť permutaci, která je setÅ\99Ã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)]$
+\:$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 k$ bitech),
-\:pøedpoèítané tabulky pro rùzné funkce.
+\:$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 k$ bitech),
+\:předpočítané tabulky pro různé funkce.
\endlist
-\>Nyní ji¾ uká¾eme, jak provádìt jednotlivé operace:
+\>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.}
+\: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.
-\::Upravíme ostatní prvky~$C$, ukazující na hodnoty v~$B$, které se vlo¾ením posunuly.
-\::Pokud se na~starou hodnotu neodkazuje ¾ádné jiné $C(\cdot)$, sma¾eme ji z~$B$.
+\: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.
+\::Upravíme ostatní prvky~$C$, ukazující na hodnoty v~$B$, které se vložením posunuly.
+\::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.
+\:$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:
+\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ý
+\: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}.
+\:Jelikož $B$ se pÅ\99i jedné Q-Heapové operaci mÄ\9bnà pouze o~konstantnà poÄ\8det 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ù}
+\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$.
+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
projects / ga.git / blobdiff