4.7Binary Heaps

Heap의 정의와 종류

힙(Heap)은 차곡차곡 쌓아올린 더미라는 뜻으로, 완전 이진 트리의 형태로 앞서 살펴본 이진 탐색 트리와 비슷하지만, 힙의 종류에 따라 규칙이 약간 다르다.

• MaxBinaryHeap(최대 힙): 부모 노드가 항상 자식 노드들보다 커야한다.
• MinBinaryHeap(최소 힙): 부모 노드가 항상 자식 노드들보다 작아야한다.

정의를 보면 알 수 있듯이 형제 노드들간에는 순서가 없다. 또, 앞서 완전 이진 트리라는 용어를 썼는데 이는 각 노드들이 최대한 가득 차 있어야 한다는 의미고, 왼쪽부터 자식 노드가 채워져야 한다는 의미다. 즉, 왼쪽이 비어있는데 오른쪽은 자식이 있다거나 하는 치우친 트리는 힙이 될 수 없다.

이미지 출처 : #

힙은 데이터 구조에서 아주 많이 쓰이는 우선순위 큐(Priority Queue)를 구현할 때 쓰인다. 이에 대해선 차차 알아보자.

Heap 구현하기

부모-자식간의 순서가 정해져있는 구조다보니, array로 힙의 요소들을 레벨 순서대로 저장한다면 부모 노드에 따라 해당 노드의 자식 노드들의 위치도 정해진다. 예를 들어, 배열 안의 n번째 요소에 대해 왼쪽 자식 노드는 2n + 1번째에, 오른쪽 자식 노드는 2n + 2번째에 저장된다. 반대로, n번째 자식 노드의 부모는 Math.floor((n-1)/2)번째에 저장된다.

이미지 출처 : #

Bubble-up

Heap에 구성요소를 추가한다면, 정확한 위치를 찾는 것이 중요해진다. 형제들끼리는 순서가 상관없고 부모-자식간에만 순서가 중요하므로, Heap에서 데이터를 추가하면 그 부모와 비교해서 큰 쪽을 스왑하는 식으로 순서를 조정할 수 있다. 이것을 Bubble-up이라고 한다.

Insert 구현하기

따라서 Heap의 insert 메소드를 구현할 때, 수도코드는 이렇게 될 것이다:

• 값을 array에 추가한다.
• 제대로 된 위치를 찾기 위해 버블업을 한다:
  • values 속성의 길이보다 1 적은 index 변수를 만든다.
  • parentIndex라는 변수를 만든다. Math.floor((index - 1)/2)다.
  • parentIndex의 value가 child index의 value보다 작을때까지 계속 아래를 루프한다.
    • parentIndex의 value와 child index의 value를 스왑한다.
    • index에 parentIndex를 할당한다.

javascript
class MaxBinaryHeap {
  constructor(){
    this.values = [];
  }
  insert(element){
    this.values.push(element);
    this.bubbleUp();
  }
  bubbleUp(){
    let idx = this.values.length - 1;
    const element = this.values[idx];
    while(idx > 0){
      let parentIdx = Math.floor((idx - 1) / 2);
      let parent = this.values[parentIdx];
      if(element <= parent) break;
      this.values[parentIdx] = element;
      this.values[idx] = parent;
      idx = parentIdx;
      }
  }
}

Remove(또는, ExtractMax) 구현하기

앞서 언급했듯, heap이 가장 많이 쓰이는 경우는 우선순위 큐인데, 이런 데이터 구조에서 가장 빈번하게 일어나는 일은 가장 큰 값을 제거, 추출하는 것이다.

가장 큰 값(루트 노드)을 제거하는 과정은 이렇게 이루어진다:

• 우선, 루트 노드를 제거하고 가장 끝에 있는 데이터(말단에 있는 자식 데이터일 것이다)를 루트 노드 자리에 올린다.
• 이 값은 물론 제 위치가 아니다. 제 위치로 옮기기 위해 sink down(또는, bubble-down)을 한다. 즉, 아래에 있는 노드들과 크기를 비교해 제 위치를 찾을때까지 재귀적으로 스왑한다.

수도코드는 아래와 같이 쓸 수 있다:

• 첫 값(루트 노드)을 마지막 값과 스왑한다.
• pop으로 마지막 값을 반환하고, 배열에선 제거한다.
• 새로운 루트 노드를 올바른 자리로 옮기기 위해 sink down을 한다.
  • parent index는 0에서 시작한다.
  • left child의 index는 2 * index + 1이고, right child는 2 * index + 2이다.
  • parent의 값이 이 값들 중 하나보다 작다면 그 값과 스왑한다. 만약 둘다가 parent보다 크다면, 그 둘 중 더 큰 값과 스왑한다.
  • 새로 바꾼 child index가 새로운 parent index가 되고, 자식 노드들보다 parent가 더 클때까지 스왑한다.

javascript
extractMax(){
  const max = this.values[0];
  const end = this.values.pop();
  if(this.values.length > 0){ // pop 했을때 0이면 end를 다시 values[0]에 할당하면 안됨
    this.values[0] = end;
    this.sinkDown();
  }
  return max;
}

sinkDown(){
  let idx = 0;
  const length = this.values.length;
  const element = this.values[0];
  while(true){
    let leftChildIdx = 2 * idx + 1;
    let rightChildIdx = 2 * idx + 2;
    let leftChild, rightChild;
    let swap = null;

    if(leftChildIdx < length){
      leftChild = this.values[leftChildIdx];
      if(leftChild > element){
        swap = leftChildIdx;
      }
    }
    if(rightChildIdx < length){
      rightChild = this.values[rightChildIdx];
      // 오른쪽이 더 크면 오른쪽과 스왑하게
      if(
          (swap === null && rightChild > element) ||
          (swap !== null && rightChild > leftChild)
        ){
          swap = rightChildIdx;
         }
    }
    if(swap === null) break;
    this.values[idx] = this.values[swap];
    this.values[swap] = element;
    idx = swap;
  }
}

우선순위 큐 만들기

A data structure where each element has a priority. Elements with higher priorities are served before elements with lower priorities.

우선순위가 있는 큐(FIFO 형태의 데이터)를 구현할 때 heap이 유용하다. 예를 들어, 병원에서 치료를 받아야 하는 환자들을 관리한다고 하자. 보다 우선순위가 높은 환자부터 높은 노드에 두고, 덜 급한 환자는 자식 노드 단계에서 관리할 수 있을 것이다.

우선순위 큐의 수도코드는 아래와 같이 작성할 수 있다:

• Min Binary Heap을 만든다.(현실에서 높은 우선순위가 낮은 숫자를 가진 경우가 많다.)
• 각 Node는 val과 priority 속성을 가진다. priority로 힙을 만든다.
• Enqueue 메소드로 value와 priority를 받아 새로운 Node를 만들고 올바른 위치에 배치한다.
• Dequeue 메소드는 루트 노드를 없애고 해당 노드를 반환하고, 힙을 정확하게 정렬한다.

Min Binary Heap은 앞서 만든 Max Binary Heap과 로직 면에서 크게 차이나지 않는다. element와 parent, 또는 child를 비교할때 부등호의 방향을 바꾸면 된다.

javascript
class Node {
  constructor(val, priority){
    this.val = val;
    this.priority = priority;
  }
}

class PriorityQueue {
  constructor(){
    this.values = [];
  }
  enqueue(val, priority){
    let newNode = new Node(val, priority)
    this.values.push(element);
    this.bubbleUp();
  }
  bubbleUp(){
    let idx = this.values.length - 1;
    const element = this.values[idx];
    while(idx > 0){
      let parentIdx = Math.floor((idx - 1) / 2);
      let parent = this.values[parentIdx];
      if(element.priority >= parent.priority) break; // 다른 부분
      this.values[parentIdx] = element;
      this.values[idx] = parent;
      idx = parentIdx;
      }
  }
  dequeue(){
  const min = this.values[0];
  const end = this.values.pop();
  if(this.values.length > 0){
    this.values[0] = end;
    this.sinkDown();
   }
    return min;
  }

  sinkDown(){
    let idx = 0;
    const length = this.values.length;
    const element = this.values[0];
    while(true){
      let leftChildIdx = 2 * idx + 1;
      let rightChildIdx = 2 * idx + 2;
      let leftChild, rightChild;
      let swap = null;

      if(leftChildIdx < length){
        leftChild = this.values[leftChildIdx];
        if(leftChild.priority < element.priority){
          swap = leftChildIdx;
        }
      }
      if(rightChildIdx < length){
        rightChild = this.values[rightChildIdx];
        // 오른쪽이 더 크면 오른쪽과 스왑하게
        if(
            (swap === null && rightChild.priority < element.priority) ||
            (swap !== null && rightChild.priority < leftChild.priority)
          ){
            swap = rightChildIdx;
          }
      }
      if(swap === null) break;
      this.values[idx] = this.values[swap];
      this.values[swap] = element;
      idx = swap;
    }
  } 
}

const ER = new PriorityQueue();
ER.enqueue("common cold", 5);
ER.enqueue("gunshot wound", 1);
ER.enqueue("high fever", 4);
ER.enqueue("broken arm", 2);
ER.enqueue("glass in foot", 3);

Binary Heap의 Big O

Binary Heap은 추가/제거가 O(log N)으로 아주 빠르다. 16개의 데이터를 가진 힙에 데이터를 추가한다고 할 때, 가장 안 좋은 경우더라도 맨 마지막에 데이터를 넣고 4번만 비교하면 끝이 난다. 또, 최댓값/최솟값을 확인하는 것이 O(1)로 매우 빠르다. 무엇이 필요한지에 따라 루트 노드에 항상 그 값이 저장되어 있기 때문이다.

단, 검색은 O(N)으로, 부모-자식 간에만 대소관계가 성립하다보니 모든 노드를 탐색해야만 원하는 값을 찾을 수 있게되는 경우가 있기 때문이다. 예를 들어, 아래에서 8을 찾는다고 해보자.

bash
        1
      /   \
     3     5
    / \   /
   4   9  8

1부터 시작해 3으로 내려가 3보다 큰 값이니 4와 9를 보지만 없다. 5로 돌아가서야 비로소 발견할 수 있다. 즉, 모든 노드를 탐색해야하는 것이다.

이는 이전에 배운 이진 탐색 트리가 비록 트리의 균형 상태에 따라 다를 수 있어도 평균적으로는 검색에 O(log n)이 필요한 것과 대비하면 불리하다.(물론 이진 탐색 트리 역시 최악의 경우 O(n)이다. 이를 보완하기 위해 AVL 트리 등이 나온 것이다.)

즉, Binary Heap은 우선순위 큐처럼 데이터를 빠르게 추가/제거하는데 유용한 데이터 구조고, 이진 탐색 트리 등에 비하면 탐색에선 불리하다.