k번째로 큰 수 구하기 (kth largest number)

정수 배열에서 k번째로 큰 수를 찾는 방법을 알아 보자 (중복된 데이터는 없다고 가정).

1) 주어진 전체 배열을 정렬한 후 data[n-k]가 원하는 값

• 데이터 정렬에 O(nlog(n))의 시간 소요하고 data[n-k] 접근에는 O(1)이 필요하므로, 전체적으로 O(nlog(n))의 시간복잡도를 갖음

2) max heap을 사용

• 데이터 전체를 max-heap으로 구성한 후, max값을 k번 extract한 값이 원하는 값
• max-heap 구성에 O(n), max값 extraction에 O(klog(n))이 필요하므로, 전체적으로 O(n + klog(n))의 시간복잡도를 갖음

3) min heap을 사용

• [0, k-1]구간의 데이터를 min-heap으로 구성. [k, n-1]데이터가 min-heap의 최소값보다 큰 경우 min-heap의 최소값을 제거하고 방금 비교한 데이터를 heap에 넣은 후, min-heap을 구성. 결국 heap의 최소값이 원하는 값
• min-heap 구성에 O(k), 나머지 데이터와의 비교에 O((n-k)log(k))의 시간이 소요되어, 전체적으로 O(k + (n-k)log(k))이 시간복잡도를 갖음

아래 코드는 min heap을 사용하여 k번째 큰 수를 찾는다.

type Comparer func (a, b int) bool

func buildHeap(data []int, size int, compFunc Comparer) {

  for index := (size - 2) / 2; index >= 0; index-- {

    heapify(data, size, index, compFunc)

  }

}

func heapify(data []int, size, index int, compFunc Comparer) {

  left := index*2 + 1

  right := left + 1

  sel := right

  if right < size {

    if compFunc(data[left], data[right]) {

      sel = left

    }

  } else if left < size {

    sel = left

  } else {

    return

  }

  if compFunc(data[sel], data[index]) {

    data[index], data[sel] = data[sel], data[index]

    heapify(data, size, sel, compFunc)

  }

}

func getKthLargestNumber(data []int, kth int) int {
  size := len(data)

  if kth > size {

    panic("can't get an element beyond data range")

  }

  minHeapFunc := func(a, b int) bool {

    return a < b

  }

  buildHeap(data, kth, minHeapFunc)

  for i := kth; i < size; i++ {

    if data[i] > data[0] {

      data[0] = data[i]

      heapify(data, kth, 0, minHeapFunc)

    }

  }

  return data[0]

}