Heap

Heap

class MaxHeap {
  constructor() {
    this.heap = [null];
  }
  
  push(value) {
    this.heap.push(value);
    let curIdx = this.heap.length - 1;
    let parentIdx = Math.floor(curIdx / 2)
    
    while(parentIdx !== 0 && this.heap[parentIdx] < value) {
      const tmp = this.heap[parentIdx];
      this.heap[parentIdx] = value;
      this.heap[currentIdx] = tmp;
      
      currentIdx = parentIdx;
      parentIdx = Math.floor(currentIdx / 2);
          }
  }
  
  pop() {
    const returnVal = this.heap[1]; // root의 값을 저장해 둠
    this.heap[1] = this.heap.pop(); // root에 가장 마지막 값 넣음
  
    let currentIdx = 1;
    let leftIdx = 2;
    let rightIdx = 3;
  
    while(
      this.heap[currentIdx] < this.heap[leftIdx] ||
      this.heap[currentIdx] < this.heap[rightIdx]
    ) {
      if(this.heap[leftIdx] < this.heap[rightIdx]) {
        const tmp = this.heap[currentIdx];
        this.heap[currentIdx] = this.heap[rightIdx];
        this.heap[rightIdx] = tmp;
        currentIdx = rightIdx;
      } else {
        const tmp = this.heap[currentIdx];
        this.heap[currentIdx] = this.heap[leftIdx];
        this.heap[leftIdx] = tmp;
        currentIdx = leftIdx;
      }
      leftIdx = currentIdx * 2;
      rightIdx = currentIdx * 2 + 1;
      }
  
    return returnVal;
  }
}