ADŠ prednáška 07: Deque. Binárna halda a heapsort.

Zhrnutie prednášky

Prednáška sa najprv vracia k vektoru s amortizovane konštantným pridávaním prvkov a ukazuje, že na ňom možno jednoducho postaviť zásobník a frontu. Hlavnou témou je dátová štruktúra deque (double-ended queue), ktorá je implementovaná ako cyklické pole s indexmi začiatku a konca. Umožňuje indexovanie v konštantnom čase a pridávanie aj odoberanie prvkov na oboch koncoch. Pri zaplnení sa pamäť zdvojnásobí a prvky sa prekopírujú, takže vkladanie ostáva v amortizovanom konštantnom čase. Praktické využitie deque je zriedkavé, typickým príkladom je najkratšia cesta v grafe s hranami váhy 0 a 1, napríklad pri hre Sokoban. Záver prepisu naznačuje prechod k binárnej halde a heapsortu.

• - Vektor pridáva prvky na koniec v amortizovanom konštantnom čase a vhodne nahrádza spájané zoznamy pri zásobníku a fronte.
• - Deque (double-ended queue) umožňuje push a pop na začiatku aj na konci a zároveň indexovanie ako pole.
• - Implementácia je cyklické pole s indexmi začiatku a konca; fyzický index sa počíta ako (Z + logický index) mod N.
• - Pri zaplnení sa pamäť zdvojnásobí a prvky sa prekopírujú od logického začiatku, takže vkladanie je amortizovane O(1).
• - Deque má väčšiu réžiu ako vektor, preto sa používa len tam, kde sú potrebné jeho operácie na oboch koncoch.
• - Príklad použitia: najkratšia cesta v grafe s hranami váhy 0 a 1 (napr. Sokoban), kde hrany s nulovou cenou idú na začiatok a ostatné na koniec fronty.

Zhrnutie pripravené s pomocou AI z prepisu videa.