Úlohy na procvičení
Cyklická fronta v poli
Na přednášce jste viděli implementaci cyklické fronty v poli (fronta.py).
Pokud dojde k přeplnění kapacity fronty, implementace z přednášky 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.
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ů).