6. cvičení: Halda a prioritní fronta

0:00 Odpovědník.
0:05 Pojmový oblak. Poslední řada.
0:15 6.1: haldy. Promítat, postupně procházet.
0:20 6.2: všemožné haldy. Dvojice. Napsat na tabuli možnosti pro 6.3.
0:25 6.3: min-max. Dát možnosti, 2 minuty na rozmyšlení, pak hlasovat. Podle času je možné zařadit diskuzi. - 2^{h-1}+1 - 2^{h+1} - 2^{h+1}-1 - 2^h
0:30 6.4: pole. Každý sám, pak tabule, bc společně.
0:34 6.5: nejmenší prvek v max haldě.
0:35 6.6: ověření korektnosti haldy. Dvojice. Říct, že chceme mít funkce Parent, Left a Right. Po 5 minutách promítnout tyto pomocné funkce. Ukázat složitost BuildMaxHeap a zdůraznit, že tohle je klíčové pozorování.
0:50 6.7: sestavení haldy. Tabule, studenti postupně chodí. Pak mazání.
1:05 6.8: Bottom-Heapify, BuildHeap. Diskuze ve dvojicích, pak merge a diskuze ve čtveřicích. Napsat tabulku k 6.9 na tabuli.
1:25 6.9: tabulka. Nechat říkat, Honza píše na tabuli.

Pokud zbude čas

HeapSort se dá nechat na doma, důkaz složitosti BuildMaxHeap spíš ne. Výše popsaný průběh je reálný průběh v semestru jaro 2019.