[자료구조] JS Heap 구현 ver.2

JS Heap 구현

 

class Heap {
  constructor(comparator = (a, b) => a > b) {
    this.heap = [];
    this.comparator = comparator; // 비교 함수로 MinHeap/MaxHeap 결정
  }

  // 힙의 크기
  size() {
    return this.heap.length;
  }

  // 힙이 비어 있는지 확인
  isEmpty() {
    return this.size() === 0;
  }

  // 힙의 최상위 요소 반환 (삭제하지 않음)
  top() {
    return this.isEmpty() ? null : this.heap[0];
  }

  // 요소 삽입
  push(value) {
    this.heap.push(value);
    let index = this.size() - 1;

    // 부모와 비교하며 위치 조정
    while (index > 0) {
      const parentIndex = Math.floor((index - 1) / 2);
      if (this.comparator(this.heap[index], this.heap[parentIndex])) {
        [this.heap[index], this.heap[parentIndex]] = [
          this.heap[parentIndex],
          this.heap[index],
        ];
        index = parentIndex;
      } else {
        break;
      }
    }
  }

  // 최상위 요소 제거 및 반환
  pop() {
    if (this.isEmpty()) return null;

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

    if (!this.isEmpty()) {
      this.heap[0] = last;
      let index = 0;

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

        if (
          leftChildIndex < this.size() &&
          this.comparator(this.heap[leftChildIndex], this.heap[index])
        ) {
          swapIndex = leftChildIndex;
        }

        if (
          rightChildIndex < this.size() &&
          this.comparator(
            this.heap[rightChildIndex],
            swapIndex !== null ? this.heap[swapIndex] : this.heap[index]
          )
        ) {
          swapIndex = rightChildIndex;
        }

        if (swapIndex === null) break;

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

    return root;
  }

  // 힙 상태를 출력 (디버깅 용도)
  print() {
    console.log(this.heap);
  }
}

// === MaxHeap 예제 ===
const maxHeap = new Heap(); // 기본적으로 MaxHeap
maxHeap.push(10);
maxHeap.push(20);
maxHeap.push(5);
maxHeap.push(30);
console.log("MaxHeap Top:", maxHeap.top()); // 30
console.log("MaxHeap Pop:", maxHeap.pop()); // 30
console.log("MaxHeap Top after Pop:", maxHeap.top()); // 20

// === MinHeap 예제 ===
const minHeap = new Heap((a, b) => a < b); // MinHeap
minHeap.push(10);
minHeap.push(20);
minHeap.push(5);
minHeap.push(30);
console.log("MinHeap Top:", minHeap.top()); // 5
console.log("MinHeap Pop:", minHeap.pop()); // 5
console.log("MinHeap Top after Pop:", minHeap.top()); // 10