Alg 

* stromy (jako graf) - binární, n-arní strom, hloubka vrcholu a stromu, delka cesty (v cem se meri?), terminologie: koren a list
* bin stromy jako datova struktura, rekurzivne
* (binarni) halda: definice, "heap = BT + usporadani + tvar"; forma BT a pole; operace: insert, extract min/max v a) stromě b) poli a jejich prevody; 
* heapsort (vytvoreni haldy v case nlog(n))
faze 1 - pole - halda jako BT - pole 
faze 2 - pole halda v poli - pole ... vse to same pole
faze 3 - tvorba haldy v case O(n)

- vlozte (prvek po prvku) do min-heapu (ve forme stromu) posloupnost hodnot: 30, 4, 71, 14, 22, 5, 2, 9, 8, 3, 11
- zmente reprezentaci vytvorene haldy z BT na pole 
- vytvorte haldu ve forme pole z nasledujici posloupnosti: 30, 4, 71, 14, 22, 5, 2, 9, 8, 3, 11
- v halde provedte 4x operaci extractMin a] v forme BT b] ve forme pole
- mejme pole hodnot: 30, 4, 71, 14, 22, 5, 2, 9, 8, 3, 11 provedte razeni heapsortem v poli

3. kolik maximálně prvků má binární strom v k-vrstvě (hloubce?)
5. kolik maximálně prvků ma binární strom o k-vrstvách (hloubce?)
7. dokazte nebo vyvratte: mejme plne zaplneny binarni strom o k vrstvach; 
obsahuje k vrstva vice hodnot nezli cely strom bez k-te vrstvy?

* různé modifikace binárního vyhledávání:
- v setříděném poli určit počet výskytů dané hodnoty x
- v setříděném poli nalézt všechny prvky s danou hodnotou x (první a poslední index)
- v setříděném poli nalézt prvek s hodnotu x (pokud tam je) nebo nejbližší vyšší (pokud tam žádné x není).


- mejme pole hodnot: 30, 4, 71, 14, 22, 5, 2, 9, 8, 3, 11 provedte razeni heapsortem v poli

Řazení v lineárním čase 
* CoutingSort - příklad 
counting sortem seřaďte posloupnost: 5,3,7,1,5,2,3,1,2,4,5,3,1,3 
* RadixSort - příklad 
seřaďte posloupnost: 15,3,17,11,25,32,23,21,42,54,75,13,31,33


Co se stane, když v algoritmu radixového třídění budeme zpracovávat souřadnice zleva doprava (místo zprava doleva),
 tj. ve funkci radixSort() přednáškových slidů vynecháme reversed v záhlaví for-cyklu.
Bude takto upravený algoritmus stále fungovat korektně?
Pokud ano, vysvětlete proč, pokud ne, sestrojte protipříklad.


* Dolni odhad složitosti řazení prvků porovnáním - rekonstrukce důkazu
- rozhodovaci strom, co znazornuje jedna cesta ve strome vs co znazornuje strom vs co znazornuje list a co vnitrni uzel stromu
- prerovnani stromu, hloubka stromu a nejhorsi pripad
- kolik listu a proc? vztah poctu listu k velikosti stromu resp. jeho vysce 
- vztah vysky stromu k delce vypoctu



Prg 

* std in
* string splitting
* f-string formating
https://ksvi.mff.cuni.cz/~dingle/2024-5/prog_1/notes_3.html



*5. Napiste funkci, ktera dostane matici (jako list listu) a vytiskne ji jako "hezkou" matici: mezi cisly je jedna mezera a cisla jsou zarovnana ve sloupci viz priklad 
a] predpokladejte ze velikost cisla je maximalne 3 cislice
b] predpokladejte ze velikost cisla nezname (ale neni vetsi nezli 20 cislic)

matici 
[ [1, 2, 3], [2, 1, 5], [3, 4, 1] ]

vypsat
1 2 3
2 1 5
3 4 1 

*5.1 To same ale se zarovnanim cisel

111 2 333
 22 1   5
  3 4  11 

*6. Napiste funkci, precte a naparsuje celociselnou matici ze standardniho vstupu a vrati ji jako list listu 
Matice na vstupu je ulozena po radcich, jednotlive hodnoty jsou oddeleny carkou a prolozeny mezerami, vstup je korektni. 

Priklad vstupu:
1, 2, 3 
2, 1, 4
3, 4, 1

nebo
   1,  3, 3, 4
     2, 2    ,  33, 5
0, 0 ,2 ,22



# OOP
# https://www.programiz.com/python-programming/object-oriented-programming
# https://ksvi.mff.cuni.cz/~dingle/2023-4/prog_1/notes_6.html

# 1 
# Definujte tridu Zvire majici: 
# a) uid 
# b) konstruktor(uid) 
# c) abstraktni metodu voice()

# 2 
# A od ni podedte dve tridy: 
# a) Pes 
# b) Kocka 
# pro ne pretezte\implementujte metodu voice(),
# která vytiskne jejich hlas (Kocka "Mnau" a Pes "Haf") a uid instance

# 3 
# Vytvorte 
# a) 3 instance Kocky 
# b) 2 instance Psů, 
# ktere ulozite do listu

# 4 
# List iterujte a zavolejte na vsech instacich objektů metodu voice()

# 5
# Ve for cyklu vytvorte list 100 Kocek 
# a ve for cyklu ho projdete a zavolejte metodu voice()