排序算法是個(gè)老生常談的問(wèn)題赢底，筆試要考窄刘，面試也問(wèn)振劳，不過(guò)翻來(lái)覆去也就那幾個(gè)花樣吧。大概理解一下各個(gè)算法的原理惫撰，記下表格里的數(shù)據(jù)，然后再試試手撕代碼檐薯，基本上就沒(méi)問(wèn)題了练俐。
從表格里可以看出，堆排序是一個(gè)時(shí)間和空間復(fù)雜度都比較優(yōu)秀的算法谭羔，至于它的原理华糖，看懂是肯定能輕易看懂的麦向，但是我總覺得如果你不自己親手寫一遍瘟裸，就很容易忘記。并且诵竭，用遞歸的話话告，代碼也是很簡(jiǎn)短的兼搏，還沒(méi)寫過(guò)的同學(xué)，不妨自己試著敲一下吧hhh沙郭。
因?yàn)樘脹](méi)寫博客了覺得不能這么頹廢下去佛呻，所以今天打算好好整理堆排序的相關(guān)知識(shí)點(diǎn)，同時(shí)講一下面試時(shí)經(jīng)常會(huì)被問(wèn)到的TopK問(wèn)題病线。
堆排序
1. 什么是堆
堆（heap）是一種數(shù)據(jù)結(jié)構(gòu)吓著，也被稱為優(yōu)先隊(duì)列（priority queue）。隊(duì)列中允許的操作是先進(jìn)先出（FIFO）送挑，在隊(duì)尾插入元素绑莺，在隊(duì)頭取出元素。而堆也是一樣惕耕，在堆底插入元素纺裁，在堆頂取出元素，但是堆中元素的排列不是按照到來(lái)的先后順序司澎，而是按照一定的優(yōu)先順序排列的欺缘。這個(gè)優(yōu)先順序可以是元素的大小或者其他規(guī)則。
而二叉堆是一種特殊的堆挤安，它是完全二元樹（二叉樹）或者是近似完全二元樹（二叉樹）谚殊。二叉堆有兩種：最大堆和最小堆。最大堆：父結(jié)點(diǎn)的鍵值總是大于或等于任何一個(gè)子節(jié)點(diǎn)的鍵值蛤铜；最小堆：父結(jié)點(diǎn)的鍵值總是小于或等于任何一個(gè)子節(jié)點(diǎn)的鍵值络凿。如下圖。
2. 堆排序的原理
堆排序（HeapSort）是指利用堆這種數(shù)據(jù)結(jié)構(gòu)所設(shè)計(jì)的一種排序算法昂羡。它的關(guān)鍵在于建堆和調(diào)整堆絮记。步驟主要如下：
- 創(chuàng)建一個(gè)堆；
- 把堆首（最大值）和堆尾互換虐先；
- 把堆的尺寸縮小1怨愤，并調(diào)整堆，把新的數(shù)組頂端數(shù)據(jù)調(diào)整到相應(yīng)位置蛹批；
- 重復(fù)步驟 2撰洗，直到堆的尺寸為1，此時(shí)排序結(jié)束腐芍。
當(dāng)然差导，光看文字肯定不能很直觀地理解，我們跟著圖示來(lái)學(xué)習(xí)吧猪勇。
現(xiàn)在设褐，我們有一個(gè)待排序的數(shù)組 {2, 4, 3, 7, 5, 8}，我們通過(guò)構(gòu)建最大堆的方法來(lái)排序。
- 步驟說(shuō)明如下：
1. 將待排序的數(shù)組視作完全二叉樹助析，按層次遍歷犀被。
2. 找到二叉樹的最后一個(gè)非葉子節(jié)點(diǎn)，也就是最后一個(gè)節(jié)點(diǎn)的父節(jié)點(diǎn)外冀。即是 (len-1)/2 索引在的位置寡键。如果其子節(jié)點(diǎn)的值大于其本身的值，則把它和較大子節(jié)點(diǎn)進(jìn)行交換雪隧，即將數(shù)字3和8交換西轩。如果并沒(méi)有子節(jié)點(diǎn)大于它，則無(wú)需交換脑沿。
3. 循環(huán)遍歷遭商，繼續(xù)處理前一個(gè)節(jié)點(diǎn)，由于此時(shí) 4<7 捅伤，因此再次交換劫流。
4. 循環(huán)遍歷，繼續(xù)處理前一個(gè)節(jié)點(diǎn)丛忆，由于此時(shí) 2<8 祠汇，因此再次交換。注意：如果某個(gè)節(jié)點(diǎn)和它的某個(gè)子節(jié)點(diǎn)交換后熄诡，該子節(jié)點(diǎn)又有子節(jié)點(diǎn)可很，系統(tǒng)還需要再次對(duì)該子節(jié)點(diǎn)進(jìn)行判斷，做相同處理凰浮。
5. 遍歷完成后得到一個(gè)最大堆我抠。將每次堆排序得到的最大元素與當(dāng)前規(guī)模的數(shù)組最后一個(gè)元素（假設(shè)下標(biāo)為i）交換，然后再繼續(xù)調(diào)整前 i - 1 的數(shù)組袜茧。遍歷終止之后菜拓，得到一個(gè)自小到大的排序數(shù)組。
C++代碼實(shí)現(xiàn)如下
void adjust(vector<int> &arr, int index, int len) {
int left = 2 * index + 1;
int right = 2 * index + 2;
int max_index = index;
if (left < len && arr[left] > arr[max_index]) max_index = left;
if (right < len && arr[right] > arr[max_index]) max_index = right;
if (max_index != index) {
swap(arr[max_index], arr[index]);
adjust(arr, max_index, len); // 繼續(xù)調(diào)整子節(jié)點(diǎn)
}
}
void heapSort(vector<int> &arr, int len) {
// 將數(shù)組進(jìn)行堆排序
for (int i = len / 2 - 1; i >= 0; i--) {
adjust(arr, i, len);
}
// 將每次堆排序得到的最大元素與當(dāng)前規(guī)模的數(shù)組最后一個(gè)元素交換
for (int i = len - 1; i >= 1; i--) {
swap(arr[0], arr[i]);
adjust(arr, 0, i);
}
}
海量TopK問(wèn)題
劍指Offer有這樣一道題笛厦，求最小的K個(gè)數(shù)纳鼎，題目描述：輸入n個(gè)整數(shù)，找出其中最小的K個(gè)數(shù)裳凸。例如輸入 4贱鄙，5，1姨谷，6逗宁，2，7梦湘，3瞎颗，8 這8個(gè)數(shù)字件甥，則最小的4個(gè)數(shù)字是 1，2言缤，3嚼蚀，4禁灼。
而在面試的時(shí)候管挟，我們也可能遇到這樣的問(wèn)題：有一億個(gè)浮點(diǎn)數(shù)，如何找出其中最大的10000個(gè)弄捕？
這類問(wèn)題我們把稱為TopK問(wèn)題：指從大量數(shù)據(jù)（源數(shù)據(jù)）中獲取最大（或最衅ⅰ）的K個(gè)數(shù)據(jù)。
最容易想到的方法當(dāng)然是全部排序再進(jìn)行查找守谓，然而時(shí)間復(fù)雜度怎么也要O(nlog?n)穿铆，當(dāng)n極其大時(shí)，該算法占用的內(nèi)存也emmm斋荞。而我們題目所要求返回的只是前K個(gè)數(shù)據(jù)荞雏，所以沒(méi)必要全部排序，做那么多無(wú)用功平酿。我們可以先取下標(biāo) 0~k-1 的局部數(shù)組凤优，用它來(lái)維護(hù)一個(gè)大小為K的數(shù)組，然后遍歷后續(xù)的數(shù)字蜈彼，進(jìn)行比較后決定是否替換筑辨。這時(shí)候堆排序就派上用場(chǎng)了。我們可以將前K個(gè)數(shù)字建立為一個(gè)最行夷妗（大）堆棍辕，如果是要取最大的K個(gè)數(shù)，則在后續(xù)遍歷中还绘，將數(shù)字與最小堆的堆頂數(shù)字進(jìn)行比較楚昭，若比它大，則進(jìn)行替換拍顷，然后再重新調(diào)整為最大堆哪替。整個(gè)過(guò)程直至所有數(shù)字遍歷完為止。時(shí)間復(fù)雜度為O(n*log?K)菇怀，空間復(fù)雜度為K凭舶。
C++代碼實(shí)現(xiàn)如下
class Solution {
public:
void adjust(vector<int> &arr, int index, int len) {
int left = 2 * index + 1;
int right = 2 * index + 2;
int max_index = index;
if (left < len && arr[left] > arr[max_index]) max_index = left;
if (right < len && arr[right] > arr[max_index]) max_index = right;
if (max_index != index) {
swap(arr[max_index], arr[index]);
adjust(arr, max_index, len);
}
}
void heapSort(vector<int> &arr, int len) {
for (int i = len / 2 - 1; i >= 0; i--) {
adjust(arr, i, len);
}
// for (int i = len - 1; i >= 1; i--) {
// swap(arr[0], arr[i]);
// adjust(arr, 0, i);
// }
}
vector<int> GetLeastNumbers_Solution(vector<int> input, int k) {
if (k <= 0 || k > input.size()) {
vector<int> nullVec;
return nullVec;
}
// 因?yàn)橐∽钚〉膋個(gè)數(shù)，所以取前k個(gè)數(shù)字構(gòu)建一個(gè)最大堆
// 相反爱沟，如果是取最大的k個(gè)數(shù)帅霜，則構(gòu)建一個(gè)最小堆
vector<int> sortedArray(input.begin(), input.begin() + k);
heapSort(sortedArray, k);
// 將后面的數(shù)字與這個(gè)構(gòu)建好的二叉堆進(jìn)行比較
for (int i = k; i < input.size(); i++) {
if (input[i] < sortedArray[0]) {
sortedArray[0] = input[i];
adjust(sortedArray, 0, k);
}
}
for (int i = k - 1; i >= 1; i--) {
swap(sortedArray[0], sortedArray[i]);
adjust(sortedArray, 0, i);
}
return sortedArray;
}
};
相似的TopK問(wèn)題還有：
- 有10000000個(gè)記錄，這些查詢串的重復(fù)度比較高呼伸，如果除去重復(fù)后身冀，不超過(guò)3000000個(gè)钝尸。一個(gè)查詢串的重復(fù)度越高，說(shuō)明查詢它的用戶越多搂根，也就是越熱門珍促。請(qǐng)統(tǒng)計(jì)最熱門的10個(gè)查詢串，要求使用的內(nèi)存不能超過(guò)1GB剩愧。
- 有10個(gè)文件猪叙，每個(gè)文件1GB，每個(gè)文件的每一行存放的都是用戶的query仁卷，每個(gè)文件的query都可能重復(fù)穴翩。按照query的頻度排序。
- 有一個(gè)1GB大小的文件锦积，里面的每一行是一個(gè)詞芒帕，詞的大小不超過(guò)16個(gè)字節(jié)，內(nèi)存限制大小是1MB丰介。返回頻數(shù)最高的100個(gè)詞背蟆。
- 提取某日訪問(wèn)網(wǎng)站次數(shù)最多的那個(gè)IP。
- 10億個(gè)整數(shù)找出重復(fù)次數(shù)最多的100個(gè)整數(shù)哮幢。
- 搜索的輸入信息是一個(gè)字符串带膀，統(tǒng)計(jì)300萬(wàn)條輸入信息中最熱門的前10條，每次輸入的一個(gè)字符串為不超過(guò)255B家浇，內(nèi)存使用只有1GB本砰。
- 有1000萬(wàn)個(gè)身份證號(hào)以及他們對(duì)應(yīng)的數(shù)據(jù)，身份證號(hào)可能重復(fù)钢悲，找出出現(xiàn)次數(shù)最多的身份證號(hào)点额。
- 等等...
對(duì)于這類問(wèn)題，比如上面第1個(gè)莺琳，可以先利用hash表將查詢串存儲(chǔ)并計(jì)數(shù)还棱，然后再構(gòu)建最小堆，將查詢串的個(gè)數(shù)進(jìn)行比較從而得到結(jié)果惭等。核心思想都是一樣的珍手。
今天就先寫到這里吧，困了睡覺去 Orz
