[JS]MaxHeap

class maxHeap{
  constructor(){
    this.heap = [null];
  }
  size() {
    return this.heap.length - 1;
  }
  swap(a,b) {
    [this.heap[a], this.heap[b]] = [this.heap[b], this.heap[a]];
  }
  add(value) {
    this.heap.push(value);
    let cur = this.heap.length - 1; // 제일 나중 노드에 새로 들어온 원소를 추가한다.
    let parent = Math.floor(cur / 2);

    while(cur > 1 && this.heap[parent] < this.heap[cur]) {  // 부모노드의 원소가 더 작으면 현재노드의 원소와 바꿔준다.
      this.swap(cur, parent);
      cur = parent;
      parent = Math.floor(cur / 2);
    }
  }
  pop(){
    const max = this.heap[1]; // max 힙이니까 가장 위에있는 원소가 가장 크다.
    if(this.size() < 2) this.heap = [null]; // 원소가 1개만 남아있을때 pop 하면 아무것도 남지않는다.
    else this.heap[1] = this.heap.pop();  // 가장 아래있던 원소를 가장 위로 올려놓고 정렬해야한다.

    let cur = 1;
    let left = cur * 2;
    let right = cur * 2 + 1;

    // 가장 위로 올린원소를 정렬해야한다.    
    if(!this.heap[left])  return max; // left 자식이 없다는것은 자식이 존재하지 않는다는것을 의미한다.
    if(!this.heap[right]) { // right 자식이 없는경우.
      if(this.heap[cur] < this.heap[left]) {
        this.swap(cur,left);
      }
      return max;
    }
    while (this.heap[cur] < this.heap[left] || this.heap[cur] < this.heap[right]) { // 자식중에 현재 원소보다 큰 값이 없을때 까지 swap해주면서 정렬한다.
      let maxIdx = this.heap[left] < this.heap[right] ? right : left; // 두개의 자식중에 더 큰값을 찾아야한다.
      this.swap(cur, maxIdx);
      cur = maxIdx;
      left = cur * 2;
      right = cur * 2 + 1;
    }
    return max;
  }
}