优先级队列
伪代码:
//返回优先级队列的最大值
Heap_Max(A)
return A[1]
end
运行时间为Θ(1)
//去掉并返回优先级队列中的最大值
/*
* 先记录最大值,将数组最后的元素与第一个元素交换,数组大小减一,
* 调用max_heapify函数保证最大堆的性质,最后返回最大值。
*/
Heap_Extract_Max(A, length)
if length < 1 then error "heap under flow"
max = A[1]
A[1] = A[length]
length --
Max_Heapify(A, 1, length)
return max
end
运行时间为Θ(lgn)
//将优先级队列中的i元素的值增加到key(key >= A[i])
Heap_Increase_Key(A, i, key)
if key < A[i] then error
A[i] = key
while i>1 && A[PARENT(i)] <A[i]
do exchange A[i] <-> A[PARENT(i)]
i = PARENT(i)
end
运行时间为Θ(lgn)
//将元素插入优先级队列.
向最大堆中插入新的关键字。新的关键字插入在优先级的队尾部,然后从尾部的父节点开始自底向上调整堆
MAX_HEAP_INSERT(A,key)
heap_size[A] = heap_size[A]+1
A[heap_size[A]] = -0; //把队尾赋值0或无穷小
HEAP_INCREASE_KEY(A,heap_size[A],key)
end
运行时间为Θ(lgn)
详细资料参考:http://www.cnblogs.com/Anker/archive/2013/01/23/2873951.html