侧边栏壁纸
  • 累计撰写 247 篇文章
  • 累计创建 16 个标签
  • 累计收到 0 条评论

目 录CONTENT

文章目录

解决 TopK 问题的利器(下):堆排序及其应用

kaixindeken
2021-04-22 / 0 评论 / 0 点赞 / 90 阅读 / 960 字

堆排序

堆排序的过程其实就是不断删除堆顶元素的过程。如果构建的是大顶堆,逐一删除后堆顶元素构成的序列是从大到小排序;如果构建的是小顶堆,逐一删除堆顶元素后构成的序列是从小到大排序。而这其中的原理,就是我们在上一篇提到的:对于大顶堆,堆顶一定是最大值;对于小顶堆,堆顶一定是最小值。

但是这里有一个问题,每次从堆顶删除元素后,需要从子节点中取值补齐堆顶,依次类推,直到叶子节点,就会致使存储堆的数组出现「空洞」:

1.png

解决办法是将数组中的最后一个元素(最右边的叶子节点)移到堆顶,再重新对其进行堆化:

1.png

复杂度分析

对堆排序而言,分为两个阶段,一个是堆的构建,一个是堆顶元素的删除。对于 n 个节点的堆化而言,通过数组存储,对应的时间复杂度是 O(n),对于堆顶元素的删除而言,需要遍历 n 个节点,并且,每次删除后需要重新堆化,对应的平均时间复杂度是 O(nlogn)。所以综合下来,堆排序的时间复杂度和快速排序、归并排序一样,是 O(nlogn)。

堆排序的过程中,涉及到不相邻元素的交换(删除堆顶元素的时候),所以不是稳定的排序算法。

我们在删除堆顶元素的时候,使用了额外的存储空间存放被删除的堆顶元素,但是,我们也可以对这个过程进行优化,从而做到原地排序,感兴趣的同学可以试试。

堆排序的应用

  • 优先级队列:在优先级队列中,数据的出队顺序不是先进先出,而是按照优先级来,优先级最高的,最先出队,背后的原理就是不断删除堆顶元素。
  • 实现 TopK 排行榜:日常开发中,经常遇到类似求销售额 Top10,浏览数 Top10,点赞数 Top10 之类的需求,也可以通过堆排序来实现,原理就是维护一个大小为 K 的小顶堆,有新数据进入后,如果值比堆顶元素大,则删除堆顶元素,最终这个小顶堆就是 TopK 数据了。
0

评论区