자료구조 ) Heap을 이용하여 우선순위 큐 구현하기

작성일 In Views: Disqus:

배열을 조작하여 원하는 값을 도출할 때 배열을 조작하는 로직의 시간복잡도 때문에 고민하는 경우가 있습니다. 예를들어 O(N)의 시간복잡도로 구현해야하는 문제에서 순회문 안에서 배열의 앞의 원소를 추가/삭제하거나 배열에서 가장 크거나 작은 값을 뽑아오는 경우가 그렇습니다. 저번 포스트에서는 배열의 앞쪽 원소를 조작할 때의 시간복잡도를 연결리스트 자료구조로 줄일 수 있다는 것을 확인하였습니다. 이번 포스트에서는 힙 자료구조를 통해 우선순위큐를 구현하여 배열 원소들 중 최대/최소값을 O(logN)의 시간복잡도로 처리하는 방법을 알아보겠습니다.

▪︎ 힙 (Heap)

image.png

힙은 완전 이진트리 구조로 되어있는 자료 구조입니다. 완전 이진트리란 각각의 노드가 최대 두 개의 자식 노드를 가지는 형태에서 마지막 레벨을 제외한 모든 노드가 완전히 채워진 것을 말합니다. 힙은 직접 연결된 부모-자식 노드 간의 크기를 비교하여 정해진 우선순위에 맞게 구성되어있습니다. 루트 노드에 가장 우선 순위가 높은 데이터를 위치시키고 각 노드를 연결하고 조정하여 모든 노드가 자식 노드에 비해 우선 순위가 크거나 같게 구현하면 됩니다. 이 때 값이 낮을 수록 우선순위가 높은 힙을 최소 힙(Min Heap)이라 하고, 값이 높을수록 우선순위가 높은 힙을 최대 힙(Max Heap)이라고 합니다.

▫︎ 데이터 삽입

힙에 데이터를 삽입하는 과정입니다. 최소힙을 예시로 들었으나 최대힙 또한 우선순위 설정의 차이만 있을 뿐 같은 과정을 거칩니다. 이렇게 데이터를 추가하고 아래에서부터 힙을 재정렬하는 방식을 Heapify Up 이라 합니다.

image.png

1. 힙의 마지막 위치에 삽입할 데이터를 추가합니다.

image.png

2. 추가된 데이터와 부모노드의 값을 비교하여 우선순위가 높다면 자리를 바꿉니다.

image.png

3. 추가된 데이터가 루트로 이동하거나 부모 노드보다 우선순위가 낮을 때까지 ‘2’를 반복합니다.

▫︎ 데이터 삭제

힙에 데이터를 삭제하는 과정입니다. 최소힙을 예시로 들었으나 최대힙 또한 우선순위 설정의 차이만 있을 뿐 같은 과정을 거칩니다. 이렇게 데이터를 삭제하고 마지막 데이터를 루트데이터에 위치시킨 후, 위에서부터 힙을 재정렬하는 방식을 Heapify Down 이라 합니다.

image.png

1. 루트 노드의 데이터를 삭제하고 그 자리에 힙의 마지막 노드를 가져옵니다.

image.png

2. 루트로 가져온 데이터와, 그 자식 노드들 중 우선순위가 더 높은 자식 노드를 비교하여 가져온 데이터가 우선순위가 낮다면 자리를 바꿉니다.

3. 마지막 노드에서 가져온 데이터가 트리의 종단으로 이동하거나 비교한 자식 노드보다 우선 순위가 높을 때까지 ‘2’를 반복합니다.

▪︎ 우선순위 큐 (Priority Queue)

image.png

image.png

우선순위 큐는 힙 자료구조를 이용해 만든 추상적인 개념의 자료구조입니다. 기본적인 큐가 First In First Out으로 동작하는 것과는 다르게 큐에 입력된 데이터들 중 우선순위가 높은 데이터를 먼저 호출합니다.

힙을 통한 우선순위 큐는 자바스크립트에서는 배열을 이용하여 추상적으로 구현할 수 있습니다. 힙을 클래스로 선언하고 배열을 정의합니다. 그리고 배열의 각 인덱스를 통해 트리를 추상화 합니다. 배열의 첫 인덱스부터 루트 노드, 이후엔 왼쪽 자식 노드, 오른쪽 자식 노드 순으로 트리의 depth를 따라 순차적으로 배열에 저장됩니다. 이후 해당 배열을 조작하는 클래스 메소드를 통해 힙을 재정렬하게 됩니다.

▪︎ 자바스크립트로 우선순위 큐 구현

자바스크립트에서 힙의 구현은 다음과 같은 단계로 나눌 수 있습니다. 위에 서술한 힙의 데이터 추가/삭제에 관련한 예시와 함께 보시면 코드를 이해하기가 편합니다. 수월한 코드 구현을 위해 부모 노드와 자식 노드간의 위치에 대한 값은 외워두는게 좋습니다.

  • 부모 노드 - 자식 노드 간 인덱스
    부모 노드 (자식 노드 기준) : Math.floor((childIndex - 1) / 2)
    왼쪽 자식 노드 (부모 노드 기준) : parentIndex * 2 + 1
    오른쪽 자식 노드 (부모 노드 기준) : parentIndex * 2 + 2

1. 힙 클래스 생성

2. 힙 정렬에 필요한 메서드 추가 (heapifyUp, heapifyDown)

3. 힙 조작 메서드 추가

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
// 1. 최소힙 클래스 생성
class MinHeap {
  constructor() {
    this.heap = [];
    this.length = 0;
  }

  // 3. 힙 조작 메서드 추가
  push(value) {
    this.heap.push(value);
    this.heapifyUp();
    this.length++;
  }
  delete() {
    const root = this.heap[0];

    if (this.heap.length === 0) return null;
    else if (this.heap.length === 1) this.heap = [];
    else {
      this.heap[0] = this.heap.pop();
      this.heapifyDown();
    }

    this.length--;
    return root;
  }

  // 2. 힙 정렬에 필요한 메서드 추가
  getLeftChildIndex(parentIndex) {
    return parentIndex * 2 + 1;
  }
  getRightChildIndex(parentIndex) {
    return parentIndex * 2 + 2;
  }
  getParentIndex(childIndex) {
    return Math.floor((childIndex - 1) / 2);
  }
  swap(index1, index2) {
    [this.heap[index1], this.heap[index2]] = [this.heap[index2], this.heap[index1]]; // 두 인덱스에 위치한 데이터의 위치를 서로 변경
  }
  heapifyUp() {
    let cIdx = this.heap.length - 1; // 새로 추가된 데이터의 위치를 변수에 저장하고 추적

    while (cIdx > 0) {
      const parentIdx = this.getParentIndex(cIdx); // 추가된 데이터와 비교할 부모 노드의 위치

      if (this.heap[cIdx] < this.heap[parentIdx]) {
        this.swap(cIdx, parentIdx);
        cIdx = parentIdx;
      } else break;
    }
  }
  heapifyDown() {
    let cIdx = 0; // 루트 노드로 이동된 힙의 마지막 노드의 위치를 변수에 저장하고 추적

    while (this.getLeftChildIndex(cIdx) < this.heap.length) {
      const leftChildIndex = this.getLeftChildIndex(cIdx);
      const rightChildIndex = this.getRightChildIndex(cIdx);
      // 두 자식 노드 중 우선순위가 높은 자식 노드의 위치
      // 자식 노드가 하나일 경우엔 반드시 왼쪽 노드에 위치하기 때문에 그 점을 고려하여 삼항연산자 작성
      const targetIndex = this.heap[leftChildIndex] > this.heap[rightChildIndex] ? rightChildIndex : leftChildIndex;

      if (this.heap[cIdx] > this.heap[targetIndex]) {
        this.swap(cIdx, targetIndex);
        cIdx = targetIndex;
      } else break;
    }
  }
}

같은 방식으로 최대힙도 만들 수 있습니다. 구성을 동일하나, heapifyUp과 heapifyDown에서 두개의 노드를 비교하는 식만 변경하면 됩니다.

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
class MaxHeap {
  constructor() {
    this.heap = [];
    this.length = 0;
  }

  push(value) {
    this.heap.push(value);
    this.length++;
    this.heapifyUp();
  }

  delete() {
    const root = this.heap[0];

    if (this.heap.length === 0) return null;
    else if (this.heap.length === 1) this.heap = [];
    else {
      this.heap[0] = this.heap.pop();
      this.heapifyDown();
    }

    this.length--;
    return root;
  }

  getLeftChildIndex(parentIndex) {
    return parentIndex * 2 + 1;
  }
  getRightChildIndex(parentIndex) {
    return parentIndex * 2 + 2;
  }
  getParentIndex(childIndex) {
    return Math.floor((childIndex - 1) / 2);
  }
  swap(index1, index2) {
    [this.heap[index1], this.heap[index2]] = [this.heap[index2], this.heap[index1]];
  }
  heapifyUp() {
    let cIdx = this.heap.length - 1;

    while (cIdx > 0) {
      const parentIdx = this.getParentIndex(cIdx);

      if (this.heap[cIdx] > this.heap[parentIdx]) {
        this.swap(cIdx, parentIdx);
        cIdx = parentIdx;
      } else break;
    }
  }
  heapifyDown() {
    let cIdx = 0;

    while (this.getLeftChildIndex(cIdx) < this.heap.length) {
      const leftChildIndex = this.getLeftChildIndex(cIdx);
      const rightChildIndex = this.getRightChildIndex(cIdx);
      const targetIndex = this.heap[leftChildIndex] < this.heap[rightChildIndex] ? rightChildIndex : leftChildIndex;
      // 자식노드가 하나만 있을 때에는 왼쪽거만 있을테니 조건문이 undefined일 때는 왼쪽걸 선택하도록 주의해야함.

      if (this.heap[cIdx] < this.heap[targetIndex]) {
        this.swap(cIdx, targetIndex);
        cIdx = targetIndex;
      } else break;
    }
  }
}

▪︎ Example of Apply

image.png

image.png

위 문제는 그리디 문제입니다. 두 개의 카드 묶음을 합치면서 하나로 합쳐질 때까지의 비교 횟수의 최솟값을 출력하기 위해서는 매번 카드묶음들 중 가장 작은 두 묶음을 비교해야합니다. 이 때 가장 작은 두 묶음을 찾기 위해 for문 등으로 순회할 경우 100,000 _ (100,000 - 1) _ (100,000 - 2) * … 2 의 시행 횟수를 가집니다 (시간복잡도는 O(N^2)). sort 메소드를 이용하여 정렬을 하는 경우에도 O(N^2log(N))의 시간복잡도이므로 시간제한을 통과할 수 없습니다.

따라서 조건에 맞게 문제를 풀기 위해서는 주어진 카드 묶음에서 가장 크기가 작은 카드 묶음을 O(N)이하로 가져와 O(N^2) 이하로 해결해야 합니다. 최소힙을 적용한 우선순위 큐를 이용하면 가장 크기가 작은 카드 묶음을 O(logN)의 시간복잡도로 가져올 수 있습니다.

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
class MinHeap {
  constructor() {
    this.heap = [];
    this.length = 0;
  }

  push(value) {
    this.heap.push(value);
    this.heapifyUp();
    this.length++;
  }

  delete() {
    const root = this.heap[0];

    if (this.heap.length === 0) return null;
    else if (this.heap.length === 1) this.heap = [];
    else {
      this.heap[0] = this.heap.pop();
      this.heapifyDown();
    }

    this.length--;
    return root;
  }

  getLeftChildIndex(parentIndex) {
    return parentIndex * 2 + 1;
  }
  getRightChildIndex(parentIndex) {
    return parentIndex * 2 + 2;
  }
  getParentIndex(childIndex) {
    return Math.floor((childIndex - 1) / 2);
  }
  swap(index1, index2) {
    [this.heap[index1], this.heap[index2]] = [this.heap[index2], this.heap[index1]];
  }
  heapifyUp() {
    let cIdx = this.heap.length - 1;

    while (cIdx > 0) {
      const parentIdx = this.getParentIndex(cIdx);

      if (this.heap[cIdx] < this.heap[parentIdx]) {
        this.swap(cIdx, parentIdx);
        cIdx = parentIdx;
      } else break;
    }
  }
  heapifyDown() {
    let cIdx = 0;

    while (this.getLeftChildIndex(cIdx) < this.heap.length) {
      const leftChildIndex = this.getLeftChildIndex(cIdx);
      const rightChildIndex = this.getRightChildIndex(cIdx);
      const targetIndex = this.heap[leftChildIndex] > this.heap[rightChildIndex] ? rightChildIndex : leftChildIndex;

      if (this.heap[cIdx] > this.heap[targetIndex]) {
        this.swap(cIdx, targetIndex);
        cIdx = targetIndex;
      } else break;
    }
  }
}

const fs = require("fs");
const input = fs.readFileSync("dev/stdin").toString().trim().split("\n");
const arr = input.slice(1).map((v) => +v);
const minHeap = new MinHeap();

if (arr.length === 1) {
  console.log(0);
  return;
}
arr.forEach((el) => minHeap.push(el));
let answer = 0;

while (minHeap.length > 1) {
  const sum = minHeap.delete() + minHeap.delete();
  minHeap.push(sum);
  answer += sum;
}

console.log(answer);