堆排序在工業(yè)屆應(yīng)用很廣泛，在實際應(yīng)用中的top-k問題很適合用堆的思想完成。

I、上帝視角看堆排序

堆排序就是利用堆（常用大頂堆）進(jìn)行排序的方法。它的基本思想就是，將待排序的序列構(gòu)成一個大頂堆。此時，整個序列的最大值就是對頂?shù)母Y(jié)點。將它移走（與堆尾元素交換），此時末尾元素就是最大值，然后將剩余的n-1個序列重新構(gòu)成了一個堆，這樣就得到n個元素中的次大值，如此反復(fù)執(zhí)行，便得到一個有序序列。

上面的描述可以用下面的示意圖表示：

堆排序示意圖1

堆排序示意圖2

II、堆排序?qū)崿F(xiàn)

對于堆排序的實現(xiàn)，主要需要考慮兩個問題：
1、如何由一個無序序列構(gòu)建一個堆；
2、調(diào)整剩余元素使之構(gòu)成一個新堆；

#include <iostream>
#include <vector>

using namespace std;

void adjustHeap(vector<int>& vec, int p, int len) {
    int curParent = vec[p];
    int child = 2*p+1;  //左孩子
    while (child < len) {   //有孩子
        if (child + 1 < len && vec[child] < vec[child+1]) {     //比較左右孩子
            child++;    //變?yōu)橛液⒆?        }
        if (curParent < vec[child]) {
            //沒有講curParent賦值給孩子是因為還要迭代子樹
            //如果其孩子中有大的，會上移，curParent還要繼續(xù)下移
            vec[p] = vec[child];
            p = child;  //向下迭代
            child = 2*p + 1;    //更新迭代坐標(biāo)
        }
        else break;
    }
    vec[p] = curParent;
}


void heapSort(vector<int>& vec, int len) {
    //建立堆，從最底層的父結(jié)點開始
    for (int i = len/2-1; i >= 0; --i)
        adjustHeap(vec, i, len);
    for (int i = len - 1; i >=0; --i) {
        swap(vec[0], vec[i]);

        adjustHeap(vec, 0, i);  //調(diào)整剩余元素的建堆

    }
}

int main()
{
    vector<int> vec = {6,3,4,5,1,7};
    heapSort(vec, vec.size());
    for (auto i : vec)
        cout << i << ",";

    return 0;
}

【參考】
[1] 《大話數(shù)據(jù)結(jié)構(gòu)》

歡迎轉(zhuǎn)載，轉(zhuǎn)載請注明出處wenmingxing 堆排序初探