Post

힙(Heap)에 대해 알아보기

Posted
By eunbi
7 min read
힙(Heap)에 대해 알아보기

힙(Heap)이란?

힙은 완전 이진트리를 기반으로 하는 자료구조이다. 특정한 조건을 만족하도록 설계된 구조로써 주로 우선순위 큐를 구현할 때 사용된다. 힙을 적절히 사용하기 위해 자세히 알아보도록 하자.


힙의 특징

  1. 힙 속성
    1. 최대 힙
      1. 부모 노드의 키 값이 자식 노드의 키보다 크거나 같다.
      2. 즉, 루트 노드에는 가장 큰 값이 위치한다.
    2. 최소 힙
      1. 부모 노드의 키 값이 자식 노드의 키 값보다 작거나 같다.
      2. 즉, 루트 노드에는 가장 작은 값이 위치한다.
  2. 완전 이진 트리
    • 힙은 완전 이진 트리 형태를 갖는다.
    • 마지막 레벨을 제외한 모든 레벨이 꽉 차 있으며, 마지막 레벨의 노드는 왼쪽에서 오른쪽으로 채워진다.

힙의 활용

  1. 우선 순위 큐
    1. 데이터가 우선순위에 따라 처리되는 큐를 구현할 때 사용된다.
    2. 삽입, 삭제 연산에서 효율적이다.
  2. 힙 정렬
    1. 힙을 이용해 정렬 알고리즘을 구현한다.
    2. 시간 복잡도: O(nlogn)
  3. 최댓값/최솟값 추출
    1. 최대 힙: 배열에서 최댓값을 효율적으로 추출
    2. 최소 힙: 배열에서 최솟값을 효율적으로 추출


힙의 동작

  1. 삽입
    • 새로운 요소를 트리의 마지막 자리에 삽입한 후 부모-자식 관계를 재조정하여 힙 속성을 유지한다.
    • 시간 복잡도: O(logn)
  2. 삭제
    • 최대 힙에서는 루트 노드를, 최소 힙에서는 루트 노드를 제거한다.
    • 마지막 노드를 루트로 이동한 뒤, 자식 노드와 값을 교환하며 힙속성을 유지한다.
    • 시간 복잡도: O(logn)

힙의 구현 방식

  1. 배열을 사용한 구현
    • 트리에서의 부모-자식 관계는 배열의 인덱스를 이용해 계산한다.
      • 부모 노드: parent(i)=⌊(i−1)/2⌋
      • 왼쪽 자식: left(i)=2i+1
      • 오른쪽 자식: right(i)=2i+2

[예시] 최소 힙 구현

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87

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

  // 요소 삽입
  insert(value) {
    this.heap.push(value);
    this.bubbleUp();
  }

  // 최솟값 제거
  remove() {
    if (this.heap.length === 1) return this.heap.pop();
    const min = this.heap[0];
    this.heap[0] = this.heap.pop();
    this.bubbleDown();
    return min;
  }

  // 힙 속성 유지 (삽입 시)
  bubbleUp() {
    let index = this.heap.length - 1;
    const lastInserted = this.heap[index];

    while (index > 0) {
      const parentIndex = Math.floor((index - 1) / 2);
      const parentValue = this.heap[parentIndex];
      if (lastInserted >= parentValue) break;

      // Swap
      this.heap[index] = parentValue;
      index = parentIndex;
    }

    this.heap[index] = lastInserted;
  }

  // 힙 속성 유지 (삭제 시)
  bubbleDown() {
    let index = 0;
    const length = this.heap.length;
    const root = this.heap[index];

    while (true) {
      const leftChildIdx = 2 * index + 1;
      const rightChildIdx = 2 * index + 2;
      let smallestIdx = index;

      if (
        leftChildIdx < length &&
        this.heap[leftChildIdx] < this.heap[smallestIdx]
      ) {
        smallestIdx = leftChildIdx;
      }

      if (
        rightChildIdx < length &&
        this.heap[rightChildIdx] < this.heap[smallestIdx]
      ) {
        smallestIdx = rightChildIdx;
      }

      if (smallestIdx === index) break;

      // Swap
      [this.heap[index], this.heap[smallestIdx]] = [
        this.heap[smallestIdx],
        this.heap[index]
      ];
      index = smallestIdx;
    }

    this.heap[index] = root;
  }
}

// 사용 예시
const heap = new MinHeap();
heap.insert(5);
heap.insert(2);
heap.insert(10);
heap.insert(1);

console.log(heap.remove()); // 1
console.log(heap.remove()); // 2
console.log(heap.remove()); // 5

[예시] 최대 힙 구현

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86

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

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

  remove() {
    if (this.heap.length === 1) return this.heap.pop();
    const max = this.heap[0];
    this.heap[0] = this.heap.pop();
    this.bubbleDown();
    return max;
  }

  bubbleUp() {
    let index = this.heap.length - 1;
    const lastInserted = this.heap[index];

    while (index > 0) {
      const parentIndex = Math.floor((index - 1) / 2);
      const parentValue = this.heap[parentIndex];
      if (lastInserted <= parentValue) break;

      // Swap
      this.heap[index] = parentValue;
      index = parentIndex;
    }

    this.heap[index] = lastInserted;
  }

  bubbleDown() {
    let index = 0;
    const length = this.heap.length;
    const root = this.heap[index];

    while (true) {
      const leftChildIdx = 2 * index + 1;
      const rightChildIdx = 2 * index + 2;
      let largestIdx = index;

      // 왼쪽 자식과 비교
      if (
        leftChildIdx < length &&
        this.heap[leftChildIdx] > this.heap[largestIdx]
      ) {
        largestIdx = leftChildIdx;
      }

      // 오른쪽 자식과 비교
      if (
        rightChildIdx < length &&
        this.heap[rightChildIdx] > this.heap[largestIdx]
      ) {
        largestIdx = rightChildIdx;
      }

      if (largestIdx === index) break;

      // Swap
      [this.heap[index], this.heap[largestIdx]] = [
        this.heap[largestIdx],
        this.heap[index]
      ];
      index = largestIdx;
    }

    this.heap[index] = root;
  }
}

// 사용 예시
const maxHeap = new MaxHeap();
maxHeap.insert(5);
maxHeap.insert(2);
maxHeap.insert(10);
maxHeap.insert(1);

console.log(maxHeap.remove()); // 10
console.log(maxHeap.remove()); // 5
console.log(maxHeap.remove()); // 2
console.log(maxHeap.remove()); // 1


힙의 장단점

  • 장점
    • 효율적인 삽입과 삭제: O(logn)의 시간 복잡도로 최댓값/최솟값을 삽입/삭제 가능하다.
    • 우선 순위 큐 구현: 높은 우선 순위로 빠르게 접근할 수 있다.
  • 단점
    • 힙 구조를 유지해야 하므로 배열 정렬에 비해 삽인과 삭제의 추가 연산이 필요하다.


힙을 사용하는 알고리즘

  1. 다익스트라(Dijkstra)
    • 최단 경로 탐색에서 우선순위 큐로 힙을 활용한다.
  2. 프림(Prim)
    • 최소 신장 트리(MST)에서 우선순위 큐로 사용한다.
알고리즘, 개념
JavaScript 알고리즘 힙
This post is licensed under CC BY 4.0 by the author.