🎈 作者：Linux猿

🎈 簡介：CSDN博客專家🏆，華為云享專家🏆，Linux、C/C++、面試、刷題、演算法盡管咨詢我，關注我，有問題私聊！

🎈 關注專欄：圖解資料結構和演算法 （優質好文持續更新中……）🚀

🎈 歡迎小伙伴們點贊👍、收藏?、留言💬

目錄

🍓一、什么是堆

🍓二、堆排序

?2.1 演算法原理

?2.2 演算法步驟

?2.3 實體演示

?2.4 代碼實作

?2.5 堆調整原理

🍓三、實體講解

?3.1 求第 k 大元素

🚩3.1.1 演算法思路

🚩3.1.1 代碼實作

?3.2 求前 k 高頻率的元素

🚩3.2.1 演算法思路

🚩3.2.2 代碼實作

🍓四、總結

🍓一、什么是堆

堆屬于二叉樹的一種，它是一棵完全二叉樹，堆有大頂堆和小頂堆之分，大頂堆是任意節點大于其左右子節點，小頂堆是任意節點大于其左右子節點，如下所示：

在上圖中，每個節點的值都大于左右孩子節點的值，例如：25 大于 13 和 10，13 大于 2 和 8 等，

使用上面的資料來構建一個小頂堆，如下所示：

在上圖的小頂堆中， 每個節點都小于左右孩子節點，左右孩子節點誰大誰小并沒關系，重點是不能比父節點大，可以看到，2 比孩子節點 8 和 7 都小，8 比孩子節點 13 和 25 都小，

🔶🔶🔶🔶🔶 我是分割線 🔶🔶🔶🔶🔶

🍓二、堆排序

這里以大頂堆為例進行講解，

?2.1 演算法原理

將待排序元素組成一個大頂堆，每次取出堆頂元素（堆頂是最大的元素），讓最后一個元素成為堆頂節點，重新調整堆，讓其成為大頂堆，再次交換堆頂元素，直到所有元素都有序，從而實作對資料的排序，

?2.2 演算法步驟

（1）將待排序元素構建一個大頂堆；

（2）最后一個節點與根節點交換，此時，不再是大頂堆；

（3）將堆重新調整堆為大頂堆；

（4）重復步驟 2 ~ 3，直到所有元素都有序，

?2.3 實體演示

下面來看一個實體，

假設有 A[ ] = {10, 8, 9, 2, 13, 7, 25}，這里以大頂堆為例實作從小到大排序，

（1）初始堆，如下所示：

（2）將待排序元素構建成一個大頂堆，如下所示：

（3）將節點 9 與 節點 25 交換，交換后如下所示：

（4）標記為紅色的節點表示已經有序，不再參與排序，這時候，堆不滿足大頂堆，重新調整堆為大頂堆，調整后如下所示：

（5）將節點 13 與 7 交換，交換后，如下所示：

（6）交換后，此時的堆不再是大頂堆，重新調整為大頂堆，調整后如下所示：

（7）交換節點 10 與 8，交換后如下所示：

（8）此時堆不再是大頂堆，重新調整為大頂堆，如下所示：

（9）交換節點 9 和 2，交換后，如下所示：

（10）將堆重新調整為大頂堆，如下所示：

（11）交換 8 和 7 的值，如下所示：

（12）將堆調整為大頂堆，可以看到，當前堆已是大頂堆，然后，交換節點 2 和 7，如下所示：

（13）此時，整個對從上到下，從左到右是遞增的，實際在陣列中存盤是這樣的：

在上圖中，節點下面的數字表示節點在陣列中的位置，一般是從下標 1 開始存盤，因為這樣方便計算父節點和子節點之間的關系，如下所示：

（1）左孩子節點的下標 = 父節點的下標 * 2

（2）右孩子節點的下標 = 父節點的下標 * 2 + 1

?2.4 代碼實作

#include <iostream>

using namespace std;

//向下調整堆, 從 idx 節點開始往下調整
void adjustHeap(int a[], int idx, int Len){
    while(idx*2+1 < Len) {
        int temp = idx*2 + 1;
        if(temp+1 < Len && a[temp+1] > a[temp]) {
            temp++;
        }
        if(a[idx] < a[temp]) {
            swap(a[idx], a[temp]);
            idx = temp;
        } else break;
    }
}

/*
 * 堆排序
 * g[] : 待排序陣列
 * n   : 元素個數
 */
void heapSort(int g[], int n){
    //先建立大頂堆
    for(int i = (n-1)/2; i >= 0; --i){
        adjustHeap(g, i, n);
    }
    //排序，每次都會有一個元素有序
    for(int i = 0;i < n; ++i){
        swap(g[0], g[n-i-1]);
        adjustHeap(g, 0, n-i-1);
    }
}

int main()
{
    int n = 8;
    int g[] = {5, 7, 9, 3, 1, 8, 6, 2};
    heapSort(g, n); // 呼叫堆排序
    for(int i = 0; i < n; ++i) {
        cout<<g[i]<<" ";
    }
    cout<<endl;
    return 0;
}

在堆排序的程序中，重點是調整堆，建立大頂堆的時候（heapSort 中第一個 for 回圈），是從下往上依次調整每個節點，使得每個節點都滿足大頂堆的條件，

正式排序的時候，每次只需要交換根節點，重新調整堆即可，只需要調整新的根節點，因為只有新的根節點不滿足堆的定義，

?2.5 堆調整原理

堆排序中，最重要的就是堆的調整了，下面就可以下圖的為例子進行講解，如下所示：

在上圖中，只有 3 是不符合條件的，下面就來調整下 3 節點，動圖如下所示：

在上圖中，3 先與 13 交換，然后，再與 8 交換，交換后便成為一個大頂堆，

🔶🔶🔶🔶🔶 我是分割線 🔶🔶🔶🔶🔶

🍓三、實體講解

?3.1 求第 k 大元素

給定整數陣列 nums 和整數 k，請回傳陣列中第 k 個最大的元素，

🚩3.1.1 演算法思路

對陣列 nums 中的元素進行堆排序，因為堆排序可以每次確定一個最大值，所以只需要求解到第 k 個最大值即可，如果使用其它排序演算法，要排序所有元素，這就顯示出了堆排序的優勢，并不需要全部排序完才找到第 k 大的元素，

🚩3.1.1 代碼實作

#include <iostream>
#include <vector>
using namespace std;

class Solution {
public:
    //向下調整堆
    void adjustHeap(vector<int>& nums, int idx, int Len) {
        while(idx*2+1 < Len) {
            int temp = idx*2 + 1;
            if(temp + 1 < Len && nums[temp+1] > nums[temp]){
                temp++;
            }
            if(nums[idx] < nums[temp]) {
                swap(nums[idx], nums[temp]);
                idx = temp;
            } else break;
        }
    }
    int findKthLargest(vector<int>& nums, int k) {
        //先建立大頂堆
        int n = nums.size();
        for(int i = (n-1)/2; i >= 0; --i){
            adjustHeap(nums, i, n);
        }
        for(int i = 0; i < nums.size(); ++i) {
            cout<<nums[i]<<" ";
        }
        cout<<endl;
        //排序
        for(int i = 0;i < k - 1; ++i){
            swap(nums[0], nums[n-i-1]);
            adjustHeap(nums, 0, n-i-1);
        }
        return nums[0];
    }
};

int main()
{
    int g[] = {5, 7, 9, 3, 1, 8, 6, 2};
    vector<int> nums(g, g+8);
    cout<<endl;
    Solution obj;
    int k;
    while(cin>>k) {
        cout<<"The k-th largest number is "<<obj.findKthLargest(nums, k)<<endl;
    }
    return 0;
}

?3.2 求前 k 高頻率的元素

給你一個整數陣列 nums 和一個整數 k ，請你回傳其中出現頻率前 k 高的元素，你可以按任意順序 回傳答案，

🚩3.2.1 演算法思路

這個題目類似于第一個題目，但是需要計算每個整數的頻率，可以使用 map 進行統計，然后就可以使用堆排序求第 k 大了，

🚩3.2.2 代碼實作

#include <iostream>
#include <vector>
#include <map>
using namespace std;

class Solution {
public:
    //向下調整堆
    void adjustHeap(vector<pair<int, int> >& nums, int idx, int Len) {
        while(idx*2+1 < Len) {
            int temp = idx*2 + 1;
            if(temp + 1 < Len && nums[temp+1].second > nums[temp].second){
                temp++;
            }
            if(nums[idx].second < nums[temp].second) {
                swap(nums[idx], nums[temp]);
                idx = temp;
            } else break;
        }
    }
    vector<int> topKFrequent(vector<int>& nums, int k) {
        map<int, int>mp;
        for(int i = 0; i < (int)nums.size(); ++i) {
            mp[nums[i]]++;
        }
        vector<pair<int, int> >hep;
        map<int, int>::iterator it;
        for(it = mp.begin(); it != mp.end(); ++it) {
            hep.push_back(pair<int, int>(it->first, it->second));
        }
        //先建立大頂堆
        int n = hep.size();
        for(int i = (n-1)/2; i >= 0; --i){
            adjustHeap(hep, i, n);
        }
        //排序
        vector<int> ans;
        for(int i = 0;i < k - 1; ++i){
            ans.push_back(hep[0].first);
            swap(hep[0], hep[n-i-1]);
            adjustHeap(hep, 0, n-i-1);
        }
        ans.push_back(hep[0].first);
        return ans;
    }
};

int main()
{
    int g[] = {1, 2, 2, 1, 3, 8, 8, 1};
    vector<int> nums(g, g+8);
    cout<<endl;
    Solution obj;
    int k;
    while(cin>>k) {
        vector<int> ans = obj.topKFrequent(nums, k);
        for(int i = 0; i < ans.size(); ++i) {
            cout<<ans[i]<<" ";
        }
        cout<<endl;
    }
    return 0;
}

🔶🔶🔶🔶🔶 我是分割線 🔶🔶🔶🔶🔶

🍓四、總結

堆排序經常用在求第 K 大上，因為堆的每次調整，根元素一定是最大/小的元素，

歡迎關注下方👇👇👇公眾號👇👇👇，獲取更多福利等你來領🤞（比心）！