코딩테스트 힙

힙(Heap)은 이진 트리 기반의 데이터 구조로, 우선순위 큐(Priority Queue)를 구현할 때 주로 사용됩니다.

1. 힙의 기본 개념

최소 힙(Min-Heap): 부모 노드의 값이 자식 노드의 값보다 항상 작거나 같다.
최대 힙(Max-Heap): 부모 노드의 값이 자식 노드의 값보다 항상 크거나 같다.

최소 힙 구현 코드

class MinHeap {
  constructor() {
    this.heap = []
  }

  // 부모 노드의 인덱스
  getParentIndex(childIndex) {
    return Math.floor((childIndex - 1) / 2)
  }

  // 왼쪽 자식 노드의 인덱스
  getLeftChildIndex(parentIndex) {
    return parentIndex * 2 + 1
  }

  // 오른쪽 자식 노드의 인덱스
  getRightChildIndex(parentIndex) {
    return parentIndex * 2 + 2
  }

  // 값 교환
  swap(index1, index2) {
    ;[this.heap[index1], this.heap[index2]] = [this.heap[index2], this.heap[index1]]
  }

  // 힙에 값 추가
  insert(value) {
    this.heap.push(value)
    this.heapifyUp()
  }

  // 위로 힙 정렬
  heapifyUp() {
    let index = this.heap.length - 1
    while (index > 0) {
      const parentIndex = this.getParentIndex(index)
      if (this.heap[parentIndex] <= this.heap[index]) break
      this.swap(index, parentIndex)
      index = parentIndex
    }
  }

  // 힙에서 최소값 제거
  remove() {
    if (this.heap.length === 0) return null
    if (this.heap.length === 1) return this.heap.pop()

    const root = this.heap[0]
    this.heap[0] = this.heap.pop()
    this.heapifyDown()
    return root
  }

  // 아래로 힙 정렬
  heapifyDown() {
    let index = 0
    const length = this.heap.length

    while (this.getLeftChildIndex(index) < length) {
      let smallerChildIndex = this.getLeftChildIndex(index)
      const rightChildIndex = this.getRightChildIndex(index)

      if (rightChildIndex < length && this.heap[rightChildIndex] < this.heap[smallerChildIndex]) {
        smallerChildIndex = rightChildIndex
      }

      if (this.heap[index] <= this.heap[smallerChildIndex]) break
      this.swap(index, smallerChildIndex)
      index = smallerChildIndex
    }
  }

  // 힙의 최소값 반환
  peek() {
    return this.heap.length > 0 ? this.heap[0] : null
  }
}

2. 코딩 테스트 예제 문제

문제: 배열의 K번째 최소값 찾기

설명: 주어진 배열에서 K번째로 작은 수를 찾으세요.

입력

배열: [7, 10, 4, 3, 20, 15]
K = 3

출력

풀이 코드

function findKthSmallest(arr, k) {
  const minHeap = new MinHeap()

  // 배열의 모든 요소를 힙에 추가
  arr.forEach((num) => minHeap.insert(num))

  // k번째 최소값 추출
  let result
  for (let i = 0; i < k; i++) {
    result = minHeap.remove()
  }

  return result
}

// 테스트
const arr = [7, 10, 4, 3, 20, 15]
const k = 3
console.log(findKthSmallest(arr, k)) // 7

3. 설명

MinHeap 클래스를 사용해 배열의 모든 값을 최소 힙에 추가합니다.
힙에서 k번 값을 제거하면, 그 값이 배열의 k번째로 작은 값이 됩니다.
시간 복잡도:
- 힙 삽입: O(log N)
- 힙 제거: O(log N)
- 전체: O(N log N) (N은 배열 길이)

힙