A kupac egyik leggyakoribb alkalmazási területe a prioritásos sor. Beszélhetünk
maximum-, vagy minimum prioritásos sorról. Maximum prioritásos sor esetén mindig a legnagyobb
prioritású elemet tudjuk kivenni, a minimum prioritásos sor esetén pedig a legkisebbet.
Mindkettő fajta ábrázolható kupaccal. Itt most a maximum prioritásos sort fogjuk látni, amit egy
maximum kupaccal ábrázolunk.
Prioritásos sor műveletei:
| $PrQueue$ |
$- \space A : \mathcal{T}[]$
$- \space n : \mathbb{N}$ |
$+ \space PrQueue ( m : \mathbb{N} ) \space \{ A := \text{new} \space
\mathcal{T}[m]; n :=
0 \}$
$+ \space \sim PrQueue() \space \{ delete \space A \}$
$+ \space add(x :
\mathcal{T})$
$
+ \space remMax() :
\mathcal{T}$
$+ \space max() : \mathcal{T}$
$+ \space isFull() : \mathbb{B} \space \{
\text{return} \space n =
A.length
\}$
$+ \space isEmpty() : \mathbb{B} \space \{ \text{return} \space n = 0 \}$
$+ \space
setEmpty() \space
\{ n := 0 \}$ |
max():
Ha nem üres a prioritásos sor, visszaadja a legnagyobb elemet, azaz a gyökér
elemet, máskülönben hibát kapunk.
$n > 0$
|
| $\text{return} \space A[0]$ |
$\text{error}$ |
remMax() (és sink()):
A kupacban a maximális elem a gyökér elem. Ez az elem a tömb első eleme. A
maximális elem eltávolításakor a helyére a tömb utolsó elemét helyezzük. Ezt le kell
süllyeszteni, hogy helyre álljon a kupac tulajdonság. Ennek során a lesüllyesztendő elemet a
nagyobb gyerekével cseréli meg, amíg a levélszint fölött van, és a nagyobbik gyereke nagyobb nála.
$n > 0$
|
| $max := A[0]$
|
$\text{error}$ |
| $n := n - 1$ |
| $A[0] := A[n]$
|
| $sink(A,0,n)$
|
| $\text{return} \space max$ |
| $i := k$ |
| $j := left(k)$ |
| $b := true$ |
|
$j \lt n \land b$ |
$j + 1 < n \land A[j+1] > A[j]$
|
| $j := j+1$
|
$\text{SKIP}$ |
$A[i] < A[j]$
|
| $swap(A[i],
A[j])$ |
$b := false$
|
| $i := j$ |
| $j :=
left(j)$ |
add():
Ha van még üres hely a tömbben beírjuk az új kulcsot az első szabad helyre, majd
emelést hajtunk végre a kupacban.
$n < A.length$
|
| $j:=n$ |
$\text{error}$ |
| $n := n+1$ |
| $A[j] := x$ |
| $i := parent(j)$ |
|
$j > 0 \land A[i] < A[j]$ |
| $swap(A[i], A[j])$ |
| $j := i$ |
| $i := parent(i)$ |
Prioritásos sor ábrázolásainak összehasonlítása:
|
$add(x : \mathcal{T})$ |
$remMax()$ |
$max()$ |
rendezetlen tömbbel
(ha a maximális elem indexét nyilvántartjuk) |
$\Theta (1)$ |
$\Theta (n)$ |
$\Theta (1)$ |
| növekvően rendezett tömbbel |
$O (n)$ |
$\Theta (1)$ |
$\Theta (1)$ |
| maximum kupaccal |
$O (log \space n)$ |
$O (lg \space n)$ |
$\Theta (1)$ |
Rendezés prioritásos sorral:
Az ötlet az, hogy rakjuk be a kulcsokat egy prioritásos sorba, majd onnan kivéve
tegyük vissza őket a tömbbe.
| $Q : PrQueue(n)$ |
|
$i := 0 \space to \space n-1$ |
| $Q.add(A[i])$ |
|
$i := n-1 \space downto \space 0$ |
| $A[i] := Q.remMax()$ |
Gyakorlatban nem szokták ezt használni, mert a rendezendő tömbbel azonos méretű
tárigénye van és egyéb tanult rendezők algoritmusok gyorsabbak. Helyette a kupacrendezést
használják.
Műveletigény:
(A műveletigény a kupacos megvalósításra vonatkozik.)
- $MT_{sortWithPrQueue}(n) \in \Theta (n \cdot log \space n)$
Gyakorlati alkalmazása:
Maximum prioritásos sort használnak például az osztott működésű számítógépeken a
munkák ütemezéséhez.
Minimum prioritásos sort használnak például az esemény-vezérelt szimulációkhoz.