雅乐网

计算机技术、学习成长

计算机 » 算法 » 堆和堆排序

堆和堆排序

数据结构中的堆和程序语言中的堆的意义并不相同,这里的堆是一种数据结构。二叉堆可以分为最大堆和最小堆,这里介绍最大堆。在最大堆中,结点的值满足堆的性质:除了根节点外,所有结点都不会比它的父节点大。

可以看到,逻辑上的堆是二叉树,但堆的物理结构却是数组,这得益于完全二叉树的性质:

假设数组下标从0开始,二叉树中父亲和孩子的关系可以方便的通过下标计算得到(图中数字是下标而不是实际的值)

scrn20160107173106

堆的主要操作

最大堆主要有三种操作:获取最大值,向堆中插入元素并保持堆的性质,删除最大值并保持堆的性质。

由于最大堆的定义,堆中元素最大值必定出现在树根,也就是下标0的地方,因此获取最大值可以在常数时间完成。

插入元素

插入元素插入数组尾部,这样仍然保持了完全二叉树的性质,但堆序性可能得到破坏。

这可以通过比较新插入元素和它的父节点元素的值,如果新插入的元素更大,则要与父节点交换。交换后,新的结点和新的父节点又面临相同的问题。反复执行到新结点比父节点小或者到根节点,这个过程就可以停止。

250716042838348

由于完全二叉树树高为O(logn),在最坏情况下,需要O(logn)的时间完成插入过程。

但是,由于树中大部分结点都位于底层,实际插入的过程中,甚至只需要常数时间,上滤过程就可以终止。

删除最大元素

最大元素位于树根处,为了保持完全二叉树的形状,将尾部元素移到根节点处,然后通过下滤过程来重新调整使之满足堆序性。

每次比较根节点和两个孩子节点中的较大者,若不满足堆序性就进行交换。

scrn20160107175719

在最坏情况下,时间复杂度也是树高,即O(logn)

批量建堆

批量建堆采取从下到上逐渐下滤的过程,左右的叶子结点都看做一个满足堆序性的堆。只需要从最后一个非叶节点开始,从下到上,从右到左的对每个结点进行下滤。这需要遍历n/2个结点,每个结点所用时间是该节点的高度。由于树中大部分结点位于底部,所以大部分结点高度都很小。

scrn20160107215246

实际上,完全二叉树中,最底层元素最多n/2个,而倒数第二层元素最多n/4个,依次类推。高度为h的元素最多有n/(2^h)个元素,每个元素下滤用时为h ,依次求和

$$ \sum_{h=0}^{h=lgn} \frac{n}{2^h} h = n \sum_{h=0}^{h=lgn} \frac{h}{2^h} <  n \sum_{h=0}^{\infty} h (\frac{1}{2})^h$$

因为 $$ \sum_{h=0}^{\infty} h x^h = x \sum_{h=0}^{\infty} h x^{h-1} = x \sum_{h=0}^{\infty} \frac{d(x^h)}{dx} = x \frac{d (\sum_{h=0}^{\infty} x^h )}{dx} = x \frac{d (\frac{1}{1-x})}{dx} = \frac{x}{(1-x)^2}$$

因此$$\sum_{h=0}^{\infty} h (\frac{1}{2})^h = \frac{\frac{1}{2}}{(1-(\frac{1}{2})^2)} = 2$$

因此时间复杂度为 O(n)

堆排序

类似于选择排序的过程,只不过这次选择前半部分的最大值不再直接遍历,而是通过堆来快速得到,然后用时O(logn)重新调整堆。这样总的用时为O(nlogn)。

c++实现

 

如果文章对你有帮助,欢迎点赞或打赏(金额不限)。你的打赏将全部用于支付网站服务器费用和提高网站文章质量,谢谢支持。

版权声明:

本文由 原创,商业转载请联系作者获得授权。
非商业转载请注明作者 雅乐网 ,并附带本文链接:
http://www.yalewoo.com/heap_and_heapsort.html

上一篇:

下一篇:

我要评论

验证码*: 5 + 9 =