Heap a Základy rekurze

Programovani 2 Matematici, teoreticke cviceni
17.03.2026 út


1. Heap 

- Heap typ DS 
- "Běžné" DS operují množinu se standardními opracemi: insert, delete, search/find, access on index, is_empty/size; 
- Heap je DS na operaci/procesení extrému, proč bych to chtěl? 
- Heap operace: insert, extract_min/extract_max, is_empty/size

Jak Heap vypadá?
- BT jako a) krabicka; b) rekurzivní struktura 
- DS Heap = BT + další vylepšení/podmínky
- DS Heap = BT + "shape/tvar" + "ordering/upořádání"
- min vs max heap 


1.3 Insert do Heapu 
do prázdného min Heapu postupně vložte následující hodnoty: 54, 69, 7, 17, 15, 63, 4, 11, 2 
(a heap si zapiste)

1.7 Extract_min z Heapu
z vypočítaného heapu proveďte 3x operaci extract_min
(kopie stromu, puvodni si ponechame pro dalsi pouziti a kontroly vypoctů)

- jake jsou casove slozitosti opraci insert a extract_min?

1.11 Heap v reprezentaci polem 
1.12 Předchozí vytvořený heap ve stromové reprezentaci převeďte přímo na reprezentaci v poli 
1.13 Vytvořte z předchozích hodnot heap insert a extract přímo v poli

1.17 Heapsort 
- vysvětlení 

na příkladu
- heapsort na haldě stromem 
- heapsort na haldě v poli 



3 Základy rekurze 
- Rekurze na DS a rekurze na funkcích
- v životě, v matematice, v informatice
- potkali jsme již rekurzi nekde v algormizaci? jasan, treba bin_search, mergesort 
- Rekurze jako jazyk popisu problému a rekurze jako metoda výpočtu a její ne-problémy

Napište rekurzivni funkci factorial(n), která ...
Napište rekurzivni funkci fib_num(n), která ...

- z ceho s sklada rekurzivni funkce?: a] rekurzivni volani, b] zastavovaci podminka

Napište rekurzivní funkci max_list(l)
Napište rekurzivní funkci sum_list(l)
Napište rekurzivní funkci reverse_list(l)
Napište rekurzivní funkci palindrom, která ověří zdali vstupní rětězec je palindrom, pokud ano vraci True, pokud ne vrací False
Napište rekurzivní funkci binary_search_recursive(l)
Napište rekurzivní funkci max_list vracejici index maximalniho prvku v listu 


BT jako rekurzivní struktura a šup na rekurzy