힙을 사용해 K번째로 큰 수 구하기

<출처: http://goprogrampractice.blogspot.com/2017/01/k-kth-largest-number.html>

 

힙을 사용해서 N개의 정렬되지 않은 데이터에 대해 K번째로 큰 숫자를 구하는 방법을 정리해보겠습니다.

 

1. MinHeap 사용

1ST. 최초 K개의 숫자에 대해 MinHeap을 구성합니다. (arr[0] ~ arr[k-1])

 

2ND. 나머지 (N-1) - K개의 데이터값을 MinHeap의 루트와 비교하며 힙을 갱신합니다. (arr[k] ~ arr[n-1])

2-1. 현재 데이터가 힙의 루트보다 큰 경우 → 힙 루트값 삭제, 현재 데이터 힙에 추가, 다시 MinHeap 만들기  

2-2. 현재 데이터가 힙의 루트보다 작은 경우 → 무시

 

이렇게 N개의 데이터가 MinHeap의 루트와 비교가 끝나면, 힙의 루트값이 K번째로 큰 수가 됩니다.

 

그림을 통해 살펴보겠습니다.

---

---

---

---

시간복잡도는

1. K개의 원소로 MinHeap을 구성하는데 O(K)

2. N-K개의 원소와 MinHeap의 비교연산이 이뤄지는 과정이 O( (n-k)logk ) 입니다.

그러므로 시간복잡도는 O(k + (n-k)logk)가 됩니다.

 

---

2. MaxHeap 사용

K번째로 큰 숫자를 구하는 것이기 때문에 MaxHeap의 경우 좀 더 간단합니다. 

 

1ST. N개의 데이터에 대해 MaxHeap을 구성합니다.

2ND. MaxHeap에서 K-1번만큼 EXTRACT 해주면, root가 K번째로 큰 원소입니다.

 

이에 대한 시간복잡도는

1. MaxHeap을 구성하는데 O(N)

2. MaxHeap의 Heapify연산에 들어가는 시간복잡도 O(klogN)

그러므로 시간복잡도는 O (N + klogN) 입니다.

 

---

Heap을 사용해 k번째로 큰 숫자를 찾는 방법은 N개의 데이터가 주어졌을 때

단순히 정렬 알고리즘을 사용하여 정렬 후 a[k-1]번째 값을 k번째로 큰 값으로 리턴하는

O(NlogN) 방법보다 더 우수한 시간복잡도를 가지므로 알아둘만한 방법인 거 같습니다.