Heap Queue (heapq) in Python | LeetCode Example Last Stone Weight
Heap data structure is mainly used to represent a priority queue. In Python, it is available using the “
heapq” module. The property of this data structure in Python is that each time the smallest heap element is popped(min-heap).
Whenever elements are pushed or popped, heap structure is maintained.
heap element also returns the smallest element each time. Let’s see various Operations on the heap in Python.
Creating a simple heap
heap.heapify(iterable) function is used to convert the iterable into a heap data structure. i.e. in heap order.
In this notebook I’ve showed:
- how heapq affects the original
- how to
def lastStoneWeight(self, stones: List[int]) -> int:
stones = [-item for item in stones]
while len(stones) > 1:
big1 = heapq.heappop(stones)
big2 = heapq.heappop(stones)
int to negative so that we can properly use
popthe largest 2 and crash them then
- till the end
heapqis a binary heap, with O(logn)O(log n)O(logn)
pushand O(logn)O(log n)O(logn)
we know that with our approach we will have O(nlogn)O(nlog n)O(nlogn) Time Complexity and O(1)O(1)O(1) Space Complexity.