# Leetcode刷題學習筆記 -- Priority_queue
## Introduction
[Learning card](https://leetcode.com/explore/learn/card/heap/)
queue的一種，但是推進去的資料會照大小排序。

// 從大排到小
priority_queue<int> pq;
// 從小排到大
priority_queue<int, vector<int>, greater<int>> pq; 
// 自定義compare function
auto cmp = [](int& a, int& b) {
    return a > b; // 從小排到大和sort的compare相反                   // 因為當cmp成立數值a會往下排列
                  // 所以最小的會在最上面
};
priority_queue<int, vector<int>, decltype(cmp)> pq(cmp);

time complexity如下:
其中N為在container中的element數量。

| | size/empty/top | push/pop |
| -------- | -------- | -------- |
| priority_queue | $O(1)$ | $O(logN)$ |

因為push和pop的效率和N息息相關，所以裡面的數量越少越好。

### 使用vector本身來當heap
因為使用priority_queue必須有額外的空間來儲存，可以使用vector本身來當成queue，則space complexity可以變成$O(1)$。因為vector操作back比較方便，只需要$O(1)$，所以pop_heap和push_heap也是利用back來操作。

[API參考連結](https://hackmd.io/_LIBYTzATYWdOTpEu3dV0Q?view#make_heap)。

vector<int> nums;
make_heap(nums.begin(), nums.end()); // make max-heap
// pop
pop_heap(nums.begin(), nums.end()); // 把top element推到back
nums.pop_back(); // 如果不需要必須把最後一個丟掉
// push
nums.push_back(n); // 把要push進去的element放到最後
push_heap(nums.begin(), nums.end());

使用make_heap的題目:
+ [1962. Remove Stones to Minimize the Total](https://hackmd.io/m_6sQq4DS9u3TXsGYEcUTw?both#1962-Remove-Stones-to-Minimize-the-Total)
## Problems
### [347. Top K Frequent Elements](https://leetcode.com/problems/top-k-frequent-elements/)
列出數列中nums出現頻率最多的k個數字。
把所有的數列都推進去，所以最後取出質料的time complexity為$O(KlogN)$ 因為使用max-heap所以答案就是最上面的k個。

vector<int> topKFrequent(vector<int>& nums, int k) {
    unordered_map<int, int> freq;
    for(auto& n : nums)
        freq[n]++;
    priority_queue<pair<int, int>> pq;
    for(auto it : freq)
        pq.push({it.second, it.first});
    vector<int> rtn;
    for(int i = 0; i < k; ++i) {
        rtn.push_back(pq.top().second);pq.pop();
    }
    return rtn;
}

另外可以使用min-heap，這樣priority_queue裡面只需要保留k個數值。這樣time complexity可以降為$O(NlogK)$。

vector<int> topKFrequent(vector<int>& nums, int k) {
    unordered_map<int, int> freq;
    for(auto& n : nums)
        freq[n]++;
    priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> pq;
    for(auto it : freq) {
        pq.push({it.second, it.first});
        if(pq.size() > k) pq.pop();
    }
    vector<int> rtn;
    while(!pq.empty()) {
        rtn.push_back(pq.top().second); pq.pop();
    }
    return rtn;
}

| | max-heap | min-heap |
| -------- | -------- | -------- |
| 統計出現頻率 |$O(NlogN)$ |$O(NlogN)$ |
| 資料推入 | $O(NlogN)$ | ==$O(NlogK)$== |
| 資料取出 |$O(K)$ |$O(K)$ |

### [253. Meeting Rooms II](https://leetcode.com/problems/meeting-rooms-ii/)
給你一連串的meeting room intervals。試問需要多少的meeting room才可以符合這些intervals。
> 1.只在乎最快結束的meeting room時間，如果連最早結束的時間都比intervals[i][0]還晚，則表示需要另一間meeting room。
>
> 2.如果連最早結束的時間都比intervals[i][0]還早，則pop這個時間，因為這間meeting room已經使用完了。可以排入下一個。

int minMeetingRooms(vector<vector<int>>& intervals) {
    sort(intervals.begin(), intervals.end());
    priority_queue<int, vector<int>, greater<int>> pq;
    // 使用min-heap來看最早結束的meeting root是那一個
    for(auto& it : intervals) {
        // pq.top() <= it[0]，表示會議已經結束，可以使用這間meeting room
        // 把目前的interval排入，等於更新結束時間。pop() then push
        // 不然所有的meeting room都還沒結束，推進pq視為一個新的
        if(!pq.empty() && pq.top() <= it[0]) pq.pop();
        pq.push(it[1]);
    }
    return pq.size();
}

| | sort() | push/pop |
| --------------- | ---------- | --- |
| Time complexity | $O(NlogN)$ | $O(N*2logN)$ |

### [1642. Furthest Building You Can Reach](https://leetcode.com/problems/furthest-building-you-can-reach/)

int furthestBuilding(vector<int>& heights, int bricks, int ladders) {
    auto sz = heights.size();
    // 因為ladders可以爬無限多階，所以留給高度差最大的使用
    priority_queue<int, vector<int>, greater<int>> l;
    int idx = 0;
    for(idx = 0; idx < sz; ++idx) {
        if(idx == sz - 1) break;
        int diff = heights[idx + 1] - heights[idx];
        if(diff <= 0) continue;
        l.push(diff);
        if(l.size() > ladders) {
            bricks -= l.top();
            l.pop();
            if(bricks < 0)  // 因為bricks有變動才需要check
                break;
        }
    }
    return idx;
}

2022/06/21
> 1. 解法和之前一樣用min-heap來儲存最大值，用來使用ladders
> 2. 站在目前的idx往前看，如果bricks >= 0 或是pq.size() < ladders，就繼續往前爬。

int furthestBuilding(vector<int>& heights, int bricks, int ladders) {
    int sz = heights.size();
    if(sz == 1) return 0;
    priority_queue<int, vector<int>, greater<int>> pq;
    int idx = 0;
    for(; idx < sz && bricks >= 0; ++idx) {
        if(idx == sz - 1) break; // 因為沒有idx+1
        int diff = heights[idx + 1] - heights[idx];
        if(diff <= 0) continue;
        pq.push(diff);
        if(pq.size() > ladders) {
            bricks -= pq.top();
            pq.pop();
        }
        if(bricks < 0) break;
    }
    return idx;
}

| | time | space |
| -------- | -------- | -------- |
| complexity | $O(NlogL)$ | $O(L)$ |

其中N為 size of heights，L 為ladders。

### [1337. The K Weakest Rows in a Matrix](https://leetcode.com/problems/the-k-weakest-rows-in-a-matrix/)
> 1.使用自己定義的compare function。
> 2.compare function如果return true，就是把前面的element往下移動。
>

vector<int> kWeakestRows(vector<vector<int>>& mat, int k) {
    auto cmp = [](pair<int, int>& a, pair<int, int>& b) {
        if(a.first > b.first) return true;
        else if(a.first == b.first) return a.second > b.second;
        else return false;
    };
    priority_queue<pair<int, int>, vector<pair<int, int>>, decltype(cmp)> pq(cmp);
    auto nr = mat.size();
    auto nc = mat[0].size();
    for(int i = 0; i < nr; ++i) {
        int j = 0;
        while(j < nc && mat[i][j] == 1) ++j;
        pq.push({j, i});
    }
    vector<int> rtn;
    while(k) {
        rtn.push_back(pq.top().second);
        pq.pop();
        k--;
    }
    return rtn;
}

### [295. Find Median from Data Stream](https://leetcode.com/problems/find-median-from-data-stream/)

class MedianFinder {
    priority_queue<int> low; // top 大
    priority_queue<int, vector<int>, greater<int>> high; // top 小
public:
    MedianFinder() {}
    void addNum(int num) {
        low.push(num);
        high.push(low.top());
        low.pop();
        if(high.size() > low.size()) {
            low.push(high.top());
            high.pop();
        } 
    }
    double findMedian() {
        return low.size() == high.size() ? 
            (low.top() + high.top()) / 2.0 :
            low.top();
    }
};

### [630. Course Schedule III](https://leetcode.com/problems/course-schedule-iii/)
> 1. 如果沒任何限制，當然是全部修
> 2. Greedy，因為題目是求最多的修課數，所以修的課duration越小越有機會修越多。(從小的開始修，刪掉目前修過最大的)
> 3. 使用max-heap來記錄目前修課中最大的duration。
> 4. 如果遇到超過lastday就退選最大的duration，來達到最多的修課數。

int scheduleCourse(vector<vector<int>>& courses) {
    sort(courses.begin(), courses.end(), [&](vector<int>& a, vector<int>& b){
        return a[1] < b[1];    
    });
    priority_queue<int> pq;
    int start = 0;
    for(auto& c : courses) {
        int duration = c[0];
        int lastday = c[1];
        start += duration;
        // 先push進去，這樣取到的duration一定大於或等於目前的值
        pq.push(duration);
        if(start > lastday) {
            start -= pq.top();
            pq.pop();
        }
        // 把最大的減掉就一定會小於等於lastday?
        // 有沒有可能目前的cur >= lastdya?
    }
    return pq.size();
}

### [1775. Equal Sum Arrays With Minimum Number of Operations](https://leetcode.com/problems/equal-sum-arrays-with-minimum-number-of-operations/description/)
給你兩個vector<int>，數值只有1~6，每次操作可以從任意element(1~6)跳到1~6，求最少次操作，可以把兩個vector的sum達到一樣。

> 1. 請先參考 [Greedy的解答](https://hackmd.io/p9hSX0fpSQGwCUL3QF7cLA#1775-Equal-Sum-Arrays-With-Minimum-Number-of-Operations)
> 2. 使用priority_queue，一個用min-heap，一個用max-heap，然後判斷要先取哪一個。

int minOperations(vector<int>& n1, vector<int>& n2) {
    if (n2.size() * 6 < n1.size() || n1.size() * 6 < n2.size())
        return -1;
    int sum1 = accumulate(begin(n1), end(n1), 0), sum2 = accumulate(begin(n2), end(n2), 0);
    if (sum1 > sum2)
        swap(n1, n2);
    // 因為n1的sum比較小使用min-heap，要往上跳
    priority_queue <int, vector<int>, greater<int>> q1(begin(n1), end(n1));
    // 因為n2的sum比較大使用max-heap，要往下跳
    priority_queue<int> q2(begin(n2), end(n2));
    int cnt = 0, diff = abs(sum1 - sum2);
    while (diff > 0) {
        ++cnt;
        // 取q2的條件:
        // 1. q1是empty
        // 2. q2不是empty，且往下跳的幅度(q2.top() - 1)
        //                比往上跳的幅度(6 - q1.top())還大
        if (q1.empty() || (!q2.empty() && q2.top() - 1 > 6 - q1.top())) {
            diff -= q2.top() - 1;
            q2.pop();
        } else {
            diff -= 6 - q1.top();
            q1.pop();
        }
    }
    return cnt;
}

但是這種解法的space complexity為$O(N+M)$，因為需要兩個priority_queue。所以可以使用make_heap來把space complexity變成$O(1)$

int minOperations(vector<int>& n1, vector<int>& n2) {
    if (n2.size() * 6 < n1.size() || n1.size() * 6 < n2.size())
        return -1;
    int sum1 = accumulate(begin(n1), end(n1), 0), sum2 = accumulate(begin(n2), end(n2), 0);
    if (sum1 > sum2)
        swap(n1, n2);
    // min-heap
    make_heap(begin(n1), end(n1), greater<int>());
    // max-heap
    make_heap(begin(n2), end(n2));
    int cnt = 0, diff = abs(sum1 - sum2);
    while (diff > 0) {
        ++cnt;
        if (n1.empty() || (!n2.empty() && n2.front() - 1 > 6 - n1.front())) {
            diff -= n2.front() - 1;
            pop_heap(begin(n2), end(n2)); n2.pop_back();
        } else {
            diff -= 6 - n1.front();
            pop_heap(begin(n1), end(n1), greater<int>()); n1.pop_back();            
        }
    }
    return cnt;
}

### [1962. Remove Stones to Minimize the Total](https://leetcode.com/problems/remove-stones-to-minimize-the-total/description/)
給你vector<int> piles，每次操作可以選一個pile然後減少floor(piles[i] / 2)的石頭，最多可以操作K次，試問最少剩下多少石頭。

> 1. Greedy點，每次操作都選最大堆，這樣可以減掉最多石頭。
> 2. 選最大堆--> priority_queue

int minStoneSum(vector<int>& piles, int k) {
    make_heap(piles.begin(), piles.end());
    while(k--) {
        piles.front() -= piles.front() / 2;
        pop_heap(piles.begin(), piles.end()); // move the top to back
        push_heap(piles.begin(), piles.end()); // push the back element to pq
    }

    return accumulate(piles.begin(), piles.end(), 0);
}

### [358. Rearrange String k Distance Apart](https://leetcode.com/problems/rearrange-string-k-distance-apart)
給你一個string s，重新排列讓新的string每個char只少都有k個distance。

> 1. 使用priority_queue來拿最多的char(Greedy)。
> 2. 使用queue來讓使用過的char排隊，當排了k次，就又可以回到priority_queue。
> 3. ==把count == 0 也往queue裡面塞，這樣可以把剩下的全部擠出queue。==
> 4. 從queue拿出來的資料中，count==0表示queue內的資料已經全部取完。

class Solution {
public:
    string rearrangeString(string s, int k) {
        using pii = pair<int, int>; //count, char
        int cnt[26] = {0};
        priority_queue<pii> pq;
        queue<pii> q;              // wait here for k time
        for (auto ch : s) cnt[ch - 'a']++;
        for (auto i = 0; i < 26; ++i)
            if (cnt[i] != 0) pq.push({cnt[i], i});
        string res = "";
        while (!pq.empty()) {
            auto p = pq.top(); pq.pop();
            res += 'a' + p.second;
            q.push({p.first - 1, p.second}); /* 把count = 0 繼續往裡面塞，把剩下的都擠出來 */
            // 使用 >= 使因為 當k == 0，
            // 就需要使用大於的情況。
            if (q.size() >= k) { 
                auto p = q.front(); q.pop();
                // 如果再次遇到count==0，表示queue都清光了
                if (p.first) // count != 0
                    pq.push({p.first, p.second});
            }
        }
        return res.size() == s.size() ? res : "";
    }
};

### [2542. Maximum Subsequence Score](https://leetcode.com/problems/maximum-subsequence-score/)
給你兩個vector<int> nums1和nums2。任取k個組合，使得score最大。score定義，
$sum(num1[i0] + nums1[i1] + ... + nums1[ik-1]) * min(num2[i0] + nums2[i1] + ... + nums2[ik-1])$
> 1. 2023/05/24，一開始我也是不知所措了一陣子。
> 2. 因為是取min(nums2[])，所以想到了用nums2來排序，這樣每次的min都會固定。
> 3. 當取的數字大於k，就需要踢掉一個，Greedy的想法當然是踢掉最小的那個，所以使用minheap。

class Solution {
public:
    long long maxScore(vector<int>& nums1, vector<int>& nums2, int k) {
        vector<vector<int>> v;
        int sz = nums1.size();
        for(int i = 0; i < sz; ++i) // O(N)
            v.push_back({nums2[i], nums1[i]});
        sort(v.begin(), v.end(), [](vector<int>& a, vector<int>& b){ // O(NlogN)
            return a[0] > b[0];
        });
        priority_queue<int, vector<int>, greater<int>> pq; // minheap
        long long sum{}, min, ans{};
        for(int i = 0; i < sz; ++i) { // O(NlogK)
            sum += v[i][1];
            min = v[i][0];
            pq.push(v[i][1]);
            if(pq.size() > k) {
                sum -= pq.top();
                pq.pop();
            }
            if(i >= k - 1) ans = max(ans, (long long)sum * min);
        }
        // time complexity  : O(N + NlogN + NlogK) = O(NlogN)
        // space complexity : O(N + K) 
        return ans;
    }
};
/*
{2, 1}{1, 3}{3, 3}{4, 2} -> sort by nums2
{4, 2}{3, 3}{2, 1}{1, 3}
                    * 取到這個的時候，因為要納入3，
                      所以踢掉最小的1

*/

###### tags: `leetcode` `刷題`