MaxHeap 구현체

max_heap.js

class MaxHeap {
  constructor (maxLevel = 1) {
    this.nodes = [];
  }

  // phase2
  insert (value) {
    this.nodes.push(value);
    this.bubbleUp();
  }

  bubbleUp (index = this.nodes.length - 1) {
    if (index < 1) {
      return;
    }

    const currentNode = this.nodes[index];
    const parentIndex = Math.floor((index - 1) / 2);
    const parentNode = this.nodes[parentIndex];

    if (parentNode >= currentNode) {
      return;
    }

    this.nodes[index] = parentNode;
    this.nodes[parentIndex] = currentNode;
    index = parentIndex;
    this.bubbleUp(index);
  }

  extract () {
    const max = this.nodes[0];
    this.nodes[0] = this.nodes.pop();
    this.trickleDown();

    return max;
  }

  trickleDown (index = 0) {
    const leftChildIndex = 2 * index + 1;
    const rightChildIndex = 2 * index + 2;
    const length = this.nodes.length;

    let largest = index;
    
    if (leftChildIndex <= length && this.nodes[leftChildIndex] > this.nodes[largest]) {
      largest = leftChildIndex;
    }
    if (rightChildIndex <= length && this.nodes[rightChildIndex] > this.nodes[largest]) {
      largest = rightChildIndex;
    }

    if (largest !== index) {
      [this.nodes[largest], this.nodes[index]] = [this.nodes[index], this.nodes[largest]];
      this.trickleDown(largest);
    }
  }
}

const heap = new MaxHeap();
heap.insert(1);
heap.insert(3);
heap.insert(23);
heap.insert(2);
heap.insert(10);
heap.insert(32);
heap.insert(9);

const length = heap.nodes.length;
console.log(length);
for (let i = 0; i < length; i++) {
  console.log('MAX_VALUE = ', heap.extract());
  console.log('HEAP = ', heap.nodes);
}