I wrote it down because I learned how to sort using a library called heapq in python.
The heap queue is mainly used for sorting (heapsort).
For execution time, In the case of bubble sort that compares the magnitude of all values, $ O (N ^ 2) $. On the other hand, in the case of heapsort, $ O (NlogN) $.
Problem link: https://leetcode.com/problems/kth-largest-element-in-a-stream/discuss/482591/Simple-Python-Solution-or-Maintain-Min-Heap-whose-size-is-always-kept-at-k
import heapq
class KthLargest:
def __init__(self, k: int, nums: List[int]):
self.heap = []
self.k = k
for num in nums:
self.add(num)
def add(self, val: int) -> int:
heapq.heappush(self.heap, val)
if len(self.heap) > self.k:
heapq.heappop(self.heap)
return self.heap[0]
Recommended Posts