map代碼練習1，對應力扣 兩個數據的交集，代碼見下

class Solution {
public:vector<int> intersect(vector<int>& nums1, vector<int>& nums2) {map<int, int> cnt;vector<int> ans;for(int i=0; i<nums1.size(); ++i){int x = nums1[i];cnt[x]++;}for(int i=0; i<nums2.size(); ++i){int x = nums2[i];if(cnt[x] > 0){cnt[x]--;ans.push_back(x);}}return ans;}
};

代碼2，對應力扣，合并相似的物品

class Solution {
public:vector<vector<int>> mergeSimilarItems(vector<vector<int>>& items1, vector<vector<int>>& items2) {map<int, int> mp;for(int i=0; i<items1.size(); ++i){int val = items1[i][0];int weh = items1[i][1];mp[val] += weh; }for(int i=0; i<items2.size(); ++i){int val = items2[i][0];int weh = items2[i][1];mp[val] += weh; }vector<vector<int>> ans;for(map<int, int>::iterator it = mp.begin(); it != mp.end(); it++){int val = it->first;int weh = it->second;ans.push_back({val, weh});}return ans;}
};

priority_queue 優先級隊列

parent(id) = (id - 1)/2

left(id) = id*2 + 1;

right(id) = id*2 + 2;

堆概念：滿足比他的所有子節點大或者小

大頂堆：滿足堆的概念（比所有子節點大），并且他的子節點也滿足堆的概念（比所有子節點大）

小頂堆：滿足堆的概念（比所有子節點小），并且他的子節點呀滿足堆的概念（比所有子節點小）

大頂堆的增刪查：

1，元素插入：往數組尾部插入一個元素、對插入的元素，比較他（在樹形結構中）和他父節點的大小關系，來決定是否和父節點進行交換。這個就是優先隊列的入隊操作。

2，獲取棧頂：獲取數組的第0個元素

3，元素刪除：把數組的第0個元素和最后有一個元素交換、然后對棧頂的元素不斷做“下沉”操作，選擇大的進行交換，直到“自己”成為最大的、刪除數組的最后一個元素。

容器特點：

線性容器：vector string list

樹形容器：set multiset map multimap

線性模擬樹：priority_queue

priority_queue對象創建，代碼見下

#include<iostream>
#include<queue>using namespace std;int main() {// 最大優先隊列priority_queue<int> q1;// 最小優先隊列priority_queue<int, vector<int>, greater<int>> q2;return 0;
}

priority_queue 數據插入

插入有一個特點，便是插入后的隊列的第零個元素都是當前元素中最大的那個元素（這個隊列是最大優先隊列）。最小優先隊列的話恰恰相反

代碼見下：

#include<iostream>
#include<queue>using namespace std;int main() {// 最大優先隊列priority_queue<int> q1;q1.push(6);q1.push(2);q1.push(1);q1.push(8); q1.push(16);q1.push(26);q1.push(9);// 最小優先隊列priority_queue<int, vector<int>, greater<int>> q2;q2.push(6);q2.push(2);q2.push(1);q2.push(8);q2.push(16);q2.push(26);q2.push(9);return 0;
}

具體調試過程可見下，用于幫助理解：

priority_queue獲取棧頂

#include<iostream>
#include<queue>using namespace std;int main() {// 最大優先隊列priority_queue<int> q1;q1.push(6); cout << q1.top() << endl;q1.push(2); cout << q1.top() << endl;q1.push(1); cout << q1.top() << endl;q1.push(8); cout << q1.top() << endl;q1.push(16); cout << q1.top() << endl;q1.push(26); cout << q1.top() << endl;q1.push(9); cout << q1.top() << endl;cout << "-----------------------------";// 最小優先隊列priority_queue<int, vector<int>, greater<int>> q2;q2.push(6); cout << q2.top() << endl;q2.push(2); cout << q2.top() << endl;q2.push(1); cout << q2.top() << endl;q2.push(8); cout << q2.top() << endl;q2.push(16); cout << q2.top() << endl;q2.push(26); cout << q2.top() << endl;q2.push(9); cout << q2.top() << endl;return 0;
}

這里的top其實便是front，見以下截圖

priority_queue 出隊操作，代碼見下

#include<iostream>
#include<queue>using namespace std;int main() {// 最大優先隊列priority_queue<int> q;q.push(6); q.push(2); q.push(1); q.push(8); q.push(16); q.push(26); q.push(9);for (int i = 0; i < 7; ++i) {cout << "top()" << q.top() << endl;q.pop();}return 0;
}

priority_queue 大小操作，代碼見下

#include<iostream>
#include<queue>using namespace std;int main() {// 最大優先隊列priority_queue<int> q;q.push(6); q.push(2); q.push(1); q.push(8); q.push(16); q.push(26); q.push(9);while (!q.empty()) {cout << "top()" << q.top() << "size()" << q.size() << endl;q.pop();}return 0;
}

priority_queue 自定義結構，代碼見下

#include<iostream>
#include<queue>using namespace std;struct type {int key;int value;type() { key = value = 0; };type(int k, int v) :key(k), value(v){};bool operator<(const type& t) const { // 這里的第二個const是確保成員函數不被修改return key < t.key;}
};
int main() {priority_queue<type> q;q.push(type(6, 1));q.push(type(5, 2));q.push(type(4, 2));q.push(type(8, 3));q.push(type(9, 2));while (!q.empty()) {cout << "top() = " << q.top().key << ", size()=" << q.size() << endl;q.pop();}return 0;
}

代碼練習一，對應力扣，丑數 || 代碼見下

class Solution {#define ll long long
public:int nthUglyNumber(int n) {priority_queue<ll, vector<ll>, greater<ll>> q;q.push(1);ll pre = -1;while(1){ll val = q.top();q.pop();while(val == pre){val = q.top();q.pop();}pre = val;--n;if(n==0){return val;}q.push(val * 2);q.push(val * 3);q.push(val * 5);}return -1;}
};

代碼練習 2 對應力扣 矩陣中的和，代碼見下

class Solution {
public:int matrixSum(vector<vector<int>>& nums) {int n = nums.size();int m = nums[0].size();priority_queue<int> q[300];for(int i=0; i<n; ++i){for(int j=0; j<m; ++j){q[i].push(nums[i][j]);}}int sum = 0;while(m--){int ret = 1;for(int i=0; i<n; ++i){ret = max(ret, q[i].top());q[i].pop();}sum += ret;}return sum;}
};