Datové struktury 1

Datové struktury 1 - NTIN066 - ZS 2014/2015

3. úkol

Termín odevzdání: 8. prosince 2014.

Způsob odevzdání: odesláním do CodExu a odesláním v příloze emailem na ds1@kam.mff.cuni.cz.

Pravidla

Veškerý odevzdaný kód musí být originální tedy vytvořen vámi bez jakékoliv vedlejší "inspirace".
Svůj kód s nikým nesdílejte, aby se váš kód nestal něčí "inspirací". Výjimku tvoří odevzdání kódu.
Úkol a možné postupy řešení můžete probírat s ostatními, avšak respektuje výše uvedené o nesdílení kódu.
Řešení, která nejsou ve shodě s těmito pravidly, nebudou hodnocená.

Popis problému

Naimplementujte líné binomiální haldy. Napište program, který přečte ze vstupu testovací data a vypíše mazané minimum při každé operaci Delete-Min. Vstupní data jsou rozdělená na běhy, každý běh sestává z posloupnosti operací Insert a Delete-Min. Řádky Insert začínají písmenem I, řádky Delete-Min začínají písmenem D, poslední řádek běhu obsahuje písmeno R. Za posledním během je řádek s písmenem X. Vkládané prvky tvoří interval [0,n-1]. Po každém běhu se strom vyprázdní. Výstup jednotlivých běhů by měl být oddělen prázdnou řádkou.

Pomocí unixového programu /afs/ms.mff.cuni.cz/u/k/koucky/ds1/pbl3-gen-data dostupného v laboratoři Rotunda vygenerujte zkušební data, spusťte na nich své programy a pro každý běh změřte celkový počet S slití stromů během Delete-Min, počet N operací Insert a počet D operací Delete-Min. Pro každá vstupní data zaneste naměřené hodnoty do grafu, kde na ose x bude vyneseno N a na ose y bude vyneseno (S-min(S,N))/D, to jest graf průměrného počtu slití normalizovaného počtem vložených prvků. Výsledný graf by měl obsahovat pět křivek, pro pět různých testovacích dat. Podejte stručné vysvětlení tvaru naměřených křivek.

Příklad vstupu

I 1 
I 3
D
I 2
D
I 0
R
I 2
I 3
I 0
I 1
D
R
X

Výstup

Náčrt možného grafu

Generování zkušebních dat

$/afs/ms.mff.cuni.cz/u/k/koucky/ds1/pbl3-gen-data XX D

vygeneruje data pro měření, kde XX jsou poslední dvě číslice z vašeho studentského čísla a D je jedno z {0,1000,10000,100000,1000000}. Když D=0, data provádí Delete-Min na všechna vložená čísla až po všech operacích Insert, když D>0, data provedou D operací Delete-Min rovnoměrně rozmístených mezi N operací Insert. Velikost běhu začíná na 1 000 vložených prvcích a roste až do 1 000 000 prvků. Je cca 300 běhů. Příklad spuštění:

pbl3-gen-data 72 0       | moje-hlada 
pbl3-gen-data 72 1000    | moje-hlada 
pbl3-gen-data 72 10000   | moje-hlada 
pbl3-gen-data 72 100000  | moje-hlada 
pbl3-gen-data 72 1000000 | moje-hlada

Výsledky

Výsledky jednotlivých lidí jsou zaznamenány u výsledků úlohy 1.