[Topic #자료구조 04] Max/Min heap 구현 with JavaScript

// Max Heap
class MaxHeap {
  constructor() {
    this.array = [];
  }
  push(value) {
    this.array.push(value);
    this.#upHeap(this.array.length - 1);
  }
  pop() {
    const result = this.array[0];
    const value = this.array.pop();
    if (this.array.length > 0) {
      this.array[0] = value;
      this.#downHeap(0);
    }
    return result;
  }
  isEmpty() {
    return this.array.length === 0;
  }
  #parentIdx(idx) {
    // return Math.floor((idx + 1) / 2) - 1;
    return Math.floor((idx - 1) / 2);
  }
  #leftChildIdx(idx) {
    return idx * 2 + 1;
  }
  #rightChildIdx(idx) {
    // return this.#leftChildIdx(idx) + 1;
    return idx * 2 + 2;
  }
  #upHeap(currentIdx) {
    let parentIdx = this.#parentIdx(currentIdx);
    while (currentIdx > 0 && this.array[currentIdx] > this.array[parentIdx]) {
      [this.array[currentIdx], this.array[parentIdx]] = [
        this.array[parentIdx],
        this.array[currentIdx],
      ];
      currentIdx = parentIdx;
      parentIdx = this.#parentIdx(currentIdx);
    }
    return;
  }
  #downHeap(currentIdx) {
    let targetChildIdx;
    let leftChildIdx = this.#leftChildIdx(currentIdx);
    let rightChildIdx = this.#rightChildIdx(currentIdx);
    // 자식 노드가 있을 동안만 while문 수행
    while (this.array.length > leftChildIdx) {
      if (
        // left child는 있는데 right child는 없는 경우
        this.array.length <= rightChildIdx ||
        this.array[leftChildIdx] > this.array[rightChildIdx]
      ) {
        targetChildIdx = leftChildIdx;
      } else {
        targetChildIdx = rightChildIdx;
      }
      if (this.array[currentIdx] >= this.array[targetChildIdx]) {
        return;
      }
      [this.array[currentIdx], this.array[targetChildIdx]] = [
        this.array[targetChildIdx],
        this.array[currentIdx],
      ];
      currentIdx = targetChildIdx;
      leftChildIdx = this.#leftChildIdx(currentIdx);
      rightChildIdx = this.#rightChildIdx(currentIdx);
    }
  }
  print() {
    console.log(this.array);
  }
}

// Simple Test Cases
const maxHeap = new MaxHeap();
maxHeap.push(5);
maxHeap.push(10);
maxHeap.push(3);
maxHeap.push(8);
maxHeap.push(13);
maxHeap.push(27);
maxHeap.push(4);

while (!maxHeap.isEmpty()) {
  console.log(maxHeap.pop());
}

 

// Min Heap
class MinHeap {
  constructor() {
    this.array = [];
  }
  push(value) {
    this.array.push(value);
    this.#upHeap(this.array.length - 1);
  }
  pop() {
    if (this.array < 1) return;
    const result = this.array[0];
    const value = this.array.pop();
    if (this.array.length > 0) {
      this.array[0] = value;
      this.#downHeap(0);
    }
    return result;
  }
  isEmpty() {
    return this.array.length === 0;
  }
  print() {
    console.log(this.array);
  }
  #parentIdx(idx) {
    return Math.floor((idx - 1) / 2);
  }
  #leftChildIdx(idx) {
    return 2 * idx + 1;
  }
  #rightChildIdx(idx) {
    return 2 * idx + 2;
  }
  #upHeap(currentIdx) {
    let parentIdx = this.#parentIdx(currentIdx);
    while (currentIdx > 0 && this.array[parentIdx] > this.array[currentIdx]) {
      [this.array[currentIdx], this.array[parentIdx]] = [
        this.array[parentIdx],
        this.array[currentIdx],
      ];
      currentIdx = parentIdx;
      parentIdx = this.#parentIdx(currentIdx);
    }
  }
  #downHeap(currentIdx) {
    let targetChildIdx;
    let leftChildIdx = this.#leftChildIdx(currentIdx);
    let rightChildIdx = this.#rightChildIdx(currentIdx);
    while (this.array.length > leftChildIdx) {
      if (
        this.array.length <= rightChildIdx ||
        this.array[leftChildIdx] < this.array[rightChildIdx]
      ) {
        targetChildIdx = leftChildIdx;
      } else {
        targetChildIdx = rightChildIdx;
      }
      if (this.array[currentIdx] < this.array[targetChildIdx]) {
        return;
      }
      [this.array[currentIdx], this.array[targetChildIdx]] = [
        this.array[targetChildIdx],
        this.array[currentIdx],
      ];
      currentIdx = targetChildIdx;
      leftChildIdx = this.#leftChildIdx(currentIdx);
      rightChildIdx = this.#rightChildIdx(currentIdx);
    }
  }
}

// Simple Test Cases
const minHeap = new MinHeap();
minHeap.push(5);
minHeap.push(10);
minHeap.push(3);
minHeap.push(8);
minHeap.push(13);
minHeap.push(27);
minHeap.push(4);

while (!minHeap.isEmpty()) {
  console.log(minHeap.pop());
}

---

자세한 내용은 추후 업데이트 하겠습니다