Ćwiczenia 11 - 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)

MAX-HEAP-INSERT(T,15)
WRITE(T)
HEAP-MAXIMUM(T)
WRITE(T)
HEAP-EXTRACT-MAX(T)
WRITE(T)
HEAP-INCREASE-KEY(T,4,11)
WRITE(T)

STRUCT-HEAP
	[]
	length = 100
	heap-size = 0

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[l] > T[i]
		L = l
	else
		L = i
	if r ≤ T.heap-size AND T[r] > T[L]
		L = r
	if L ≠ i
		tmp = T[i]
		T[i] = T[L]
		T[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[1]

HEAP-EXTRACT-MAX(T)
	if T.heap-size < 1
		error "kopiec pusty"
	max = T[1]
	T[1] = T[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[i]
		error "klucz mniejszy"
	T[i] = key
	while i > 1 AND T[PARENT(i)] < T[i]
		tmp = T[i]
		T[i] = T[PARENT(i)]
		T[PARENT(i)] = tmp
		i = PARENT(i)

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