[자료구조] 이진힙 - BinaryHeap

1. 이진힙이란?

힙이란 모양은 트리와 같다.

트리와는 다르게 힙은 부모와 자식간의 규칙이 있다는 것이다.

 

최대 이진힙에서는 부모노드가 항상 자식노드보다 큰 값을 가진다.

왼쪽이나 오른쪽 상관없이 한 레벨 아래에 있는 자식 노드보다 항상 부모 노드가 크다.

형제들 사이에는 특별한 규칙이 없다.

 

최소 이진힙에서는 그 반대이다. 부모 노드가 언제나 양쪽의 자식보다 작다.

이진힙은 언제나 가장 적은 공간을 차지한다.

 

2. 최대 이진힙 구현

(1) 클래스

class MaxBinaryHeap {
  constructor() {
    this.values = [];
  }
}

(2) insert

insert(element) {
    this.values.push(element);
    this.bubbleUp();
}

(3) 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;
    }
}

(4) extractMax (루트 제거 후 마지막 자식 넣어주고 정렬)

extractMax() {
    const max = this.values[0];
    const end = this.values.pop();
    if (this.values.length > 0) {
      this.values[0] = end;
      this.sinkDown();
    }
    return max;
}

(5) sinkDown

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;
    }
}

3. 이진힙 빅O

insertion(삽입)	removal(제거)	search(탐색)
O(logn)	O(logn)	O(n)