TIL5. 자바스크립트로 Heap(힙) 구현하기

imloopy·2022년 3월 25일

Today I Learned

목록 보기

5/56

Today I Learned

그 동안 파이썬으로 알고리즘을 공부해온 탓에, "이 때는 이런 자료구조를 사용하면 좋겠다." 라고 생각은 했었으나, 정작 어떤 원리로 동작하는지에 대해서는 잘 이해하지 못하고 사용했다. 여러 자료구조중, 그래도 힙 자료구조가 구현하기 까다로운 편이라고 생각하여 한번 정리해보았다.

Heap(힙)이란?

힙은 우선순위 큐 중 한 종류로, 루트 노드가 우선순위가 가장 높은 값을 갖고, 그 다음 레벨은 다음으로 우선순위가 높은 상태로, 반 정렬(느슨한 정렬)상태를 가진다.
최댓값과 최솟값을 O(log(N))의 시간복잡도로 구할 수 있어 많은 양의 자료에서 원
하는 값을 찾을 때 매우 유리하다.
또, 완전 이진 트리 구조를 갖기 때문에 배열로 구현할 수 있다는 장점도 있다.

힙의 동작 과정과 구현하기

힙은 큐와 달리 어떤 정형화된 구현 방식이 존재하지 않는다. 클래스를 사용하여 구현하는 것이 일반적이다.

interface HeapInterface {
  heap: Array<number | null>;
}

class Heap implements HeapInterface {
  heap: Array<number | null>;
  constructor() {
    this.heap = [null];
  }
  
  // ...
}

편의상 첫 번째 칸을 비워두면 자식 인덱스를 구하는 것이 편해지지만, 타입을 철저하게 체크하는 타입스크립트 특성상, 철저한 type guard를 진행해주지 않으면 엄청난 lintError를 내뿜을 것이다. 예를 들면 이렇게 말이다.

  // ...
   heappush(value: number) {
    this.heap.push(value);
    let currentIndex = this.heap.length - 1;
    let parentIndex = Math.floor(currentIndex / 2);
    
    // null type이 아님을 증명하기 위해 as number를 사용했으나, 이는 좋은 방법이 아니다..
    while (parentIndex) {
      if (
        (this.heap[currentIndex] as number) < (this.heap[parentIndex] as number) 
      ) {
        // ...
      }
      break;
    }
  }

여러 자료구조가 잘 구현되어 있는 파이썬을 잘 써왔기 때문에, 파이썬 라이브러리를 까서 최대한 파이썬스럽게 구현해보기로 했다.

힙은 크게 두 가지 메소드로 분류할 수 있다. 힙 정렬을 위해서 heapify() 메소드를 구현할 수 있지만, 이번엔 스킵하겠다.

heappush()

heappop()

힙에 값을 삽입하기 (heappush)

1. 힙 배열의 가장 마지막에 요소를 삽입한다.
2. 삽입한 노드의 부모 노드를 비교하여 자식 노드의 우선순위가 더 크다면, 위치를 교환한다.

// ...
function heappush(heap: Array<number>, value: number) {
  heap.push(value);
  _shiftdown(heap, 0, heap.length - 1);
}

파이썬 코드를 살펴보니, push 함수 내부에 인덱스를 shift하는 함수가 따로 구현되어 있음을 알 수 있었다.
_shiftdown함수는 현재 인덱스의 값과 상위 노드의 값을 비교하여 우선순위가 더 크다면 부모 노드와 스왑하는 함수이다.

// ...
function _shiftdown(heap: Array<number>, startpos: number, pos: number) {
  const newItem = heap[pos];
  while (startpos < pos) {
    let parentpos = (pos - 1) >> 1;
    let parent = heap[parentpos];
    if (newItem < parent) {
      heap[pos] = parent;
      pos = parentpos;
      continue
    }
    break
  }
  heap[pos] = newItem;
}

처음 보면 잘 이해가 안되는 코드였다. 이렇게 깔끔하게 짜기 위해서는 부단한 노력과 꾸준한 코드리뷰 과정이 필요함을 다시 한번 깨닫는 순간이다.
1. 방금 추가한 아이템을 newItem 변수에 저장한다.
2. parentpos로 거슬러 올라가면서 newItem과 parent를 대소비교한다.
3. parent보다 newItem이 작다면, 현재 heap[pos] 위치를 parent로 치환한다.

힙에서 요소를 제거하기(heappop)

1. heap배열의 가장 첫번째 노드를 반환한다.
2. heap 배열의 가장 마지막 노드를 root노드에 삽입한다.
3. root 노드와 자식 노드를 비교하여 우선순위에 따라 값을 치환한다.

function heappop(heap: Array<number>) {
  const lastelt = heap.pop(); // type: number | undefined
  
  // lastelt가 undefined거나 heap이 비어있다면 lastelt는 root노드가 되므로 더 진행할 필요가 없다
  if (heap.length && lastelt) {
    const ret = heap[0];
    heap[0] = lastelt;
    _shiftup(heap, 0);
    return ret;
  }
  return lastelt;
}

heappush() 함수와 비슷하게, 파이썬 라이브러리는 _shiftup()함수에서 스왑 과정을 위임하고 있었다. "다시 한번 깔끔한 코드는 이런것이구나" 라는 것을 느꼈다.

function _shiftup(heap: Array<number>, pos: number) {
  let startpos = pos;
  let endpos = heap.length;
  let childpos = startpos * 2 + 1;
  const newItem = heap[pos];
  while (pos < endpos) {
    let rightpos = childpos + 1;
    
    // 자식간 우선순위를 비교하여 더 낮은 값과 치환해야 한다.
    if (rightpos < endpos && !(heap[childpos] < heap[rightpos])) {
      childpos = rightpos;
    }
    
    // 이미 다음 레벨 우선순위가 차우선순위이므로 root를 끝까지 탐색하여 재배치
    heap[pos] = heap[childpos];
    pos = childpos;
    childpos = childpos * 2 + 1;
  }
  heap[pos] = newItem;
  
  
  /**
   * while 문에서는 두 자식 노드간 대소만 비교하였으므로
   * shiftdown 함수를 통해 다시 우선순위에 맞게 재정렬
   */
  _shiftdown(heap, startpos, pos);
}

shiftup() 또한 shiftdown()과 마찬가지로 pos에 있는 값을 아래로 내려보낸다. 다만, shiftup()의 주 목적은 왼쪽 자식과 오른쪽 자식의 값을 비교하여 우선순위를 결정하는 역할이 더욱 크다. 실제로 기존 root값과 child값을 비교하는 로직은 shiftup()에 없다. 가장 하위 레벨로 내려보낸후, _shiftdown() 함수를 통해 적절한 위치를 찾는다. 시간복잡도 측면에서 손해일 수 있으나, 깔끔하게 코드를 작성할 수 있어서 이런 구조를 선택한 것 같다.(뇌피셜이다)

마치며

파이썬의 라이브러리를 뜯어보았더니, 클래스를 구현하지 않고도 함수만을 이용해 힙을 구현할 수 있었다. 실제로 heapq 라이브러리를 사용만 해 봤지 뜯어보고 구현한 경험은 처음이라 함수 작성하는 시야를 넓힐 수 있었다. 이러한 리뷰 과정을 통해 앞으로 더 깔끔한 코드를 작성하는 연습을 해 나아가야겠다.