Pseudokody do wyk lad´

ow 8 i 9

21, 28 kwiecie´

n 2011

Przywracanie w lasno´

sci kopca

typu max

Dane: Tablica A oraz indeks i w tej tablicy

Za lo ˙zenia: Drzewa binarne o korzeniach w LEFT(i) i RIGHT(i)
sa

,

kopcami typu max, ale element A[i] mo˙ze by´

c mniejszy od

swoich syn´

ow (naruszenie w lasno´

sci kopca typu max)

Efekt: Poddrzewo zaczepione w we

,

´

zle i staje sie

,

kopcem typu

max

MAX-HEAPIFY(A, i)

l

← LEFT(i)

r

← RIGHT(i)

if (l

≤ heap-size[A]) and (A[l] > A[i])

then L

← l

else L

← i

if (r

≤ heap-size[A]) and (A[r] > A[L])

then L

← r

if L

̸= i

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´

scie to we

,

z ly o indeksach

⌊n/2⌋ + 1, ⌊n/2⌋ + 2, . . . , n

Zatem ka˙zdy element podtablicy A[

⌊n/2⌋+1..n] jest ju˙z 1-elementowym

kopcem.

Algorytm: Przejd´

z przez pozosta le we

,

z ly drzewa i w ka˙zdym

z nich wywo laj procedure

,

MAX-HEAPIFY (podej´

scie wste

,

puja

,

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´

sciowej A[1..n], gdzie n = length[A]

– A[1]

↔ A[n]

– przekszta l´

c tablice

,

A[1..(n

−1)] w kopiec typu max; nowy korze´n

mo˙ze narusza´

c w lasno´

s´

c 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 s lu˙za

,

ca do reprezen-

towania zbioru S element´

ow, z kt´

orych ka˙zdy ma przporza

,

dkowana

,

warto´

s´

c, zwana

,

kluczem (priorytetem)

Kolejka priorytetowa typu max – mo˙zliwe operacje:

INSERT(S, x) – wstawia element x do zbioru S

MAXIMUM(S) – zwraca element zbioru S o najwie

,

kszym

kluczu

EXTRACT-MAX(S) – usuwa i zwraca element zbioru
S o najwie

,

kszym kluczu

INCREASE-KEY(S, x, k) – zmienia warto´

s´

c klucza

elementu x na nowa

,

warto´

s´

c k nie mniejsza

,

ni˙z

aktualna warto´

s´

c klucza elementu x

Implementacje operacji

kolejki priorytetowej typu max

przy u ˙zyciu kopca typu max

Za lo˙zenie: 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´

orego klucz ma zosta´

c zwie

,

kszony jest

okre´

slony 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)