Datové struktury I - 3. úkol

Termín odevzdání: 27. listopadu 2016.
Způsob odevzdání: Odevzdáním na stránce https://kam.mff.cuni.cz/~ds1/.
Obecná pravidla: Prečtěte si je důkladně

Popis problému

Naimplementujte dvě varianty Fibonacciho haldy, standardní variantu z přednášky a naivní variantu, která nepoužívá značkování vrcholů a operace Decrease-key pouze odpojí daný vrchol od otce (tj. nepokračuje v odpojování otce od dědy).
Výsledek naivní operace Decrease-key

Prozkoumejte chování obou datových struktur na testovacích datech vygenerovaných níže popsaným programem.

  • náhodný rovnoměrný test: posloupnost operací obsahuje přibližně stejný počet operací Insert, Delete-min a Decrease-key;
  • nevyvážený test: počet operací Decrease-key je podstatně větší než počet operací Delete-min;
  • zákeřný test: posloupnost operací proti naivní verzi.

Vaším úkol je změřit průměrný počet kroků vyžadující operace Delete-min. Krokem v operaci Delete-min rozumíme přesun syna od smazaného otce do seznamu haldových stromů a spojení dvou stromů při následné konsolidaci.

Generování dat

Pro vygenerování testovacích dat si stáhněte generátor. Spusťte ho s následujícími parametry:
  • -s XX, kde XX jsou poslední dvě číslice vašeho studentského čísla;
  • -r, pro vygenerování náhodného rovnoměrného testu;
  • -b, pro vygenerování nevyváženého testu;
  • -x, pro vygenerování zákeřného testu.

Výstupem generátoru bude textový soubor, ve kterém každý řádek popisuje jednu operaci na stromu:

  • # N : začátek testu s N prvky – zrušte původní haldu a založte novou (velikost množin se vám může hodit při kreslení grafů);
  • INS E K: vložení prvku s identifikátorem E a klíčem (prioritou) K do haldy
  • DEL: smazání prvku s nejmenším klíčem z haldy (pokud je více prvků s nejmenším klíčem, pak smažte jeden libovolný prvek)
  • DEC E K: snížení klíče prvku s identifikátorem E na hodnotu K (pokud prvek E není uložen v haldě nebo klíč je menší než K, pak operaci ignorujte)

Na jedno spuštění generátor vytvoří sadu testů s maximálně 2 000 000 prvků. Identifikátor prvku je celé číslo od 0 do N-1. Operace Insert nikdy nevkládá prvek s identifikátorem, který v haldě aktuálně je, ale identifikátory se mohou recyklovat (po smazání může být stejný prvek znovu vložen).

Výstupní grafy

Nakreslete následující grafy závislostí průměrného počtu kroků operace Delete-min na hodnotě N.
  1. Graf obsahující dvě křivky porovnávající počet kroků operace Delete-min standardní verze Fibonacciho stromu, jedna křivka pro rovnoměrný test a druhá pro nevyvážený test. Vysvětlete rozdíl mezi těmito testy.
  2. Graf obsahující dvě křivky porovnávající počet kroků operace Delete-min standardní a naivní verze Fibonacciho stromu v zákeřném testu.

Příklad vstupu

# 4
INS 0 3
DEC 0 0
DEL
INS 1 2
DEC 1 0
DEL
INS 2 1
DEC 2 0
INS 3 3
# 5
INS 0 3
DEL
DEC 0 0
INS 1 1
DEC 1 0
DEL
INS 2 4
INS 3 4
DEC 3 0
DEC 2 0
DEL
DEL
INS 2 2