Algo_9_Heap

code c++ algo

學習算法

Heap

特色：具有最大堆和最小堆
- 最大堆：跟節點永遠是最大值
- 最小堆：跟節點永遠是最小值

二叉堆

概念：二叉堆是一顆完全二叉樹，樹的每層都會滿，除了最後一層不一定
- i > 1的節點，其父節點i/2
- 如果2i>n那麼i節點沒有孩子，如果2i+1>n那麼節點i沒有右孩子
- 如果i有孩子，那麼左孩子為2i，右孩子為2i+1
操作：
- 進堆：每次把元素放進堆，使跟節點保持最小(最小堆)
- 出堆：每次取出的堆頂，也就是最小值。同時調整堆，使新的堆頂最小

實現

可以直接使用priority_queue，因為是由堆實現的
- priority_queue默認由小排到大，可以使用priority_queue<T,vector<T>,geather<>>來自訂排序
- geather為struct，可以自定義，默認由小到大，以下使用cmp代替原本的geather
```
struct cmp {
      bool operator()(pair<int,int>a,pair<int,int>b){
          return a.second < b.second;
       }
   };
```
也可以使用數組實現

Leetcode 1046

class Solution {
public:
    int lastStoneWeight(vector<int>& stones) {
        priority_queue<int> maxHeap;
        for(int stone : stones){
            maxHeap.push(stone);
        }
        while(maxHeap.size() > 1){
            int x = maxHeap.top();
            maxHeap.pop();
            int y = maxHeap.top();
            maxHeap.pop();
            if(x != y){
                maxHeap.push(x-y);
            }
        }
 
        return maxHeap.size() > 0 ? maxHeap.top() : 0;
    }
};

Leetcode 215

class Solution {
public:
    int findKthLargest(vector<int>& nums, int k) {
        priority_queue<int> pq;
        for(int n : nums) pq.push(n);
        for(int i=0;i<k-1;i++){
            pq.pop();
        }
        return pq.top();
    }
};

Leetcode 347

struct cmp {
        bool operator()(pair<int,int>a,pair<int,int>b){
            return a.second < b.second;
        }
    };
    vector<int> topKFrequent(vector<int>& nums, int k) {
        unordered_map<int,int> mp;
        for(int n : nums ) mp[n]++;
        priority_queue<pair<int,int>,vector<pair<int,int>>,cmp> pq;
        for(auto m : mp) {
            pq.push({m.first,m.second});
        }
        vector<int> ans;
        while(k-- > 0){
            ans.push_back(pq.top().first);
            pq.pop();
        }
        return ans;
    }

第二種解法

vector<int> topKFrequent(vector<int>& nums, int k){
        unordered_map<int,int> mp;
        for(int n : nums ) mp[n]++;
        vector<vector<int>> vc(nums.size()+1);
        for(auto m : mp) {
            vc[m.second].push_back(m.first);
        }
        vector<int> ans;
        for(int i=vc.size()-1;i>=0;i--){
            for(int v : vc[i]){
                ans.push_back(v);
                if(ans.size()==k) return ans;;
            }
        }
        return {};
    }

Leetcode 973

class Solution {
public:
    vector<vector<int>> kClosest(vector<vector<int>>& points, int k) {
        priority_queue<pair<int,vector<int>>> pq;
        for(vector<int> point : points) {
            int x = point[0];
            int y = point[1];
            int dis = x*x + y*y;
            pq.push({dis,point});
            if(pq.size() > k) pq.pop();
        }
        vector<vector<int>> ans;
        while(!pq.empty()){
            pair<int,vector<int>> top = pq.top();
            ans.push_back(top.second);
            pq.pop();
        }
        return ans;
    }
};

Leetcode 23

class Solution {
public:
    ListNode* mergeKLists(vector<ListNode*>& lists) {
        priority_queue<int,vector<int>,greater<int>> pq;
        ListNode* head = new ListNode();
        ListNode* dummy = head;
        for(int i=0;i<lists.size();i++){
            ListNode* l = lists[i];
            while(l != nullptr) {
                pq.push(l->val);
                l = l->next;
            }
        }
        while(!pq.empty()){
            int top = pq.top();
            dummy->next = new ListNode(top);
            dummy = dummy->next;
            pq.pop();
        }
        return head->next;
    }
};