[Python] Heap Explained with Easy Code
Naive Approach\nThe naive approach to solve the question, would be:\n\n1. Sort the array in decreasing order\n2. Pop the first two elements, subtract them.\n3. 
# Naive Approach\nThe naive approach to solve the question, would be:\n\n1. Sort the array in decreasing order\n2. Pop the first two elements, subtract them.\n3. If the difference is 0, then do nothing. Else, append the difference in the array\n4. Repeat the step 1, 2 and 3 until there is only one item left in the array\n5. The only item left in the array is the answer\n\nHowever, the time complexity would be high because sorting is performed (N-1) times. The time complexity would be O(N<sup>2</sup>).\n\n---\n\n\n# Optimal Approach\nThe optimal approach uses a very important Data Structure, Heap. Heap is a Complete Binary Tree.\nFirst, let\'s understand what is a <b>Complete Binary Tree</b>. \n*[Skip if you know that already]*\n\n### Complete Binary Tree\n1. <b>Definition 1</b>\nA complete binary tree is a binary tree where all the levels, except the last level must be completely filled. The last level may or may not be filled completely. The last level MUST be filled from left to right.\n2. <b>Definition 2</b>\nA Complete Binary Tree is a Tree, where every level in the tree is required to be filled with maximum nodes, except the last level. The last level may not be completely filled but all the nodes in the last level must be towards the left of the tree.\n\n## Heap\nHeap Data Strucutre, is a Complete Binary Tree, which satisfies the <b>Heap Property</b>. We are going to discuss the heap properties in a moment. There are two types of Heaps: <b>MaxHeap</b> and <b>MinHeap</b>.\n\n## MaxHeap\nProperty for a MaxHeap is "<b>The value of every node is less than or equal to its parent</b>". Therefore, in a MaxHeap, the maximum value resides as the root node. Here is a valid MaxHeap:\n<table width = "100%">\n<tr>\n<td><img src = "https://assets.leetcode.com/users/images/22cb76cb-8d54-4e4a-8947-d500f0c7c0f3_1669561918.8131528.png" style ="text-align: center; margin: 0; width: 100%;" /></td>\n</tr>\n<tr>\n<td>This is a valid MaxHeap Tree because:\n<ol>\n<li>It is a complete binary tree. Every level is completely filled except the last level which is completely left aligned.</li>\n<li>Every Node is less than or equal to its parent node.</li>\n</ol>\n</td>\n</tr>\n</table>\n\n## MinHeap\nMinHeap is just opposite of MaxHeap. The Heap Property for a MinHeap is "<b>The value of every node is greater than or equal to its parent</b>". Therefore, in a MinHeap, the minimum value resides as the root node.\n\n---\n\n# Why Heap?\n\nAs you just saw, in a MaxHeap, the maximum element is guaranteed to be on the top of the tree, or in a MinHeap, the minimum element is guaranteed to be on the top of the tree. In an sorted array, each time, we inserted, removed or updated an element in the array, the whole array needs to be sorted again to keep the array in order. It was a very time costly operation. In heaps, we can remove, insert or update an element in the heap in `log N`.\n\n### How is it so fast?\nThis high performace is achieved because a Heap Tree can be written in an array (list) in such a way that, the traversals are easy as compared to that in a normal array. \nFor example, let\'s write the above mentioned MaxHeap in the array.:\n<table>\n<tr>\n<td>100</td>\n<td>17</td>\n<td>39</td>\n<td>15</td>\n<td>13</td>\n<td>36</td>\n<td>25</td>\n<td>14</td>\n<td>9</td>\n</tr>\n</table>\n\nLet the indices be 1, 2, 3, 4... and so on. If, I ask you to look at the array and tell me the parent of 36 in the Heap, how would you do it?\nWell, there\'s a simple trick. Get the index of 36, which is 6. Floored Division of the index by 2 would give the index of its parent. Hence, its parent is at index 3, i.e. 39. You can try that for other elements as well.... You can also do the opposite, i.e. multiply and index by 2 to get the index of left child, and add 1 to it to get the index of right child.\nThis holds true, as long as the tree is a Complete Binary Tree.\n\nNow, how things work is... say you want to insert an element 19 in the array (or heap). The algorithm goes like:\n1. Add 19 to the next available position in the heap, i.e. 19 would be added as the left child of 13 (Consider the tree diagram above). \n**Important:** Note that, in the array notation of the heap, the element would be added to the last of the array. Actually, there is no data structure like Complete Binary Tree getting involved here, it\'s just for visualisation. All the operations we do are on the array.\n2. Find the parent of 19 and compare both the numbers. Here, the parent is 13 and 13 < 19. Since, it is a Max Heap, larger number remains on top. So, we swap 13 with 19.\n3. Now, again we find the parent of 19, which would be 17 this time. Again, 17 < 19. So, 17 and 19 are swapped.\n4. Again the parent of 19 is 100, but 100 > 19, so no more swapping is done, and we have our element inserted.\n\nSimilarily there are deletion operations, which can also be performed in `log N` time. But, we are not going deeper into this.\n\n---\n\n# Heap in Python\nPython provides an inbuilt module for dealing with heap data structure, namely \'heapq\'. It has various functions which are going to help us throughout the program. Thus, we need to import it to use it. The library can be used to create MinHeap. But, we can use the properties of MaxHeap if we multiply every value in the MinHeap with -1. Then, the negative value of every node acts as a MaxHeap.\nLet\'s code:\n\n```\nclass Solution:\n    def lastStoneWeight(self, stones: List[int]) -> int:\n        \n\t\t#    First, import the heapq module. Specifically the functions heapify, heappop and heappush\n        from heapq import heapify, heappop, heappush\n        \n\t\t#    Initialize an empty array, which we would use as heap\n        heap = []\n        for stone in stones:\n\t\t\n\t\t#    We would add the negative values of the given list in the Heap\n            heap.append(-stone)\n        \n\t\t#    heapify function from the heapq module, takes an array as parameter, arranges the contents\n\t\t#    of the array in such a way that the array becomes a minheap\n        heapify(heap)\n        \n        while len(heap) > 1:\n\t\t\n\t\t#    heappop function from the heapq module, takes an array (heap) as parameter, and removes\n\t\t#    the root of the minheap, returns the value, and then makes the necessary arrangement so\n\t\t#    that the heap does not lose its properties.\n            x = heappop(heap)\n            y = heappop(heap)\n            \n\t\t#    if the two minimum values from the heap are not equal, then subtract the larger value (smaller\n\t\t#    magnitude) from the smaller value (larger magnitude). Add the difference back to the heap\n            if x != y:\n\t\t\t\n\t\t#    heappush function, from the heapq module, takes an array (heap) as parameter, and adds\n\t\t#    the second parameter to the array, maintaining the heap properties of the array.\n                heappush(heap, x - y)\n        \n\t\t#    if heap is not empty then, return the first item in the heap multiplied by -1\n        if heap:\n            return -heap[0]\n\t\t\t\n\t\t#    if heap was empty, then return 0\n        return 0\n```\n\nIt took sweats to create this post. Please upvote, if you found it helpful. Happy Leetcoding!
['Heap (Priority Queue)', 'Python', 'Python3']