C++/Java/Python 6 Line Approach, Question Clarifications & Heap Cheatsheet
If you are already familiar with priority_queue in C++ skip to the Approach section at the end\n### C++ Heap Guide/Cheatsheet\nIn C++ priority_queue is the impl
If you are already familiar with priority_queue in C++ skip to the Approach section at the end\n### C++ Heap Guide/Cheatsheet\nIn C++ [priority_queue](https://www.cplusplus.com/reference/queue/priority_queue/) is the implementation for heaps. If you have never used priority_queue before, you can get started by reading this cheatsheet and solving this problem. However, you still should read about [heaps](https://ocw.mit.edu/courses/6-006-introduction-to-algorithms-fall-2011/resources/lecture-4-heaps-and-heap-sort/) and how they work so that you know when and where to use them.\n\n1. **Introduction**\n* Why heaps?\nHeap as a container gives you fast insertion of any element as well as reads and deletion of either the minimum-most or maximum-most element. Also it does not provide random access to any other element in the heap\n* Where to use?\nBased on this advantage, some major use cases for heaps are BFS, Djikstra, Current median of stream of elements\n\n2. **Initialising**\n\t```cpp\n\t// 1. max heap -> for popping largest element\n\t\tpriority_queue<int> pq;     // replace int with any other type or a struct based on need\n\t// 2. min heap -> for popping minimum element\n\t\tpriority_queue<int, vector<int>, greater<int>> pq;\n\t// 3. custom heaps in case of custom ordering (here we are creating min heap based on second property)\n\t\tstruct comp {\n\t\t\tbool operator()(pair<int, int> a, pair<int, int> b) {\n\t\t\t\treturn a.second > b.second;\n\t\t\t}\n\t\t};\n\t\tpriority_queue<int, vector<int>, comp> pq;\n\t// 4. If you already have an array and want to initialise using it\n\t\tpriority_queue<int, vector<int>, greater<int>> pq(a.begin(), a.end());\n\t```\n\tThis last operation takes O(n) time where n is size of array a.\n\n3. **Important operations**\n\t```cpp\n\tpq.push(10);           // adds element to heap\n\tint cur = pq.top();    // returns top element, does NOT pop though\n\tpq.pop()               // pops top element, does NOT return the value of top element though\n\tpq.size()              // return size of heap\n\tpq.empty()             // returns true if heap is empty else false\n\t```\n - Always make sure that heap is not empty prior to top() and pop() methods\n - *Time* - push() and pop() takes O(logn) time, the other three require O(1) time.\n___\n</br>\n\n### Question Clarifications\nSome people have misinterpreted the question a bit, for example [here](https://leetcode.com/problems/last-stone-weight/discuss/1922217)\nNote, the question states that you always have to pick the two largest stones and then find the minimum-most stone. Its however not necessary that if you had the freedom to pick any two stones, that picking the largest would give you smallest stone at the end. It actually wont, consider the following example -\n> [25, 23, 16, 16, 16]\n\n* If you picked the largest two every time you would end up with 14.\n* However with freedom to pick any stone you can end with 0. By picking following stones at each step -\n\t```text\n\t(25, 16) -> (23, 16) -> (16, 9)  -> (7, 7)\n\tleaves 9 -> leaves 7 -> leaves 7 -> leaves 0\n\t```\n\nAnother clarification, is the question states find the minimum most possible stone after only one stone remains. Since there can be only one pair of largest stones possible at each step and you do not have the element of choice, you can only have one way of smashing the stones and hence only one possibility of last stone remaining, which being the only candidate for being the minimum-most will also be the answer.\n___\n</br>\n\n### Approach\nOnce we are aware of how to use the priority queue and the above facts the approach is straightforward as the question instructs us what to do. We need the two largest elements at each step for our operation, since heaps give the fastest access to the extremes its our go to here. The pseudo-code is as follows -\n```text\n\tInitialise heap using the array (use 4th option above)\n\tKeep smashing as long as there is 2 or more stones (use size() method)\n\t\tPick the two largest and remove them from heap (use top() and pop())\n\t\tif their difference is positive add new stone to our heap (use push())\n\t\n\tIf there is a stone remaining in heap return it or else return 0 (use empty() and top())\n```\n\nC++/Java/Python code based on above pseudo code\n\n<iframe src="https://leetcode.com/playground/kocCUYy5/shared" frameBorder="0" width="800" height="370"></iframe>\n\nComplexity - Time: O(nlogn), Space: O(n)\n\nWould also like to add the common heap operations and code for Java and Python along with complexity to this cheatsheet, please mention them if you are familiar with them.\n
['C', 'Heap (Priority Queue)', 'Python', 'Java']