Min Heap

• 이진 트리를 기반으로 한 자료구조
• 부모 노드가 자식들보다 작거나 같은 구조
• 가장 작은 값이 부모 노드에 위치하는 자료구조

---

1. heapifyUp()

메소드는 새로 들어온 노드가 최소 힙의 조건에 맞는 자리를 찾도록 도와주는 메소드

heapifyUp() {
  let index = this.heap.length - 1;
  while (index > 0) {
    const parentIndex = Math.floor((index - 1) / 2);
    if (this.heap[parentIndex] <= this.heap[index]) break;
    [this.heap[parentIndex], this.heap[index]] = [
      this.heap[index],
      this.heap[parentIndex],
    ];
    index = parentIndex;
  }
}

새로 들어온 값의 자리 (this.heap.length - 1)부터 시작하여

index의 값이 0이 될 때까지(= 부모노드가 될 때까지) 그의 부모 노드 Math.floor(index - 1) / 2와의 비교를 반복한다.

이진 트리의 특성 상 부모 노드가 자식들보다 값이 더 작거나 같아야하므로 이미 부모 노드가 현재 노드보다 값이 작거나 같다면 반복문을 종료한다. 만약 그렇지 않다면 swap을 진행하고 현재 값의 index를 parentIdx로 업데이트하며 과정을 반복한다.

부모 노드와 자식 노드의 인덱스 구하기

인덱스 i가 주어졌을 때 왼쪽 자식은 2 * i + 1에 위치하고, 오른쪽 자식은 2 * i + 2에 위치한다.

그러면 부모 노드는 반대로 자식 노드 인덱스 - 1 / 2에 위치하게 된다.

               10
            /      \
          20       30
         /  \      /
       40   50   100

여기 [10, 20, 30, 40, 50, 100]의 힙이 있다.

인덱스 4에 위치한 요소 50의 부모를 찾아보려고 한다.

4 - 1 / 2를 하면 1.5가 되고, 내림하면 1이 되어 부모의 값이 20임을 알 수 있다.

2. heapifyDown()

heapifyUp()이 새로 들어온 노드의 자리를 찾아주는 것이었다면, 

heapifyDown()은 루트 노드를 제거한 후 최소 힙의 조건에 맞도록 힙을 재정비하는 메소드이다.

  heapifyDown() {
    let index = 0;
    const length = this.heap.length;

    while (true) {
      let smallest = index;
      const leftChildIndex = 2 * index + 1;
      const rightChildIndex = 2 * index + 2;

      if (
        leftChildIndex < length &&
        this.heap[leftChildIndex] < this.heap[smallest]
      ) {
        smallest = leftChildIndex;
      }

      if (
        rightChildIndex < length &&
        this.heap[rightChildIndex] < this.heap[smallest]
      ) {
        smallest = rightChildIndex;
      }

      if (smallest === index) break;

      [this.heap[index], this.heap[smallest]] = [
        this.heap[smallest],
        this.heap[index],
      ];
      index = smallest;
    }
  }

루트 노드가 빠져나갔으므로 탐색을 0번 인덱스부터 시작한다.

왼쪽 자식 노드와 오른쪽 자식 노드의 인덱스를 찾고 부모 노드와 두 자식 노드 간의 비교를 수행한다.

초기값을 0으로 갖는 smallest라는 변수를 만들고, 조건에 따라 그 변수에 자식 노드의 인덱스 값을 할당한다.

이 smallest 변수는 자식 노드들과의 비교를 수행한 후에 밑에서 index의 노드와 서로 swap하게 된다.

leftChildIndex가 length보다 작고 (=범위를 벗어나지 않고) 왼쪽 자식 노드의 값이 부모 노드의 값보다 더 작다면 부모가 더 작아야하는 최소 힙의 성질을 만족하지 않으므로 둘을 바꾸기 위해 smallest에 leftChildIndex를 할당한다.

마찬가지로 rightChildIndex가 length보다 작고 오른쪽 자식 노드의 값이 부모 노드의 값보다 더 작다면 smallest에 rightChildIndex를 할당한다.

smallest가 index와 같다면 성질을 만족하는 것이므로 반복문을 종료한다.

반복문이 종료되지 않았다면 가장 작은 값으로 지정된 smallest와 초기 인덱스 값 index 간의 swap을 진행하고, index를 smallest로 업데이트해준다.

이 과정을 smallest와 index가 같아질 때까지, 더 이상 자신보다 큰 값이 부모 노드에 있지 않을 때까지 반복한다.

3. push(value)

힙에 값을 삽입하는 메소드이다.

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

힙은 배열로 구현되어 있고, 배열의 push 연산을 이용하고 있기 때문에 값이 맨 끝에 추가된다.

추가한 후 최소 힙의 성질을 만족할 수 있도록 마지막에 삽입된 요소를 끌어올려주는 heapifyUp()을 수행해준다.

4. pop()

힙의 루트 노드를 제거하는 메소드이다.

  pop() {
    if (this.isEmpty()) return null;

    const root = this.heap[0];
    const lastNode = this.heap.pop();

    if (!this.isEmpty()) {
      this.heap[0] = lastNode;
      this.heapifyDown();
    }

    return root;
  }

이미 힙이 비어있는 상태라면 null을 리턴한다.

루트 노드를 저장해둔다.

배열의 pop 연산을 수행한 후 그 값을 lastNode 변수에 저장해둔다.

힙이 비어있지 않다면 힙의 0번 인덱스(=부모 노드)에 lastNode의 값을 할당하고 힙의 성질을 만족할 수 있도록 heapifyDown()을 수행한다.

힙이 비어있지 않음을 체크하는 이유는 힙에 노드가 하나만 있는 경우도 있을 수 있기 때문이다.

마지막으로 저장해뒀던 루트 노드를 리턴한다.

5. isEmpty()

힙이 비어있지 않은지 확인하는 메소드이다. 불리언값을 리턴한다.

  isEmpty() {
    return this.heap.length === 0;
  }

같이 읽어보면 좋을 글

최종코드

class MinHeap {
  constructor() {
    this.heap = [];
  }

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

  pop() {
    if (this.isEmpty()) return null;

    const root = this.heap[0];
    const lastNode = this.heap.pop();

    if (!this.isEmpty()) {
      this.heap[0] = lastNode;
      this.heapifyDown();
    }

    return root;
  }

  isEmpty() {
    return this.heap.length === 0;
  }

  heapifyUp() {
    let index = this.heap.length - 1;
    while (index > 0) {
      const parentIndex = Math.floor((index - 1) / 2);
      if (this.heap[parentIndex] <= this.heap[index]) break;
      [this.heap[parentIndex], this.heap[index]] = [
        this.heap[index],
        this.heap[parentIndex],
      ];
      index = parentIndex;
    }
  }

  heapifyDown() {
    let index = 0;
    const length = this.heap.length;

    while (true) {
      let smallest = index;
      const leftChildIndex = 2 * index + 1;
      const rightChildIndex = 2 * index + 2;

      if (
        leftChildIndex < length &&
        this.heap[leftChildIndex] < this.heap[smallest]
      ) {
        smallest = leftChildIndex;
      }

      if (
        rightChildIndex < length &&
        this.heap[rightChildIndex] < this.heap[smallest]
      ) {
        smallest = rightChildIndex;
      }

      if (smallest === index) break;

      [this.heap[index], this.heap[smallest]] = [
        this.heap[smallest],
        this.heap[index],
      ];
      index = smallest;
    }
  }
}

간략버전

const heap = [];

function push(val) {
  heap.push(val);
  let cur = heap.length - 1;
  while (cur > 0) { // 부모와 비교하며 위로!
    let parent = Math.floor((cur - 1) / 2);
    if (heap[parent] <= heap[cur]) break;
    [heap[parent], heap[cur]] = [heap[cur], heap[parent]];
    cur = parent;
  }
}

function pop() {
  if (heap.length === 1) return heap.pop();
  const min = heap[0];
  heap[0] = heap.pop();
  let cur = 0;
  while (cur * 2 + 1 < heap.length) { // 자식과 비교하며 아래로!
    let left = cur * 2 + 1, right = cur * 2 + 2;
    let smaller = (right < heap.length && heap[right] < heap[left]) ? right : left;
    if (heap[cur] <= heap[smaller]) break;
    [heap[cur], heap[smaller]] = [heap[smaller], heap[cur]];
    cur = smaller;
  }
  return min;
}