Heap Queue (heapq) in Python | LeetCode Example Last Stone Weight
Easy read on: Heap Queue (heapq) in Python | LeetCode Example Last Stone Weight — Hung, Chien-Hsiang 洪健翔 | Blog (chienhsiang-hung.github.io)
Heap
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.
The heap[0]
element also returns the smallest element each time. Let’s see various Operations on the heap in Python.
Creating a simple heap
The 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
list
- how to
push
andpop
push
andpop
simultaneously withheapq.heappushpop(list, item)
andheapq.heapreplace(list, item)
nlargest(n, list)
andnsmallest(n, list)
Example
import heapq
class Solution:
def lastStoneWeight(self, stones: List[int]) -> int:
stones = [-item for item in stones]
heapq.heapify(stones)
while len(stones) > 1:
big1 = heapq.heappop(stones)
big2 = heapq.heappop(stones)
heapq.heappush(stones, big1-big2)
return -stones[0]
Approach
Turn all int
to negative so that we can properly use Heap
.
pop
the largest 2 and crash them thenpush
them back- till the end
With
heapq
is a binary heap, with O(logn)O(log n)O(logn)push
and O(logn)O(log n)O(logn)pop
.1
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.