Řazení použitím prioritní fronty
Dále se budeme zabývat úlohou seřadit prvky pole podle velikosti jejich klíče. Z pohledu samotného algoritmu řazení se můžeme omezit na pole, kterého prvky jsou přímo klíče a navíc budeme předpokládat, že jsou nimi celá čísla.
Třída pro řazení pole, kromě metody pro seřazení jeho prvků, bude mít ještě metodu pro načtení prvku pole a tisk všech prvků v poli. Její rozhraní tedy bude
class RazeniPole {
//ADT rozhrani
void nactiPrvek(int)
void tiskPole()
void razeniPF()
}
Imlementace metod nactiPrvek( ), tiskPole( ) a razeniPF( ) je na obr.. Metoda razeniPF( )vytvoří v první fázi prázdnou prioritní frontu a postupně do ní vloží prvky řazeného pole. Pak ve fázi řazení postupně vybírá největší prvek a ukládá ho od konce původního pole, čímž získáme v původním poli jeho prvky vzestupně seřazené.
Jakoukoliv z uvedených implementací prioritní fronty můžeme použít ve třídě RazeniPole pokud jde o její funkčnost. Navíc pro konkrétní implementace prioritní fronty, získáme různé metody řazení. Prioritní fronta je tedy další typický ADT jehož použitím v klientovi dostáváme řešení s různými vlastnostmi pro jeho různé implementace při zachování rozhraní.
Použijeme-li uspořádané pole, získáme metodu řazení typu řazení vkládáním. Použijeme-li neuspořádané pole získáme metodu, která odpovídá řazení výběrem.
Navíc, můžeme takto získané programy upravit tak, že prioritní fronta bude součástí řazeného pole a nebudeme potřebovat kromě paměti pro řazené pole ještě další paměť pro prioritní frontu. Dostaneme tak známé metody řazení vkládáním a výběrem.
Použijeme-li implementaci prioritní formy pomocí haldy, při výběru největšího prvku z kořene haldy nastává obnova haldy, která může znamenat cestu až k listům délky trvající log2 n. Poslední cesta bude mít délku log2 1 a tedy časová náročnost fáze řazení je
log2 n + ... + log2 2 + log2 1 < n log2 n
Také při použití haldy pro implementaci řazení pomocí prioritní fronty, můžeme haldu uchovávat jako součást řazeného pole. Při řazení samotném je v tomto případě použití rozhraní ADT prioritní fronta omezující a metody nahoru( ) a dolu( ) použijeme přímo ve třídě RazeniPoleHaldou1 (obr.).
Po načtení všech prvků pole, budeme procházet v metodě razeniHaldou1( ) polem od jeho začátku a metodou nahoru( ) vytvářet vlevo od okamžité pozice haldu (obr.), což odpovídá fázi vytvoření haldy. Připomeňme, že vzhledem k námi použité implementaci haldy, prvky řazeného pole jsou uloženy v pf[1] až pf[pocet] . Následuje fáze řazení, kdy vyměníme kořen haldy (první prvek pole) s posledním prvkem haldy a v poli obnovíme metodou dolu( ) haldu zmenšenou o jeden prvek. Protože obě fázy jsou O(n log2 n) je čas razeniHaldou1( ) také O(n log2 n).
Řazení výběrem bylo založeno na nalezení největšího prvku postupným procházením neseřazené části pole a jeho výměnou s prvkem bezprostředně před seřazenou částí. Vidíme, že uvedená metoda razeniHaldou1( ) pracuje podobně s tím, že výběr největšího prvku z neseřazené části pole je efektivnější. Neprochází potenciálně všechny ještě neseřazené prvky, ale protože tyto jsou organizovány v haldě, pro obnovu vlastnosti haldy po odebrání největšího prvku nutno projít nejvíce log2 (počet_ neseřazených_ prvků).