[JavaScript] 최소 힙 (Min Heap) 구현

1️⃣ 구현 코드

class MinHeap {
  constructor() { this.a = []; }
  size() { return this.a.length; }
  peek() { return this.a[0]; }
  push(x) {
    const a = this.a;
    a.push(x);
    let i = a.length - 1;
    while (i > 0) {
      const p = (i - 1) >> 1;
      if (a[p] <= a[i]) break;
      [a[p], a[i]] = [a[i], a[p]];
      i = p;
    }
  }
  pop() {
    const a = this.a;
    if (!a.length) return undefined;
    const top = a[0], last = a.pop();
    if (a.length) {
      a[0] = last;
      let i = 0;
      while (true) {
        let l = i * 2 + 1, r = i * 2 + 2, m = i;
        if (l < a.length && a[l] < a[m]) m = l;
        if (r < a.length && a[r] < a[m]) m = r;
        if (m === i) break;
        [a[i], a[m]] = [a[m], a[i]];
        i = m;
      }
    }
    return top;
  }
}

2️⃣ 코드 분석

🟢 constructor()

constructor() { this.a = []; }

• 실제 데이터를 저장한 배열 a
• 이진 트리를 배열 인덱스로 표현
  • 부모 인덱스 = (i-1) >> 1
  • 왼쪽 자식 = i*2+1
  • 오른쪽 자식 = i*2+2

🟢 size(), peek()

size() { return this.a.length; }
peek() { return this.a[0]; }

• size() : 힙에 들어 있는 원소 개수
• peek() : 루트(가장 작은 값) 확인

🟢 push(x)

push(x) {
  const a = this.a;
  a.push(x);                   // 1) 맨 끝에 삽입
  let i = a.length - 1;        // 삽입된 원소 위치
  while (i > 0) {              // 2) 부모랑 비교하며 위로 올리기
    const p = (i - 1) >> 1;    // 부모 인덱스
    if (a[p] <= a[i]) break;   // 부모 ≤ 자식이면 종료
    [a[p], a[i]] = [a[i], a[p]]; // 부모 > 자식 → swap
    i = p;                     // 부모 위치로 이동
  }
}

• 새로운 원소를 배열 끝에 넣음
• 부모보다 작으면 위로 올리기 (bubble up)

🟢 pop()

pop() {
  const a = this.a;
  if (!a.length) return undefined; // 빈 힙이면 undefined
  const top = a[0], last = a.pop(); // 1) 루트 꺼내고, 마지막 원소 추출
  if (a.length) {
    a[0] = last;   // 2) 루트 자리에 마지막 원소 넣기
    let i = 0;
    while (true) { // 3) 자식과 비교하며 내려가기 (bubble down)
      let l = i * 2 + 1, r = i * 2 + 2, m = i;
      if (l < a.length && a[l] < a[m]) m = l; // 왼쪽 자식이 더 작으면 후보
      if (r < a.length && a[r] < a[m]) m = r; // 오른쪽 자식이 더 작으면 후보
      if (m === i) break; // 더 이상 작아질 곳이 없음
      [a[i], a[m]] = [a[m], a[i]]; // swap
      i = m;
    }
  }
  return top; // 원래 루트(최솟값) 반환
}

• 루트 제거 후 마지막 원소를 위로 올림
• 자식 중 더 작은 쪽과 교환하며 내려감

3️⃣ 사용 예시

const h = new MinHeap();
h.push(5);
h.push(3);
h.push(8);
h.push(1);

console.log(h.peek()); // 1 (최솟값)
console.log(h.pop());  // 1
console.log(h.pop());  // 3
console.log(h.pop());  // 5
console.log(h.pop());  // 8