Pseudokody do wykladów 8 i 9
21, 28 kwiecień 2011
Przywracanie wlasności kopca
typu max
Dane: Tablica A oraz indeks i w tej tablicy
Zalożenia: Drzewa binarne o korzeniach w LEFT(i) i RIGHT(i)
sa kopcami typu max, ale element A[i] może być mniejszy od
swoich synów (naruszenie wlasności kopca typu max)
Efekt: Poddrzewo zaczepione w wez
le i staje sie kopcem typu
max
MAX-HEAPIFY(A, i)
l �! LEFT(i)
r �! RIGHT(i)
if (l d" heap-size[A]) and (A[l] > A[i])
then L �! l
else L �! i
if (r d" heap-size[A]) and (A[r] > A[L])
then L �! r
if L = i
8
then A[i] "! A[L]
MAX-HEAPIFY(A, L)
Typeset by AMS-TEX
1
2
Budowanie kopca
Obserwacja: W tablicowej reprezentacji kopca n-elementowego
liście to wezly o indeksach
#n/2# + 1, #n/2# + 2, . . . , n
Zatem każdy element podtablicy A[ #n/2#+1..n] jest już 1-elementowym
kopcem.
Algorytm: Przejdz
przez pozostale we zly drzewa i w każdym
z nich wywolaj procedure MAX-HEAPIFY (podejście wstepuja ce
bottom-up)
BUILD-MAX-HEAP(A)
heap-size[A] �! length[A]
for i �! #length[A]/2# downto 1
do MAX-HEAPIFY(A, i)
Sortowanie przez kopcowanie
 stosuja c procedure BUILD-MAX-HEAP zbuduj kopiec typu max
w tablicy wejściowej A[1..n], gdzie n = length[A]
 A[1] "! A[n]
 przeksztalć tablice A[1..(n-1)] w kopiec typu max; nowy korzeń
może naruszać wlasność kopca typu max
HEAPSORT(A)
BUILD-MAX-HEAP(A)
for i �! length[A] downto 2
do A[1] "! A[i]
heap-size[A] �! heap-size[A] - 1
MAX-HEAPIFY(A, 1)
3
Kolejki priorytetowe
Kolejka priorytetowa  struktura danych sluża ca do reprezen-
towania zbioru S elementów, z których każdy ma przporza dkowana
wartość, zwana kluczem (priorytetem)
Kolejka priorytetowa typu max  możliwe operacje:
INSERT(S, x)  wstawia element x do zbioru S
MAXIMUM(S)  zwraca element zbioru S o najwiekszym
kluczu
EXTRACT-MAX(S)  usuwa i zwraca element zbioru
S o najwiekszym kluczu
INCREASE-KEY(S, x, k)  zmienia wartość klucza
elementu x na nowa wartość k nie mniejsza niż
aktualna wartość klucza elementu x
Implementacje operacji
kolejki priorytetowej typu max
przy użyciu kopca typu max
Zalożenie: kopiec nie jest pusty
Implementacja operacji MAXIMUM
HEAP-MAXIMUM(A)
return A[1]
4
Implementacja operacji EXTRACT-MAX
HEAP-EXTRACT-MAX(A)
max �! A[1]
A[1] �! A[heap-size[A]]
heap-size[A] �! heap-size[A] - 1
MAX-HEAPIFY(A, 1)
return max
Implementacja operacji INCREASE-KEY
Element kolejki, którego klucz ma zostać zwie kszony jest
określony przez indeks i w tablicy A
HEAP-INCREASE-KEY(A, i, key)
if key < A[i]
then error
A[i] �! key
while i > 1 and A[PARENT(i)] < A[i]
do A[i] "! A[PARENT(i)]
i �! PARENT(i)
Implementacja operacji INSERT
MAX-HEAP-INSERT(A, key)
heap-size[A] �! heap-size[A] + 1
A[heap-size[A]] �! -"
HEAP-INCREASE-KEY(A, heap-size[A], key)