Úlohy na procvičení
Validní uzávorkování (jednoduchá varianta)
O posloupnosti závorek (, ) rozhodněte, jestli je to validní uzávorkování.
Například: ()(()) a ()((()())()) jsou validní, ale ((()( ani ()(())) nejsou.
Operace nad haldou
Na přednášce jste viděli datovou strukturu minimová binární halda, která měla následující operace:
insert– přidat prvek do haldy,min– vrátit minimální prvek (ale nechat ho v haldě),extract_min– odebrat minimální prvek.
Při implementaci v poli měly operace insert a extract_min časovou složitost \(\mathcal{O}(\log n)\), kde \(n\) je počet prvků v haldě. Zjištění minima trvalo jen konstantní čas.
Rozmyslete, jak přidat ještě operace:
decrase– zmenšení hodnoty prvku v haldě,delete– odstranění libovolného prvku.
U obou operací předpokládejte, že máte index daného prvku (tedy jeho pozici v poli, ve kterém je halda uložena) a nemusíte prvek hledat.
Zvládnete obě operace v čase \(\mathcal{O}(\log n)\)?
Nápověda
Vzpomeňte si, že při implementaci haldy v poli jsme používali ještě dvě pomocné operace. Při vkládání to bylo bubble_up (dokud daný prvek porušuje haldové uspořádání, prohazuj ho s jeho rodičem), při odebírání minima bubble_down (dokud daný prvek porušuje haldové uspořádání, prohazuj ho s menším z jeho synů).
Cyklická fronta v poli
Na přednášce jste viděli implementaci cyklické fronty v poli (fronta.py).
Problém této implementace je, že přestane fungovat, pokud dojde k přeplnění kapacity fronty (vyvolá výjimku).
Tento problém lze řešit alokací většího pole a (případným) kopírováním uložených hodnot.
Upravte odpovídajícím způsobem implementaci.
Spojové seznamy
Pokud už máte úlohy výše hotové, vraťte se k úlohám na spojové seznamy z předchozího cvičení, zejména k úloze v ReCodExu.