堆排序

堆

（二叉）堆是一个数组，可以看成一个近似的完全二叉树。树上每个节点对应数组中的一个元素，按照从左向右的顺序填充。

二叉堆可以分为两种形式：最大堆和最小堆。两种形式都满足堆的定义，最大堆的根节点是最大元素，最小堆的根节点是最小元素。

在堆排序算法中，我们使用的是最大堆。最小堆通常用于构造优先队列。

如果把堆看成一棵树，一个堆中的节点高度就应该是该节点到叶节点最长简单路径上边的数目，进而可以把堆的高度定义为节点的高度。

维护堆的性质（最大堆为例）

伪代码：

MAX-HEAPIFY(A,i)

l=LEFT(i)
r=RIGHT(i)
if l<=A.heapsize and A[l]>A[i]
    largest=l
else largest=i
if r<=A.heapsize and A[r]>A[largest]
    largest=r
if largest!=i
    exchange A[i] with A[largest]
    MAX-HEAPIFY(A,largest)

如果根节点已经是最大那么就不用改变，否则如果子节点比根节点大，就交换两个的值，交换后在递归检查子树。

对于一个树高为h的节点，上面这个过程的时间复杂度是O(h)。

建堆

伪代码：

BUILD-MAX-HEAP(A)

A.heapsize=A.length
for i= A.length/2 downto 1
    MAX-HEAPIFY(A,i)

排序

1. 建堆

• 将根节点输出
• 调整堆
• 2,3循环直到最后一个节点输出

伪代码：

HEAPSORT(A)

BUILD-MAX-HEAP(A)
for i=A.length downto 2
    exchange A[1] with A[i]
    A.heapsize =A.heapsize-1
    MAX-HEAPIFY(A,1)

时间复杂度是

优先队列

优先队列是一种来维护由一组元素构成的集合的数据结构，结构是key-value

一个最大优先队列支持一下操作：

• INSERT(S,x)：将x插入S
• MAXIMUM(S)：返回最大值
• EXTRACT-MAX(S)：返回最大值同时出队
• INCREASE-key(S,x,k)：将x添加到k位置

最大优先队列应用：操作系统的作业调度

最小优先队列同样支持对应的操作。
最小优先队列用于基于事件驱动的模拟器

最大优先队列操作的伪代码：

HEAP-MAXIMUM(A)

return A[1]

HEAP-EXTRACT-MAX(A)

if A.heapsize<1
    error
max=A[1]
A[1]=A[A.heapsize]
A.heapsize--
MAX-HEAPIFY(A,1)
return max

HEAP-INCREASE-KEY(A,i,key)

if key<A[i]
    error
A[i]=key
while i>1 and A[parent(i)]<A[i]
    exchange A[i] with A[PARENT(i)]
    i=PARENT(i)

MAX-HEAP-INSERT(A,key)

A.heapsize++
A[A.heapsize]=无穷小
HEAP-INCREASE-KEY(A,A.heapsize,key)