힙, 이진 힙

힙은 이진 힙 이라고도 하며, 최댓값 또는 최솟값을 찾아내는 연산을 빠르게 하기 위해 고안된 이진트리를 기본으로 한 자료구조이다.

힙은 다음과 같은 속성을 갖고 있다.

• 이진트리 (Binary Tree) 이다.
• 부모노드의 키값과 자식노드의 키값 사이에는 대소관계가 성립한다.
  - 대소관계는 부모자식 간에만 성립되며 형제사이에는 대소관계가 성립하지 않는다.

힙의 종류

1. 최대 힙 (Max Heap)

• 부모노드의 키값이 자식노드의 키값보다 크다.
• 가장 큰 값이 루트노드에 있다.

2. 최소 힙 (Min Heap)

• 부모노드의 키값이 자식노드의 키값보다 작다.
• 가장 작은 값이 루트노드에 있다.

힙 특징

힙은 이진트리이다. 일반적으로 배열로 표현한다.
힙을 배열로 나타낼때 다음과 같은 특징이 있다.

현재 노드의 인덱스가 idx라고 가정할때,

부모 노드의 인덱스: (idx - 1) / 2 를 내림한값
왼쪽 자식노드의 인덱스: 2 x idx + 1
오른쪽 자식노드의 인덱스: 2 x idx + 2

힙 구현

class MaxBinaryHeap {
  constructor() {
    this.values = []; // 힙은 일반적으로 배열로 표현한다.
  }

  // 배열의 맨 끝에 노드를 넣어주고 bubbleUp 메소드를 통해 힙의 특성에 맞게 노드들의 자리를 조정한다.
  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;
    }
  }
  
  // 가장 큰 값을 찾아 제거하고 리턴하는 메소드
  extractMax() {
    const max = this.values[0];
    const end = this.values.pop();
    if (this.values.length > 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;
    }
  }
}