@Author：Runsen

上次介紹了堆排序，這次介紹堆排序常見的應(yīng)用場景TopK問題和。

利用堆求TopK問題

TopK問題是一個(gè)堆排序典型的應(yīng)用場景。

題目是這樣的：假設(shè)，我們想在大量的數(shù)據(jù)，如 100 億個(gè)整型數(shù)據(jù)中，找到值最大的 K 個(gè)元素，K 小于 10000。對(duì)此，你會(huì)怎么做呢？

對(duì)標(biāo)的是Leetcode第215題：數(shù)組中的第K個(gè)最大元素。

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

在未排序的數(shù)組中找到第 k 個(gè)最大的元素。請(qǐng)注意，你需要找的是數(shù)組排序后的第 k 個(gè)最大的元素，而不是第 k 個(gè)不同的元素。

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

經(jīng)典的TopK問題還有：最大（小） K 個(gè)數(shù)、前 K 個(gè)高頻元素、第 K 個(gè)最大（小）元素

對(duì)此TopK問題本質(zhì)上是一個(gè)排序問題，排序算法一共有十個(gè)，這個(gè)還有很多排序算法沒有介紹過。

至于為什么TopK問題最佳的答案是堆排序？其實(shí)在空間和時(shí)間的復(fù)雜度來考量，雖說快排是最好的排序算法，但是對(duì)于100億個(gè)元素從大到小排序，然后輸出前 K 個(gè)元素值。

可是&#x

總結(jié)

以上是生活随笔為你收集整理的八十四、堆排序解决TopK问题的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。