堆排序之Top-K问题

作者：你好赵伟 | 2024-06-14 06:36:32

踩

top-k

概念:即求数据结合中前k个最大的元素或者最小的元素，一般数据都比较大

（eg：专业前几，国服前百等）；

对于Top-K问题，相信大家最先想到的就是排序，但是那样的话时间复杂度太大。最佳的方法就是利用堆排序，具体思路如下：
一.进行排序

进行排序每进行一次上下交换的时间复杂度为o（logN），对N个数进行操作，其时间复杂度为o（N*logN）

二.建立N个数的大堆

建立大堆之前先排序，时间复杂度为o（N），然后取头部最大的那个数，再利用取top和pop来实现,时间复杂度为o（k*logN），总的时间复杂度为o（N+k*logN）。

三.建立k个数的小堆

1.首先利用前k个数建立一个小堆

2.剩下的N-k个数依次与堆顶的数据相比，如果比堆顶的数据大，就替代堆顶数据进入堆

声明：本文内容由网友自发贡献，不代表【wpsshop博客】立场，版权归原作者所有，本站不承担相应法律责任。如您发现有侵权的内容，请联系我们。转载请注明出处：https://www.wpsshop.cn/w/你好赵伟/article/detail/716843