Prioritní fronta: Porovnání verzí
Smazaný obsah Přidaný obsah
Oprava interních odkazů, drobné stylistické úpravy |
m →Implementace: do budoucna přesnější odkaz |
||
Řádek 11:
Prioritní frontu je možné implementovat různými způsoby. Jednodušší na [[Programátor|naprogramování]], ale náročnější na [[Asymptotická složitost|procesorový čas]] jsou implementace netříděným [[Pole (datová struktura)|polem]] nebo [[Lineární seznam|spojovým seznamem]]. Taková řešení nabízejí vložení v konstantním čase, ovšem vydání prvku s nejvyšší prioritou má časovou náročnost <math>O(n)</math>.
Rozšířenější je implementace pomocí [[Halda (datová struktura)|haldy]], kde má zařazení i vydání prvku s nejvyšší prioritou časovou náročnost <math>O(\log n)</math>; platí to např. pro [[Binární halda|binární]] nebo [[Binomiální halda|binomiální haldu]]. Zvláštním případem je [[Fibonacciho halda]], operace vložení do níž má [[Asymptotická složitost|asymptotickou složitost]] <math>O(1)</math> a vydání toho prvku zní, jenž má nejvyšší prioritu, [[
== Literatura ==
| |||