八十四、堆排序解决TopK问题

@Author：Runsen

上次介绍了堆排序，这次介绍堆排序常见的应用场景TopK问题和。

利用堆求TopK问题

TopK问题是一个堆排序典型的应用场景。

题目是这样的：假设，我们想在大量的数据，如 100 亿个整型数据中，找到值最大的 K 个元素，K 小于 10000。对此，你会怎么做呢？

对标的是Leetcode第215题：数组中的第K个最大元素。

具体链接：https://leetcode-cn.com/problems/kth-largest-element-in-an-array/

在未排序的数组中找到第 k 个最大的元素。请注意，你需要找的是数组排序后的第 k 个最大的元素，而不是第 k 个不同的元素。

示例 1:

输入: [3,2,1,5,6,4] 和 k = 2
输出: 5
示例 2:

输入: [3,2,3,1,2,4,5,5,6] 和 k = 4
输出: 4

  

 

  
1
  
2
  
3
  
4
  
5
  
6
  
7
  
8
 

经典的TopK问题还有：最大（小） K 个数、前 K 个高频元素、第 K 个最大（小）元素

对此TopK问题本质上是一个排序问题，排序算法一共有十个，这个还有很多排序算法没有介绍过。

至于为什么TopK问题最佳的答案是堆排序？其实在空间和时间的复杂度来考量，虽说快排是最好的排序算法，但是对于100亿个元素从大到小排序，然后输出前 K 个元素值。

可是&#x

文章来源: maoli.blog.csdn.net，作者：刘润森！，版权归原作者所有，如需转载，请联系作者。

原文链接：maoli.blog.csdn.net/article/details/111770759