[알고리즘] heap 자료구조

Heap 자료구조란 무엇인가

• Heap(힙)은 완전 이진 트리 형태로 구성되며, 각 노드가 특정 규칙(우선순위)에 따라 정렬되어 있는 자료구조이다.
• 힙에서는 부모 노드와 자식 노드의 관계가 명확하다.
• Heap 자료구조의 주요 목적은 최댓값/최솟값을 빠르게 찾기 위함으로, 우선순위 큐를 구현할 때 자주 사용된다.

Heap의 종류

• 최대 힙(Max Heap)

  • 부모 노드의 값이 자식 노드의 값보다 크거나 같다. 항상 최댓값이 루트에 위치.

• 최소 힙(Min Heap)

  • 부모 노드의 값이 자식 노드의 값보다 작거나 같다. 항상 최솟값이 루트에 위치.

Heap의 특징

• 삽입, 삭제가 각각 O(logN)의 시간복잡도로 동작
• 배열로 쉽게 구현할 수 있다.
• 우선순위 큐 용도로 널리 사용된다.

heap 구현법

• 사실 알고리즘 시험에서 힙을 직접 구현하는 경우는 없다고 보면 된다
• python, java의 경우 heap이 이미 기본 라이브러리로서 제공되기 때문이다
• 그러나 javascript는 기본 라이브러리에 heap 자료구조가 없어 외부 라이브러리를 가져다 쓰거나 직접구현해야한다.
  • 그래서 만약 javascript로 시험이 보는 경우 별도로 제공이 되는 경우가 많다.

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

  insert(val) {
    this.heap.push(val);
    this.bubbleUp();
  }

  bubbleUp() {
    let idx = this.heap.length - 1;
    while (idx > 0) {
      let parentIdx = Math.floor((idx - 1) / 2);
      if (this.heap[parentIdx] <= this.heap[idx]) break;
      [this.heap[parentIdx], this.heap[idx]] = [this.heap[idx], this.heap[parentIdx]];
      idx = parentIdx;
    }
  }

  extractMin() {
    if (this.heap.length === 0) return undefined;
    const min = this.heap[0];
    const end = this.heap.pop();
    if (this.heap.length > 0) {
      this.heap[0] = end;
      this.sinkDown(0);
    }
    return min;
  }

  sinkDown(idx) {
    const length = this.heap.length;
    const element = this.heap[idx];
    while (true) {
      let leftIdx = 2 * idx + 1;
      let rightIdx = 2 * idx + 2;
      let swap = null;

      if (leftIdx < length && this.heap[leftIdx] < element) {
        swap = leftIdx;
      }
      if (rightIdx < length &&
          this.heap[rightIdx] < (swap === null ? element : this.heap[leftIdx])) {
        swap = rightIdx;
      }
      if (swap === null) break;
      [this.heap[idx], this.heap[swap]] = [this.heap[swap], this.heap[idx]];
      idx = swap;
    }
  }
}

import heapq 

heap = []
heapq.heappush(heap, 4)
heapq.heappush(heap, 1)
heapq.heappush(heap, 7)

minimum = heapq.heappop(heap)  # 최소값 1 반환, 힙에서 제거
최대힙을 구현할 경우에는 값을 음수로 바꿔서 넣는 방식으로 처리한다.

python
import heapq 

heap = []
heapq.heappush(heap, -4)
heapq.heappush(heap, -1)
heapq.heappush(heap, -7)

maximum = -heapq.heappop(heap)  # 최대값 7 반환, 힙에서 제거

알고리즘 문제 풀이에서의 활용

• 우선순위 큐를 직접 구현하지 않고 heap 자료구조를 활용해서 시간복잡도를 줄일 수 있다.
• 다익스트라, A* 등 최단경로 알고리즘에 자주 쓰인다.
• K번째 최댓값 찾기, merge k sorted lists 같은 문제도 heap으로 효율적으로 해결이 가능하다.

정리

• Heap은 완전 이진트리 구조로 구성되며, 삽입과 삭제가 빠르고, 우선순위 큐 등 다양한 알고리즘 문제에서 유용하게 쓰이는 핵심적인 자료구조이다.
• 자바스크립트에서는 배열로 직접 구현하고, 파이썬에서는 heapq를 이용해 손쉽게 사용할 수 있다.