堆排序
堆排序排序是优秀的算法，但是在实际应用中，快速排序的性能一般会优于堆排序，
尽管如此，堆排序仍然有很多应用，例如：作为高效的优先队列，最大优先队列应用于共享计算机系统的作业调度，最小优先队列应用于基于事件驱动的模拟器（时间必须按照发生的事件顺序进行模拟）。
堆：是一个数组，它可以看成是一个近似的完全二叉树。
其中：父节点，左孩子，右孩子为：
PARENT(i)
return i/2 (此处要取下界)
LEFT(I)
return 2i
RIGHT(i)
return 2i+1** 并且，当数组存储n个元素的堆时，叶子结点下边是 n/2+1, n/2+2, ..., n。(n/2取下界)
最大堆：A[PARENT(i)] >= A[i]
最小堆：A[PARENT(i)] <= A[i]
维护堆的性质：
MAX_HEAPIFY
MAX-HEAPIFY(A,i)
l = LEFT(i)
r = RIGHT(i)
if l<=A.heap-size and A[l]>A[i]
largest = l
else largest = i
if r<=A.heap-size and A[r]>A[largest]
largest = r
if largest != i
exchange A[i] with A[largest]
MAX-HEAPIFY(A,largest)建堆：
BUILD-MAX-HEAP(A)
A.heap-size = A.length
for i = A.length/2(这里要取下界) downto 1
MAX-HEAPIFY(A,i)堆排序算法：
HEAPSORT(A)
BUILD-MAX-HEAP(A)
for i= A.length downto 2
exchange A[1] with A[i]
A.heap-size = A.heap-size - 1
MAX-HEAPIFY(A,1)本文参与 腾讯云自媒体分享计划，分享自作者个人站点/博客。
原始发表：2017年10月11日，如有侵权请联系 cloudcommunity@tencent.com 删除
评论
登录后参与评论
推荐阅读