堆是一種二叉樹結(jié)構(gòu)，有兩種主要類型：最大堆和最小堆。在最大堆中，每個(gè)節(jié)點(diǎn)的值都大于或等于其子節(jié)點(diǎn)的值；而在最小堆中，每個(gè)節(jié)點(diǎn)的值都小于或等于其子節(jié)點(diǎn)的值。對(duì)于優(yōu)先隊(duì)列來說，最大堆常常用于實(shí)現(xiàn)。

在堆中，根節(jié)點(diǎn)的元素具有最高（或最低）優(yōu)先級(jí)，而且這一性質(zhì)對(duì)于整個(gè)堆中的每個(gè)節(jié)點(diǎn)都成立。這確保了當(dāng)我們從堆中移除元素時(shí)，總是移除具有最高（或最低）優(yōu)先級(jí)的元素。

優(yōu)先隊(duì)列的常見操作包括：

• 插入（Insertion）：將元素插入隊(duì)列中。
• 刪除最大（或最?。┰兀阂瞥⒎祷仃?duì)列中具有最高（或最低）優(yōu)先級(jí)的元素。

堆的實(shí)現(xiàn)可以通過數(shù)組或鏈表等數(shù)據(jù)結(jié)構(gòu)。在使用數(shù)組實(shí)現(xiàn)堆時(shí)，父節(jié)點(diǎn)和子節(jié)點(diǎn)之間的關(guān)系可以通過數(shù)組的索引關(guān)系來表示。在C++中，可以使用 std::priority_queue 來實(shí)現(xiàn)優(yōu)先隊(duì)列，它默認(rèn)使用最大堆，也可以通過傳遞自定義比較函數(shù)來實(shí)現(xiàn)最小堆。

01.最后一塊石頭的重量

題目鏈接：https://leetcode.cn/problems/last-stone-weight/

有一堆石頭，每塊石頭的重量都是正整數(shù)。

每一回合，從中選出兩塊 最重的 石頭，然后將它們一起粉碎。假設(shè)石頭的重量分別為 x 和 y，且 x <= y。那么粉碎的可能結(jié)果如下：

• 如果 x == y，那么兩塊石頭都會(huì)被完全粉碎；
• 如果 x != y，那么重量為 x 的石頭將會(huì)完全粉碎，而重量為 y 的石頭新重量為 y-x。

最后，最多只會(huì)剩下一塊石頭。返回此石頭的重量。如果沒有石頭剩下，就返回 0。

示例：

輸入：[2,7,4,1,8,1]
輸出：1
解釋：
先選出 7 和 8，得到 1，所以數(shù)組轉(zhuǎn)換為 [2,4,1,1,1]，
再選出 2 和 4，得到 2，所以數(shù)組轉(zhuǎn)換為 [2,1,1,1]，
接著是 2 和 1，得到 1，所以數(shù)組轉(zhuǎn)換為 [1,1,1]，
最后選出 1 和 1，得到 0，最終數(shù)組轉(zhuǎn)換為 [1]，這就是最后剩下那塊石頭的重量。 

提示：

• 1 <= stones.length <= 30
• 1 <= stones[i] <= 1000

思路

我們可以每次拿出最大的兩個(gè)相比較，有差值就將差值保留，相等就都粉碎，這樣我們很容易想到使用堆去計(jì)算，因?yàn)檫@符合堆的特性，我們可以使用各語言庫中的堆容器來計(jì)算。

1. 創(chuàng)建最大堆（Max Heap）： 通過 priority_queue<int> 創(chuàng)建一個(gè)默認(rèn)為最大堆的優(yōu)先隊(duì)列，將給定的石頭數(shù)組中的元素加入最大堆中。
2. 迭代處理： 使用一個(gè)循環(huán)迭代處理，直到堆中剩余的元素個(gè)數(shù)小于等于1。
3. 從堆中取出兩個(gè)最大的元素，執(zhí)行碎石操作： 每次取出堆中的兩個(gè)最大元素（即石頭的重量最大的兩塊），執(zhí)行碎石操作，計(jì)算碎石后的重量，將結(jié)果加回堆中。
4. 返回結(jié)果： 當(dāng)循環(huán)結(jié)束時(shí)，堆中剩余的元素即為最后一塊石頭的重量，或者堆為空，返回相應(yīng)的結(jié)果。

代碼文章來源地址http://www.zghlxwxcb.cn/news/detail-835012.html

class Solution {
public:
    int lastStoneWeight(vector<int>& stones) {
        priority_queue<int> heap;
        for(int x:stones) heap.push(x);

        while(heap.size()>1){
            int a=heap.top(); heap.pop();
            int b=heap.top(); heap.pop();
            if(a>b) heap.push(a-b);
        }

        return heap.size()?heap.top():0;
    }
};

02.數(shù)據(jù)流中的第 K 大元素

題目鏈接：https://leetcode.cn/problems/kth-largest-element-in-a-stream/

設(shè)計(jì)一個(gè)找到數(shù)據(jù)流中第 k 大元素的類（class）。注意是排序后的第 k 大元素，不是第 k 個(gè)不同的元素。

請(qǐng)實(shí)現(xiàn) KthLargest 類：

• KthLargest(int k, int[] nums) 使用整數(shù) k 和整數(shù)流 nums 初始化對(duì)象。
• int add(int val) 將 val 插入數(shù)據(jù)流 nums 后，返回當(dāng)前數(shù)據(jù)流中第 k 大的元素。

示例：

輸入：
["KthLargest", "add", "add", "add", "add", "add"]
[[3, [4, 5, 8, 2]], [3], [5], [10], [9], [4]]
輸出：
[null, 4, 5, 5, 8, 8]

解釋：
KthLargest kthLargest = new KthLargest(3, [4, 5, 8, 2]);
kthLargest.add(3);   // return 4
kthLargest.add(5);   // return 5
kthLargest.add(10);  // return 5
kthLargest.add(9);   // return 8
kthLargest.add(4);   // return 8

提示：

• 1 <= k <= 104
• 0 <= nums.length <= 104
• -104 <= nums[i] <= 104
• -104 <= val <= 104
• 最多調(diào)用 add 方法 104 次
• 題目數(shù)據(jù)保證，在查找第 k 大元素時(shí)，數(shù)組中至少有 k 個(gè)元素

思路

這里是典型的topk問題，找的是第k個(gè)大的數(shù)，所以我們使用一個(gè)k大的小堆就能很好的解決這個(gè)問題。

在構(gòu)造函數(shù)中，將初始的元素加入最小堆中，并維護(hù)堆的大小為 K，保證堆中只有前 K 大的元素。

當(dāng)有新元素加入時(shí)，將新元素加入最小堆中，然后檢查堆的大小是否超過 K，如果超過則彈出堆頂元素。最終返回當(dāng)前堆頂元素，即為第 K 大的元素。這樣，通過不斷地將新元素加入最小堆，并保持堆的大小為 K，可以在 add 操作后始終保持堆中的元素為前 K 大的元素，而堆頂元素即為第 K 大的元素。

代碼

class KthLargest {
    priority_queue<int,vector<int>,greater<int>> heap;
    int _k;
public:
    KthLargest(int k, vector<int>& nums) {
        _k=k;
        for(int& x:nums){
            heap.push(x);
            if(heap.size()>k) heap.pop();
        }
    }
    
    int add(int val) {
        heap.push(val);
        if(heap.size()>_k) heap.pop();
        return heap.top();
    }
};

/**
 * Your KthLargest object will be instantiated and called as such:
 * KthLargest* obj = new KthLargest(k, nums);
 * int param_1 = obj->add(val);
 */

03.前K個(gè)高頻單詞

題目鏈接：https://leetcode.cn/problems/top-k-frequent-words/

給定一個(gè)單詞列表 words 和一個(gè)整數(shù) k ，返回前 k 個(gè)出現(xiàn)次數(shù)最多的單詞。

返回的答案應(yīng)該按單詞出現(xiàn)頻率由高到低排序。如果不同的單詞有相同出現(xiàn)頻率， 按字典順序 排序。

示例 1：

輸入: words = ["i", "love", "leetcode", "i", "love", "coding"], k = 2
輸出: ["i", "love"]
解析: "i" 和 "love" 為出現(xiàn)次數(shù)最多的兩個(gè)單詞，均為2次。
    注意，按字母順序 "i" 在 "love" 之前。

示例 2：

輸入: ["the", "day", "is", "sunny", "the", "the", "the", "sunny", "is", "is"], k = 4
輸出: ["the", "is", "sunny", "day"]
解析: "the", "is", "sunny" 和 "day" 是出現(xiàn)次數(shù)最多的四個(gè)單詞，
    出現(xiàn)次數(shù)依次為 4, 3, 2 和 1 次。

注意：

• 1 <= words.length <= 500
• 1 <= words[i] <= 10
• words[i] 由小寫英文字母組成。
• k 的取值范圍是 [1, **不同** words[i] 的數(shù)量]

**進(jìn)階：**嘗試以 O(n log k) 時(shí)間復(fù)雜度和 O(n) 空間復(fù)雜度解決。

思路

很顯然這里這是還是topk問題，還是使用堆來解決問題，但是這里有兩個(gè)比較條件，所以我們要注意比較函數(shù)的實(shí)現(xiàn)，主邏輯是找出前k個(gè)出現(xiàn)次數(shù)最多的，所以整體我們建小堆，還有一個(gè)附屬條件，次數(shù)相同時(shí)，字典序小的排在前面，所以在相同次數(shù)時(shí)，我們相對(duì)于字符串建大堆，將字母小的排在前面。

1. 哈希表統(tǒng)計(jì)頻率： 使用 unordered_map 哈希表記錄每個(gè)字符串出現(xiàn)的頻率。
2. 優(yōu)先隊(duì)列： 使用一個(gè)自定義的比較函數(shù)對(duì)象 cmp 作為優(yōu)先隊(duì)列的比較規(guī)則。按照頻率從大到小排序，若頻率相同則按照字符串字典序從小到大排序。遍歷哈希表，將每個(gè)鍵值對(duì)（字符串及其頻率）加入最小堆，并保持堆的大小為 K，當(dāng)堆的大小超過 K 時(shí)，彈出堆頂元素。
3. 結(jié)果處理： 從堆中依次取出前 K 高的字符串，存儲(chǔ)到結(jié)果數(shù)組中。

最終，返回存儲(chǔ)前 K 高字符串的結(jié)果數(shù)組 ret。這樣通過哈希表統(tǒng)計(jì)頻率，并使用優(yōu)先隊(duì)列來維護(hù)前 K 高的頻率，實(shí)現(xiàn)了找出頻率前 K 高的字符串。

代碼

class Solution {
    struct cmp{
        bool operator()(const pair<string,int>& a,const pair<string,int>& b){
            if(a.second==b.second) return a.first<b.first;
            return a.second>b.second;
        }
    };
public:
    vector<string> topKFrequent(vector<string>& words, int k) {
        unordered_map<string,int> hash;
        for(string& s:words) hash[s]++;

        priority_queue<pair<string,int>,vector<pair<string,int>>,cmp> heap;

        for(const pair<string,int>& x:hash){
            heap.push(x);
            if(heap.size()>k) heap.pop();
        }

        vector<string> ret(k);
        for(int i=k-1;i>=0;--i){
            ret[i]=heap.top().first;
            heap.pop();
        }

        return ret;
    }
};

04.數(shù)據(jù)流的中位數(shù)

題目鏈接：https://leetcode.cn/problems/find-median-from-data-stream/

中位數(shù)是有序整數(shù)列表中的中間值。如果列表的大小是偶數(shù)，則沒有中間值，中位數(shù)是兩個(gè)中間值的平均值。

• 例如 arr = [2,3,4] 的中位數(shù)是 3 。
• 例如 arr = [2,3] 的中位數(shù)是 (2 + 3) / 2 = 2.5 。

實(shí)現(xiàn) MedianFinder 類:

• MedianFinder() 初始化 MedianFinder 對(duì)象。
• void addNum(int num) 將數(shù)據(jù)流中的整數(shù) num 添加到數(shù)據(jù)結(jié)構(gòu)中。
• double findMedian() 返回到目前為止所有元素的中位數(shù)。與實(shí)際答案相差 10-5 以內(nèi)的答案將被接受。

示例 1：

輸入
["MedianFinder", "addNum", "addNum", "findMedian", "addNum", "findMedian"]
[[], [1], [2], [], [3], []]
輸出
[null, null, null, 1.5, null, 2.0]

解釋
MedianFinder medianFinder = new MedianFinder();
medianFinder.addNum(1);    // arr = [1]
medianFinder.addNum(2);    // arr = [1, 2]
medianFinder.findMedian(); // 返回 1.5 ((1 + 2) / 2)
medianFinder.addNum(3);    // arr[1, 2, 3]
medianFinder.findMedian(); // return 2.0

提示:

• -105 <= num <= 105
• 在調(diào)用 findMedian 之前，數(shù)據(jù)結(jié)構(gòu)中至少有一個(gè)元素
• 最多 5 * 104 次調(diào)用 addNum 和 findMedian

思路

這里我們最容易想到的暴力解法就是每次插入時(shí)排序，但是這種方法時(shí)間復(fù)雜度太高，其實(shí)這里我們可以使用一個(gè)大堆和一個(gè)小堆來維護(hù)所有數(shù)，各分一半數(shù)據(jù)，若兩邊長度相等，則返回兩個(gè)堆頂相加除2的值，若不等，返回大堆堆頂即可。

在構(gòu)造函數(shù)中初始化兩個(gè)優(yōu)先隊(duì)列，left 用于存放較小的一半元素（最大堆），right 用于存放較大的一半元素（最小堆）。 在 addNum 方法中，根據(jù)元素的大小選擇將其插入到左堆或右堆。插入后需要保持兩個(gè)堆的大小差不超過 1，以確保中位數(shù)的計(jì)算。 在 findMedian 方法中，根據(jù)兩個(gè)堆的大小關(guān)系返回中位數(shù)。通過這種方式，不斷將數(shù)據(jù)插入到兩個(gè)堆中，并保持它們的大小差不超過 1，就能夠在 O(1) 時(shí)間內(nèi)查找到當(dāng)前數(shù)據(jù)流的中位數(shù)。

代碼

class MedianFinder {
    priority_queue<int> left;
    priority_queue<int,vector<int>,greater<int>> right;
public:
    MedianFinder() {}
    
    void addNum(int num) {
        if(left.size()==right.size()){
            if(left.empty()||num<=left.top()) left.push(num);
            else{
                right.push(num);
                left.push(right.top());
                right.pop();
            }
        }
        else{
            if(num<=left.top()){
                left.push(num);
                right.push(left.top());
                left.pop();
            }else right.push(num);
        }
    }
    
    double findMedian() {
        if(left.size()==right.size()) return (left.top()+right.top())/2.0;
        return left.top();
    }
};

/**
 * Your MedianFinder object will be instantiated and called as such:
 * MedianFinder* obj = new MedianFinder();
 * obj->addNum(num);
 * double param_2 = obj->findMedian();
 */

到了這里，關(guān)于算法沉淀——優(yōu)先級(jí)隊(duì)列(堆)（leetcode真題剖析）的文章就介紹完了。如果您還想了解更多內(nèi)容，請(qǐng)?jiān)谟疑辖撬阉鱐OY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章，希望大家以后多多支持TOY模板網(wǎng)！