如果數據量堪稱是海量的時候，我們還需要耗費大量的時間空間排序后在排序完成后取他們的前k個最大值或者是前k個最小值么？面對海量數據，并不要求所有的數據都排序成有序序列時，我們沒有必要采用各式各樣的排序算法對所有數都進行排序后再獲得TopK值，這道題在面試題中可能會經常碰到，考察的就是排序中的堆排序。

輸入：所有需要排序的數據，記作a1a2...ak，k值

輸出：k個最大元素

對a1a2...ak建小頂堆（最小堆），根節點記為aroot

遍歷剩余的元素，即ak+1ak+2ak+3....an：

如果元素值小于aroot，則跳過，此值和我們所需要的K個最大值一定是無關的。

如果元素值大于aroot，則將該元素和aroot替換，并調整堆，使得符合小頂堆。

遍歷結束，小頂堆上所有的節點就是我們所需要求的最大值Topk。

相反，求最大值Topk則利用大頂堆。

那么為什么我們不能選擇其他的排序方法呢？

在內部排序方法中，一趟排序后只有直接選擇排序和起泡排序可以選出一個最大的或者是最小的元素，并加入到已有的有序子序列中，但是要比較n-1次，再選次大元素的時候有需要比較n-2詞，這樣排序的時間復雜度為O(n2)。如果是海量數據的話，則意味著n會很大，那么為了選擇前k個最大的元素那么它的時間復雜度過大，不能采用這種方法。

而插入排序、快速排序、歸并排序以及基數排序等排序方法雖然時間性能比較好，但是需要把所有元素都完全排序完成，直到最后才能確定各元素的位置。

而堆排序，在未結束全部排序前，就可以得出部分排序結果。在對前k個元素建立堆后，堆頂元素則是最大元素，調堆又能獲得次大元素，這樣就可以獲得前k個最大元素。一般在數據量比較大時選出k個最大或者是最小的元素使用的一般是堆排序。

首先堆排序建堆比較的次數至多不超過4n,對于深度為k的堆，在調堆算法中關鍵字比較的次數至多為2(k-1)次，且輔助空間為O(1),所以在這種情況下我們會選擇堆排序。

既然講到了堆排序，下面就涉及以下堆排序的思想：

建堆過程：將待排序序列看作是一個完全二叉樹，不斷從n/2的下界開始篩選，不斷篩選最終建成堆，可以看下面的建堆過程，圖示為建小頂堆的過程。

調堆過程：將堆頂元素與堆的最后一個記錄交換，之后將序列中的前n-1記錄重新調整為堆，再將的堆頂記錄和當前堆序列的最后一個記錄交換，如此反復直到排序結束。

堆排序的優點：時間性能與樹形選擇排序屬于同一量級，并且只需要一個記錄大小供交換用的輔助空間，調堆時子女只和雙親比較。

?

總結

以上是生活随笔為你收集整理的插播面试题：海量数据求最大值Topk或者是最小值Topk的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。