Záznam přednášky - ICO-Dict
| Akce: | Krutá Smršť Přednášek 2018 (záznamy z akce) |
|---|---|
| Přednášející: | Matej Lieskovský |
| Motto: | Chtěli jste si pořídit strom, ale zjistili jste, že na něj nemáte místo? Máme řešení! |
| Anotace: | Někdy v šedesátých letech byl objeven in-place heapsort a s ním implicitní halda (taková ta permutace prvků v poli, kde potomci i-tého prvku jsou na pozicích 2i a 2i+1) a následně byla položena otázka, zda by náhodou nešlo vyrobit i implicitní strom. Vydáme se tedy na cestu za datovou strukturou, která pozůstává jen z nějaké prapodivné permutace n prvků v poli, a která umí Insert, Find, Delete, Min, Max, Pred i Succ v čase O(log n). Jo a jen tak mimochodem to bude celé cache-oblivious. |
| Ke stažení: | Video (MP4/H.264) a Audio (MP3/AAC) |