Ćwiczenia 12 - Kopiec binarny i Kolejka priorytetowa

STRUCT-HEAP T
tab =(4,1,3,2,16,9,10,14,8,7)
HEAP-INIT(T,tab,tab.length)
BUILD-MAX-HEAP(T)
WRITE(T) //16 14 10 8 7 9 3 2 4 1

MAX-HEAP-INSERT(T,15)
WRITE(T) //16 15 10 8 14 9 3 2 4 1 7
WRITE(HEAP-MAXIMUM(T)) //16
WRITE(T) //16 15 10 8 14 9 3 2 4 1 7
WRITE(HEAP-EXTRACT-MAX(T)) //16
WRITE(T) //15 14 10 8 7 9 3 2 4 1
HEAP-INCREASE-KEY(T,4,19)
WRITE(T) //19 15 10 14 7 9 3 2 4 1

STRUCT-HEAP
	data[1..20]
	length = 0
	heap-size = 0

HEAP-INIT(T,tab,n)
	for i = 1 to n
		T.data[i] = tab[i]
	T.length = n

PARENT(i)
	return i DIV 2

LEFT(i)
	return 2 * i

RIGHT(i)
	return 2 * i + 1

MAX-HEAPIFY(T, i)
	l = LEFT(i)
	r = RIGHT(i)
	if l ≤ T.heap-size AND T.data[l] > T.data[i]
		L = l
	else
		L = i
	if r ≤ T.heap-size AND T.data[r] > T.data[L]
		L = r
	if L ≠ i
		tmp = T.data[i]
		T.data[i] = T.data[L]
		T.data[L] = tmp
		MAX-HEAPIFY(T, L)

BUILD-MAX-HEAP(T)
	T.heap-size = T.length
	for i = T.length DIV 2 DOWNTO 1
		MAX-HEAPIFY(T, i)

HEAP-MAXIMUM(T)
	return T.data[1]

HEAP-EXTRACT-MAX(T)
	if T.heap-size < 1
		error "kopiec pusty"
	max = T.data[1]
	T.data[1] = T.data[T.heap-size]
	T.heap-size = T.heap-size - 1
	MAX-HEAPIFY(T,1)
	return max

HEAP-INCREASE-KEY(T,i,key)
	if key > T.data[i]
		T.data[i] = key
		while i > 1 AND T.data[PARENT(i)] < T.data[i]
			tmp = T.data[i]
			T.data[i] = T.data[PARENT(i)]
			T.data[PARENT(i)] = tmp
			i = PARENT(i)

MAX-HEAP-INSERT(T,key)
	T.heap-size = T.heap-size + 1
	T.data[T.heap-size] = -∞
	HEAP-INCREASE-KEY(T,T.heap-size,key)