[자료구조] Heap

이번 포스팅에서는 Heap에 대해서 정리하겠습니다.

Heap은 이진 트리 구조를 가지며 루트가 최대 값을 가지는 경우 최대 이진힙이라 부르고 최소 값을 가지는 경우 최소 이진힙이라 부릅니다. 이진 티르는 배열로 나타낼 수 있는데 배열에서 i번째 인덱스의 요소를 하나 선택했을 때, 그 자식 요소는 2i+1 번째 인덱스(left)의 요소와 2i+2 번째 인덱스의 요소(right)입니다.

이러한 규칙을 이용하면 빠른 시간 내에 데이터를 탐색할 수 있으며 요소를 추가하거나 제거할 때 O(logN) 시간 복잡도를 가집니다. 아래의 코드는 최대 이진힙을 구현한 것 입니다.

class Heap {
  constructor() {
    this.values = [];  // 배열을 value값으로 가집니다.
  }
  // 새로운 값을 추가합니다.
  insert(value) {
    this.values.push(value); 
    this.bubleup();  
  }
  // 추가한 값의 부모 요소와 비교하여 큰 경우 위치를 바꿉니다.
  bubleup() {
    let idx = this.values.length - 1;
    const element = this.values[idx]; // 추가한 마지막 요소
    while (idx > 0) {
      const parentIdx = Math.floor((idx - 1) / 2);
      const parent = this.values[[parentIdx]];

      if (element < parent) break;
      this.values[parentIdx] = element;
      this.values[idx] = parent;
      idx = parentIdx;
    }
  }
  // 가장 큰 값(root)의 value를 꺼내고 마지막 인덱스의 요소를 root로 이동 시 킵니다. 
  extractMax() {
    const max = this.values[0];
    const end = this.values.pop();

    this.values[0] = end;
    this.sinkDown();

    return max;
  }
  // root와 자식들을 비교해서 자식 중 가장 큰 요소와 자리를 바꿉니다.
  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 swap = null;
      let leftChild, rightChild;

      if (rightChildIdx > length) return;
      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;
      }
    }
  }
}