堆与堆排序—优先队列
上一节我们写了树以及二叉树的知识
http://blog.csdn.net/wtyvhreal/article/details/43487095
堆是一种特殊的完全二叉树。
所有父节点都比子节点要小，这样的完全二叉树称为最小堆，反之叫最大堆。
下图一棵完全二叉树，调整为最小堆步骤：
向下调整的代码如下：
从上面可以得到：调整堆的时间复杂度是O(logN)。
如果堆的大小为N，那么插入一个新元素所需要的时间为O(logN).
在刚刚那个最小堆里插入数值3
向上调整的代码如下：
建堆：从空的堆开始，依次往堆中插入每一个元素。整体时间复杂度是O(NlogN).
下面用O(N)复杂度来建堆。
。。。
n个元素建堆：
首先可以将这n个节点以自顶向下，从左到右的方式从1到n编码，这样就可以把这n个节点转换为一棵完全二叉树，然后从（最后一个非叶节点）第n/2个节点（n为节点总数）开始到根节点逐个处理这颗完全二叉树（最后一个非叶节点是第n/2个节点）。根据需要将当前节点向下调整，直至符合堆的特征。时间复杂度为O(N).
证明时间复杂度为O(N):
首先这个循环是从i = n/2 -> 1，也就是说这是一个bottom-up的建堆。于是，有1/2的元素向下比较了一次，有1/4的向下比较了两次，有1/8的向下比较了3次，......，1/2^k的向下比较了k次，其中1/2^k <= 1, k 约等于lg(n)。于是就有总的比较量：
T = () * n
令 S =
1/2 S =
S - 1/2S = 1/2S =
到这步就很明显了吧，S <= 2
于是T <= 2n => T = O(n).
堆排序的时间复杂度也是O(NlogN)。
比如从小到大排序，先建立最小堆。然后每次删除顶部元素然后调整，直到堆为空。
还有一中堆排方法，是建立最大堆，而不是上面建立的最小堆。
最大堆建立好后，最大的元素是h[1],交换h[1]和h[n]，此时h[n]就是最大的元素了。然后将交换后的h[1]向下调整保持堆的特性。交换一次，n--，反复直到堆的大小变为1.此时h数组就是已经排好序了。
总结：
支持插入元素和寻找最值的数据结构称为优先队列。堆就是一种优先队列。
堆还经常用来求一个数列中第K大的数，只需要建立一个大小为K的最小堆，堆顶就是第K大的数,时间复杂度O(NlogK)。
（10个数找第3大的数，首先任意3个数，建成最小堆，然后从第4个数开始，与堆顶比较，小忽略，比堆顶大，则舍弃当前堆顶而将这个数作为新的堆顶，并再去维护。。。）
郑重声明：本站内容如果来自互联网及其他传播媒体，其版权均属原媒体及文章作者所有。转载目的在于传递更多信息及用于网络分享，并不代表本站赞同其观点和对其真实性负责，也不构成任何其他建议。
