Algoritmy a dátové štruktúry prednáška 06

Zhrnutie prednášky

Prednáška pokračuje v téme haldy (heap) ako dátovej štruktúry pre efektívnu prioritnú frontu. Rozoberajú sa dva extrémne tvary stromu (hlboký reťazec a plytký veľmi rozvetvený strom) a ukazuje sa, že optimálny je dokonale vyvážený binárny strom s logaritmickou hĺbkou. Vysvetľujú sa operácie vkladania prvku bublaním nahor a výberu maxima bublaním nadol, obe v logaritmickom čase, a spôsob uloženia haldy do obyčajného poľa pomocou vzorcov pre indexy detí (2n+1, 2n+2) a rodiča. Predstavuje sa algoritmus heapsort vrátane implementácie bez pomocných polí priamo v jednom poli a spomína sa hybridné triedenie kombinujúce quicksort, insertion sort pre malé úseky a heapsort ako poistku (tzv. introsort) pre zaručenú n log n zložitosť aj v najhoršom prípade. Na záver sa ukazuje trik na vybudovanie haldy z neusporiadaného poľa v lineárnom čase a pripája sa jazykový exkurz o pôvode slova 'triedenie' z histórie dierno-štítkových strojov.

• Tvar haldy - hlboký reťazec vs. rozvetvený strom vs. vyvážený binárny strom
• Vkladanie do haldy bublaním nahor (bubble up)
• Výber maxima z haldy bublaním nadol (bubble down)
• Reprezentácia haldy v poli - výpočet indexov detí a rodiča
• Algoritmus heapsort a jeho implementácia bez pomocných polí
• Hybridné triedenie - quicksort, insertion sort a heapsort (introsort)
• Zostavenie haldy z neusporiadaného poľa v lineárnom čase
• Dolný odhad zložitosti triedenia porovnávaním

Zhrnutie pripravené s pomocou AI z prepisu videa.