Notes

tags: Binary Tree,Tree A complete binary tree is a binary tree in which every level, except possibly the last, is completely filled, and all nodes in the last level are as far left as possible.

tags: Heap (data structure),Data Structures,Complete Binary Tree,Tree source: https://en.wikipedia.org/wiki/Binary%5Fheap Binary tree with two additional constraints: Shape property: complete binary tree. Heap property: the key stored in each node is greater or equal(max-heaps) to or less than or equal to(min-heaps) the keys in the node’s children, according to some total order. Heap operations Insert Steps to add an element to a heap: Add element to the bottom level of the heap at the leftmost open space. Compare to its parent, if they are in the correct the order, stop. If not, swap element with its parent and return to the previous step. Extract: Delete the root from heap Replace the root of heap with the last element on the bottom level. Compare the new root with its children; if they are in the correct order, stop. If not, swap the element with one of its children and return to the previous step. Search Delete Decrease or increase key Heap implementation with array each element a at index i has ...

tags: Priority Queue,LeetCode101 Max heap priority queue class Solution { public: int findKthLargest(vector<int>& nums, int k) { // max heap priority_queue<int> pq; for (auto iter = nums.begin(); iter != nums.end(); ++iter) { pq.push(*iter); } // The Kth largest element should let k > 1 not k > 0 for (; k > 1; --k) { pq.pop(); } return pq.top(); } };

tags: Priority Queue,LeetCode101 The key ideas: Use a std::pair to hold {count, index}, so it can compare count first then the index. Use a min heap priority queue to get the K weakest rows. class Solution { public: vector<int> kWeakestRows(vector<vector<int>>& mat, int k) { // min heap priority_queue< std::pair<int, int>, vector<std::pair<int, int> >, std::greater<std::pair<int, int> > > pq; for (auto iter = mat.begin(); iter != mat.end(); ++iter) { int c = count((*iter).begin(), (*iter).end(), 1); pq.push({c, iter - mat.begin()}); } vector<int> ret; for (; k > 0; --k) { ret.push_back(pq.top().second); pq.pop(); } return ret; } };

tags: Data Structures,Heap (data structure) The priority queue is solved: The K smallest/largest/weakest X.