,kn}是堆,则堆顶元素(或完全二叉树的根)必为序列中n个元素的最大值(或最小值)....spm=1001.2014.3001.5502
建堆的时间复杂度
建堆有两种方式,一种是从堆顶开始向下建堆,另一种是从堆尾开始向上建堆.乍一听好像两种建堆方式除了向上调整和向下调整方式不同之外没什么区别...向下调整的建堆方式的时间复杂度为
向下调整建堆是优于向上调整建堆的....我们先模拟一下向上建堆的过程:
即数组逐渐向后遍历,模拟向堆中插入元素:
(ps:此处建堆也可以使用向下建堆的思路,时间复杂度会更小,但要注意的是,向下建堆时,我们对数组的遍历是从最后一个叶子结点的父节点开始向前遍历并向下调整的...对于Top-k问题,最容易想到的方法是先整体排序,再取前k个,但当数据量非常大时(可能都无法加载到内存上),排序就不是一个很好的解决方法了.