- v množině najde maximální objekt a vloží ho na začátek již seřazených prvků
- objekt odstraní a hledá maximum znovu
- předpoklady: efektivní operace
Max a DeleteMax
- implementuje se pomocí datové struktury: strom
- acyklický neorientovaný graf
- kořenový strom: jeden vrchol je zvolená jako kořen
- pojmy: rodič, děti/synové, sourozenci, následník
- stupeň vrcholu = počet synů
- hloubka vrcholu = počet hran k danému vrcholu
- výška vrcholu = nejdelší cesty z vrcholu do listu
- hloubka stromu = výška stromu = nejdelší cesta od kořene k
- $k$-tá hladina stromu = množina všech vrcholů stromu ležící v hloubce $k$
- binární strom = strom, kde každý vrchol má nejvýše 2 syny, levý a pravý syn
- k-ární strom = strom, kde každý vrchol má nejvýše $k$ synů
- statická datová struktura - pole
- dynamická datová struktura - pomocí ukazatelů
- stromová datová struktura splňující vlastnost haldy
- kořenový strom má vlastnost haldy právě tehdy, když pro každý uzel $v$ a pro každého jeho syna $w$ platí $v.key \ge w.key$
- díky této vlastnosti obsahuje kořen stromu největší klíč celé haldy
- úplný binární strom s vlastností haldy
- binární strom je úplný, pokud jsou všechny jeho hladiny kromě poslední poslední úplně zaplněny a v poslední hladině leží listy, co nejvíce vlevo
- prvky pole $A$ odpovídají uzlům binární stromu
- uzly očíslujeme po hladinách počínaje od nuly
- klíč z uzlu $i$ uložíme do $A[i]$
- klíč levého syna uzlu $i$ je uložen v poli na pozici $2i + 1$, klíč pravého syna uzlu $i$ je uložen na pozici $2i + 2$
- klíč otce uzlu $i$ je uložen v poli na pozici $(i - 1)//2$
- vstupem je posloupnost klíčů uložená v poli $A[0…n-1]$
A.size =$n$- klíče v poli přeuspořádáme tak, aby na konci výpočtu tvořili haldu
- v odpovídajícím binárním stromu postupujeme od listů směrem ke kořeni
- na každý uzel aplikujeme operaci
Heapify
- postupujeme od uzlu $n-1$ k uzlu $0$
- nechť $i$ je aktuálně zpracovávaný uzel; pak všechny uzl $j$, pro $i < j \le n - 1$, splňují vlastnost haldy
- po zpracování uzlu $i$ splňují vlastnost haldy všechny uzly $j \ge i$
- předpokládá, že binární stromy s kořeny
Left(i)a Right(i) mají vlastnost haldy a že klíč A[i] může být menší než jeho následníci, tj. nemusí splňovat vlastnost haldy
- funkce modifikuje A tak, že po jejím provedení strom s kořenem $i$ má vlastnost haldy
- úprava je založena na přesunu klíče $A[i]$ směrem dolů
function Heapify(A,i)
largest = i
if Left(i) <= A.size and A[left(i)] > A[i] then
largest = Left(i)
if Rigth(i) <= A.size and A[Right(i)] > A[largest] then
largest = Right(i)
if largest != i then
Swap(A[i],A[largest])
Heapify(A,lagest)
- složitost $O(h)$, kde $h$ je hloubka stromu s kořenem $i$
- korektnost indukcí vzhledem k hloubce stromu
- využitím procedury
Heapify zkonvertujeme pole $A[0…n-1]$ na maximovou haldu
- listy stromu tvoří haldu s 1 vrcholem která má požadované vlastnosti procedury
Heapify aplikujeme na zbylé klíče v poli v pořadí odspodu směrem nahoru a na dané úrovni směrem zprava doleva
function BuildHeap(A)
A.size = len(A)
for i = A.size // 2 downto 0 do
Heapify(A,i)
- složitost
BuildHeap pro strom s hloubkou $h$ je složitost $\in O(n)$
- použitím procedury
BuildHeap vybudujeme haldu nad polem $A[0…n-1]$; velikost haldy je $A.size = n$
- maximální prvek pole $A$ je uložený v kořeni haldy na pozici 0 a proto ho můžeme přesunout na jeho finální pozici $A.size - 1$ a to tak, že vyměníme prvky $A[0]$ a $A[A.size - 1]$
- prvek na pozici $A.size - 1$ již není součástí haldy a proto snížíme hodnotu $A.size$ o $1$
- prvek, který jsme přesunuli do kořene, může porušit vlastnost haldy pro obnovení vlastnosti haldy použijeme
Heapify(A,0)
- celý proces opakujeme
algorithm HeapSort(A)
BuildHeap(A)
for i = len(A) downto 1 do
Swap(A[i],A[0])
A.size -= 1
Heapify(A,0)
- funkce
BuildHeap má složitost $O(n)$
- každé z $n - 1$ volání
Heapify má složitost $O(\log n)$
- algoritmus
HeapSort má složitost $\green O(\log n)$
- datový typ pro reprezentaci množiny prvků, nad kterými je definováno uspořádání
- požadujeme efektivní realizaci operací
Insert(S,x) vloží prvek $x$ do množiny $S$Maximum(S) vrátí největší prvek množiny $S$ExtractMax(S) odstraní z množiny $S$ největší prvekIncreaseKey(S,x,k) nahradí prvek $x$ za předpokladu, že $k \ge x$
- prioritní frontu implementujeme jako haldu
- prvky množiny $S$ tvoří haldu $A$
- maximální prvek haldy je v jejím kořeni
- jeho nalezení má konstaní složitost
function Maximum(A)
return A[0]
- odstranění maximálního prvku se implementuje stejně jako v algoritmu řazení haldou
- složitost operace je $O(\log n)$
function ExtractMax(A)
if A.size == 0 then
return None
max = A[0]
A[0] = A[A.size-1]
A.size -= 1
Heapify(A,0)
return max
- index $i$ identifikuje prvek, kterž má být operací nahrazen (navýšen)
- vstupní podmínka: $A[i] \le key$
- nejdříve změníme hodnotu $A[i]$ na novou hodnoty $key$ a potom obnovíme vlastnost haldy tak, že nový prvek posouváme směrem ke kořeni
- složitost operace je $O(\log n)$
function IncreaseKey(A,i,key)
A[i] = key
while i > 0 and A[Parent(i)] < A[i] do
Swap(A[i],A[Parent(i)])
i = Parent(i)
- na konec pole vložíme nový prvek, který je menší než všechny ostatní prvky, symbolicky ho označujeme $-\infty$
- zvýšíme hodnotu vloženého prvku, který chceme vložit do fronty
- složitost operace je $O(\log n)$
function Insert(A,key)
A.size += 1
A[A.size] = $-\infty$
IncreaseKey(A,A.size,key)
- vstupní podmínka: vstupní posloupnost obsahuje celá čísla z intervalu $0,…,k$, kde $k$ je nějaké pevně dané přirozené číslo
- zaznamenávám si kolik čísel s danou hodnotou se v dané posloupnosti vyskytuje
algorithm CountingSort(A,B,k)
for i = 0 to k do
C[i] = 0
for j = 0 to len(A) - 1 do
C[A[j]] += 1
for i = 1 to k do
C[i] += C[i-1]
for j = len(A)-1 downto 0 do
B[C[A[j]]-1] = A[j]
C[A[j]] -= 1
- časová složitost $\Theta(k+n)$
- algoritmus je stabilní
- řazení čísel podle číslic na jednotlivých bitech
- postup zleva doprava (most significant digit, MSD) - používá se pro lexikografické upsořádání
- postup zprava doleva (least significant difit, LSD), stabilní řazení
- dá se použít i pro řazení položek, které nemají číselný charakter
- používá se např. když potřebujeme seřadit položky vzhledem k různým klíčům
algorithm RadixSort(A,d)
for i = 1 to d do
použij stabilní řazení a seřaď položky podle i-te číslice
- složitě se vyjadřuje (mnoho proměnných)
- počet čísel, kolik číslic čísla mají, …
- $\Theta(d(n+k))$
- složitost je garantována např. při použití algoritmu
CountingSort
- vstupní podmínka:
- posloupnost obsahuje čísla $[0…1)$
- čísla rovnoměrně pokrývají celý interval
- interval $[0…1)$ rozdělíme na stejně velké podintervalu (koše)
- vstupní čísla rozdělíme dle jejich hodnoty do košů
- seřadíme prvky v každém koši