JavaScript 최소 힙 구현: 우선순위 큐의 push·pop과 비교 함수

여기부터는 필요한 기능을 골라 읽는 참고 영역입니다. 새로운 파일로 전체 코드를 실행할 때는 아래 Node.js 실행 안내를 따르세요. 앞쪽의 작은 브라우저 실습과 전체 파일을 한 콘솔에 이어 붙이지 마세요. 기능별 입력 조건과 반환 형식은 아래 설명을 기준으로 합니다.

가장 작은 항목만 필요할 때 전체 정렬을 유지해야 할까요

우선순위 큐는 먼저 넣은 항목이 아니라 우선순위가 가장 높은 항목을 먼저 꺼냅니다. 여기서는 비교 값이 작은 항목을 우선하는 최소 힙을 구현합니다. 작업이 계속 들어오는 동안 다음 작업 하나만 선택한다면 매번 전체 배열을 정렬하는 것보다 갱신 범위를 좁힐 수 있습니다.

힙은 배열 전체를 정렬해 두지 않습니다. 부모가 자식보다 우선한다는 지역 조건만 유지하면 루트가 전체 최솟값이라는 결론을 얻습니다. 따라서 data[1]과 data[2]의 대소 순서나 형제 간 순서를 가정하면 안 됩니다. 임의 값 찾기와 범위 검색은 BST처럼 빠르지 않습니다.

완전 이진 트리를 배열 인덱스로 표현합니다

0번을 루트로 두면 i의 부모는 floor((i-1)/2), 왼쪽 자식은 2i+1, 오른쪽 자식은 2i+2입니다. 배열 마지막에만 추가·삭제하여 중간 빈자리가 없는 완전 이진 트리 모양을 유지합니다. 이 모양 덕분에 루트에서 마지막 층까지의 이동은 O(log n)단계에 그칩니다.

유일하게 순서를 정하는 것은 compare(a,b)입니다. 음수이면 a가 앞, 0이면 동률, 양수이면 b가 앞입니다. 모든 저장 값에 대해 일관된 순서를 만들고 NaN이 아닌 유한한 수를 반환해야 합니다. 기본 비교 함수 a-b는 유한한 숫자용이며 이 글의 예시는 작은 정수만 사용합니다.

compare가 외부 상태에 따라 바뀌거나 저장한 객체의 priority를 나중에 수정하면 기존 부모-자식 조건이 깨질 수 있습니다. 코드가 모든 비교법의 수학적 성질을 검사하지는 않습니다. 저장 중인 우선순위를 바꾸려면 제거·재삽입이나 인덱스 추적을 갖춘 별도 갱신 API가 필요합니다.

빈 peek/pop은 undefined를 반환하므로 undefined 저장은 금지합니다. push는 값을 추가하며 반환값을 사용하지 않고, size는 현재 항목 수입니다. 동률 항목의 삽입 순서는 일반 힙이 보장하지 않습니다. 안정적인 동률 처리가 필요하면 입력 순번을 비교의 두 번째 기준으로 포함해야 합니다.

전체 코드와 실행

heap.cjs에 아래 전체를 저장한 뒤 Node.js에서 node ./heap.cjs를 실행합니다. CommonJS 한 파일에 구현·export·직접 실행 예제가 모두 있습니다. 내부 배열의 모양이 아니라 pop을 반복한 결과가 정렬 순서인지 확인하는 예제입니다.

'use strict';

class MinHeap {
  constructor(compare = (a, b) => a - b) {
    if (typeof compare !== 'function') throw new TypeError('compare must be a function');
    this.compare = compare;
    this.data = [];
  }

  get size() {
    return this.data.length;
  }

  peek() {
    return this.data[0];
  }

  push(value) {
    if (value === undefined) throw new TypeError('undefined is reserved for an empty heap');
    let hole = this.data.length;
    this.data.push(value);
    while (hole > 0) {
      const parent = Math.floor((hole - 1) / 2);
      if (this.compare(this.data[parent], value) <= 0) break;
      this.data[hole] = this.data[parent];
      hole = parent;
    }
    this.data[hole] = value;
  }

  pop() {
    if (this.data.length === 0) return undefined;
    const minimum = this.data[0];
    const last = this.data.pop();
    if (this.data.length === 0) return minimum;

    let hole = 0;
    while (hole * 2 + 1 < this.data.length) {
      let child = hole * 2 + 1;
      const right = child + 1;
      if (right < this.data.length &&
          this.compare(this.data[right], this.data[child]) < 0) {
        child = right;
      }
      if (this.compare(last, this.data[child]) <= 0) break;
      this.data[hole] = this.data[child];
      hole = child;
    }
    this.data[hole] = last;
    return minimum;
  }
}

module.exports = { MinHeap };

if (require.main === module) {
  const heap = new MinHeap();
  for (const value of [8, 3, 5, 1, 3]) heap.push(value);
  const smallest = heap.peek();
  const sorted = [];
  while (heap.size > 0) sorted.push(heap.pop());
  console.log(JSON.stringify({ smallest, sorted, empty: heap.pop() === undefined }));
}

실행 출력

{"smallest":1,"sorted":[1,3,3,5,8],"empty":true}

push: 새 값 하나만 위로 올라갑니다

새 값을 배열 끝에 놓으면 완전 이진 트리 모양은 유지됩니다. 기존 노드끼리의 순서도 그대로여서 새 값과 조상 사이만 검사하면 됩니다. hole은 새 값이 들어갈 위치를 뜻하며, 부모가 새 값보다 크면 부모를 hole로 내려 보내고 hole을 부모 자리로 올립니다.

이 구현은 매 단계 두 값을 교환하지 않고 새 값을 지역 변수 value에 보관합니다. 마지막 위치가 결정된 뒤 한 번만 value를 씁니다. 이동 중 같은 부모 값이 잠시 두 칸에 보여도 메서드가 끝날 때 hole을 채우면 완전한 힙이 됩니다. 중간 상태를 외부에서 읽지 않는 동기 메서드 계약입니다.

pop: 두 자식 중 작은 쪽을 먼저 선택합니다

최솟값은 루트에 있으므로 먼저 따로 저장합니다. 배열의 마지막 원소를 pop하면 트리 모양이 유지되지만 루트 자리가 비었다고 볼 수 있습니다. 원소가 하나뿐이었다면 마지막 원소가 곧 최솟값이어서 더 복구하지 않고 반환합니다.

빈 루트에 마지막 값을 무조건 넣으면 자식보다 클 수 있습니다. 두 자식 중 작은 쪽을 고르고, 그 자식이 last보다 앞서면 자식을 hole로 올립니다. 큰 자식을 올리면 작은 자식이 부모보다 작아지는 위반이 남으므로 자식 선택 순서가 핵심입니다.

last가 선택한 자식보다 앞서거나 같으면 그 아래로 내려갈 필요가 없습니다. 해당 자식은 자기 자식보다 앞서므로 현재 자리의 last도 모든 아래 값보다 앞섭니다. 자식이 없는 곳까지 내려간 경우에도 hole에 last를 넣으면 복구가 끝납니다.

최소 힙은 안정 정렬 자료구조가 아닙니다

동률을 compare=0으로만 표현하면 나중에 들어온 항목이 먼저 나올 수 있습니다. 예를 들어 우선순위가 같은 작업 세 개는 pop할 때 마지막 작업이 루트로 올라가는 과정에서 순서가 바뀔 수 있습니다. 작업의 입력 순번 order를 저장하고 priority 차이 다음 order 차이를 비교하면 원하는 FIFO 동률 계약을 만들 수 있습니다.

모든 데이터를 한꺼번에 받아 전체 정렬 결과만 반환한다면 내장 sort가 더 간단할 수 있습니다. 힙의 장점은 입력과 추출이 섞이거나 상위 K개만 유지하는 상황입니다. 이 구현에는 임의 항목 삭제, decrease-key, 선형 시간 heapify가 없으므로 그런 연산이 필요한 알고리즘에 그대로 있다고 가정하면 안 됩니다.

복잡도와 메모리

표는 compare 한 번과 배열 인덱스 접근을 O(1)로 보는 모델입니다. 비교 함수가 긴 문자열을 비교하면 그 비용을 곱해야 합니다. JavaScript 동적 배열의 저장 공간 확장까지 포함하면 특정 push에서 재할당 비용이 생길 수 있어 “상수 시간 배열 append”는 통상 상환 모델로 해석합니다. 힙의 위아래 이동 자체는 로그 단계로 제한됩니다.

경계 확인과 연습

빈 힙, 한 항목, 같은 우선순위 여러 개, 음수 값, 오른쪽 자식이 더 작은 경우를 확인하세요. 각 child에 대해 compare(parent,child) ≤ 0을 검사하는 불변식 테스트와, 정렬 배열에서 하나씩 꺼내는 독립 기준을 함께 쓰면 눈에 보이지 않는 내부 위반도 잡을 수 있습니다.

함께 연습하고 확인할 자료

Kth Largest Element in a Stream: 스트림에서 K번째 큰 값을 유지하는 외부 연습입니다. 이 글의 모든 작업 출력 문제와는 목표가 다릅니다.

관련 개념 참고: Princeton Algorithms — Priority Queues 공식 자료와 문제 페이지는 2026년 9월 10일 확인했습니다. 외부 문제의 지문·예시를 복제하지 않고 이 글의 예제와 창작 문제를 별도로 구성했습니다.