[leetcode] Kth Largest Element in an Array (w/o sorting) -> heap

• 1 5
• -104 4

---

Python의 heapq 모듈은 기본적으로 min-heap을 구현합니다. 즉, heap[0]은 항상 힙에서 가장 작은 값입니다.

핵심 아이디어:

1. 힙의 크기를 k개로 제한
2. 힙에는 항상 가장 큰 k개의 원소만 유지
3. min-heap이므로 heap[0]은 이 k개 중에서 가장 작은 값

따라서 heap[0]이 바로 k번째로 큰 값

class Solution:
    def findKthLargest(self, nums: List[int], k: int) -> int:
        heap = []

        for num in nums:
            heapq.heappush(heap, num)
            if len(heap) > k:
                heapq.heappop(heap)

        return heap[0]

#leetcode, #heap, #min_heap