1. What I learned
a. heapq.heapify(LIST)
It changes a list to heap. It takes nlog(n)
import heapq
nums = [4,2,5,3,1]
heapq.heapify(nums)
b. heapq.nlargest(NUM, HEAP)
It returns a list with largest NUM numbers.
import heapq
nums = [4,2,5,3,1]
new_list = heapq.nlargest(3, nums)
print(new_list)
#it will print [5,4,3]
c. float(‘inf’) and float(‘-inf’)
It represents an infinite float.
2. Code
class KthLargest:
def __init__(self, k: int, nums: List[int]):
#changed nums to the heap with largest k numbers
heapq.heapify(nums)
self.heap = heapq.nlargest(k, nums)
heapq.heapify(self.heap)
self.k = k
def add(self, val: int) -> int:
#if the length of the heap is smaller less than k, push val into the heap
if len(self.heap)<self.k:
heapq.heappush(self.heap, val)
return self.heap[0]
#if val is bigger than the smallest number of the heap, pop the heap and push val into the heap
if val > self.heap[0]:
heapq.heappushpop(self.heap, val)
return self.heap[0]
3. Result
Runtime : 90 ms(69.07%), Memory usage : 19 MB(5.59%)
(Runtime can be different by a system even if it is a same code.)