힙을 사용한 예제(배열의 k번째 큰 요소)

https://leetcode.com/problems/kth-largest-element-in-an-array/submissions/

Kth Largest Element in an Array - LeetCode

 

 

 1. heapq 모듈 이용

class Solution:
    def findKthLargest(self, nums: List[int], k: int) -> int:
        heap=list()
        for n in nums:
            heapq.heappush(heap,-n)
            
        for _ in range(k-1):
            heapq.heappop(heap)
            
        return -heapq.heappop(heap)

 

 2. heapq 모듈의 heapify 이용

 heapify()란 주어진 자료구조가 힙 특성을 만족하도록 바꿔주는 연산이다. 물론 하나라도 값을 추가하면 다시 힙 특성이 깨지지만, 추가가 게속 일어나는 형태가 아니기 때문에 heapify()는 한 번만 해도 충분하다.

class Solution:
    def findKthLargest(self, nums: List[int], k: int) -> int:
        heapq.heapify(nums)
        
        for _ in range(len(nums)-k):
            heapq.heappop(nums)
            
        return heapq.heappop(nums)

 

 3. heapq 모듈의 nlargest 이용

class Solution:
    def findKthLargest(self, nums: List[int], k: int) -> int:
        return heapq.nlargest(k,nums)[-1]

 k번째만큼 큰 값이 가장 큰 값부터 순서대로 리스트로 리턴된다. 힙이 아니라도 내부적으로 heapify() 함수도 호출해 처리해주기 때문에, 별도로 힙 처리를 할 필요가 없어 편리하다. 참고로 nsmallest()를 사용하면 동일한 방식으로 n번째 작은 값도 추출이 가능하다.

 

 4. 정렬을 이용한 풀이

class Solution:
    def findKthLargest(self, nums: List[int], k: int) -> int:
        return sorted(nums,reverse=True)[k-1]