# 算法学习笔记之二（堆排序） 堆其实是一个数组，它可以看成一个二叉树，用来储存数组里的元素。  其中10为根结点,25，30，70为叶结点，其余称为结点。当父结点的键值总是大于或等于任何一个子节点的键值时为最大堆。当父结点的键值总是小于或等于任何一个子节点的键值时为最小堆。一个结点的高度就是从结点到叶节点的最长路径，一个堆的高度就是根节点的高度。含n个元素的堆高度是floor[log2(n)]. 堆排序利用的是最大堆的性质。 ~~~ Parent(i)//返回一个结点的父结点 returnfloor[i/2] Left(i)//返回一个结点的左子节点 return 2*i Right(i) //返回一个结点的右子节点 return 2*i+1 Max_Heapify(i)//维护以i为结点的子树的最大堆性质 l=Left(i) r=Right(i) if l<=A.heap-size and A[l]>A[i] large=l else large=i if r<= A.heap-size and A[r]>A[larget] larget=r if larget !=i exchanceA[i] with A[larget] Maax_Heapify(A.larget) Build_Max_Heapify(A)//建立一个堆 A.heap-size=A.length For i=floor[A.length/2] downto 2 Max_Heapify(A,i) HeapSort(A)//每一次提取根节点的值，也就是最大值，然后重新建立最大堆 Build_Max_Heapify(A) for i=A.length downto 2 ExchanceA[1] with A[i] A. heap-size =A.heap-size-1 Max_Heapify(A,1) ~~~ 堆排序的时间复杂度也是O（n*log2(n)） 虽然堆排序不是最优，但是其堆的结构却很能引发我们的思考，比如用堆结构可以实现优先队列；接下来就是学习优先队列了。