1. (nalezení prvních $\sqrt{n}$ nejmenších čísel)
    Dostaneme pole $n$ prvků $\ARRAY{A}{1,\dots, n}$. Najděte algoritmus, který vypíše prvních $\sqrt{n}$ nejmenších čísel. Umíte to v čase $\OO(n)$?

    Nápověda: čtverec.

  2. (Max-heap)
    Vymyslete podobnou datovou strukturu jako je halda, ale tentokrát chceme odebírat prvek s největší hodnotou.

  3. (Heapsort)
    Zkuste vymyslet jednoduchý třídící algoritmus využívající haldy. Jaká bude jeho časová složitost v nejhorším případě? Umíte ho realizovat tak, abychom potřebovali pouze to pole, ve kterém dostaneme vstup?

  4. ($d$-regulární halda)
    Binární halda je halda, kde má každý vrchol nejvýše dva syny. V $d$-regulární haldě má každý vrchol nejvýše $d$ synů. Zkuste zobecnit binární haldu na $d$-regulární haldu. Jak se $d$-regulární halda uloží do pole? Na které pozici budou synové vrcholu z pozice $k$? Na jaké pozici bude jeho otec? Jak se změní implementace haldových operací? Jaká bude jejich časová složitost?

  5. (Kalendář událostí)
    Jak byste realizovali kalendář událostí? Kalendář událostí funguje podobně jako váš diář. Průběžně dostáváme úlohy, které mají přesně stanovený čas, kdy se mají vykonat. Můžeme je dostávat v libovolném pořadí, tedy ne nutně seřazené podle času. Úlohy zpracováváme v pořadí podle času. Při zpracovávání úlohy se dozvíme, jaké další úlohy přibyly. Občas naopak zjistíme, že máme nějakou naplánovanou úlohu zrušit, případně ji přeplánovat na jiný čas.

    Při realizaci se stačí zamyslet nad následujícími funkcemi: Odebrání úlohy, která je na řadě. Přidání nové úlohy, smazání a přeplánování konkrétní úlohy.

  6. (Využití reprezentace binárního stromu v poli)
    Napište co nejrychlejší program, který čte ze vstupu morseovku a překládá ji do anglické abecedy. Využijte při tom vyhodnocovacího stromu z následujícího obrázku.1 Binární strom na obrázku je netradičně nakreslený jako tabulka.

    Při vyhodnocování kódu písmene v morseovce (například .-) začneme v prvním řádku (v kořenu stromu). Pokud je první znak tečka, přesuneme se o řádek níže doleva. Pokud je první znak čárka, přesuneme se o řádek níže doprava. Dostali jsme se do dalšího vrcholu stromu. Tento postup opakujeme, dokud nezpracujeme všechny znaky aktuálního písmene v morseovce. Skončíme ve vrcholu označeném písmenem, které odpovídá Morseovu kódu.

    Binární vyhodnocovací strom si reprezentujte v poli, například jako řetězec $\sqcup$ETIANMSURWDKGOHVF$\sqcup$L$\sqcup$PJBXCYZQ$\sqcup\sqcup$, kde $\sqcup$ představuje mezeru. Předpokládejte, že vstup obsahuje pouze znaky ., -, | a že je celý vstup je ukončen znakem $. Tak ....|---|-..|-.|.||...|-|.|...|-|...


    Nápověda: Jediný cyklus $+$ stavový automat pamatující si pozici ve vyhodnocovacím stromě.