-우선 순위가 높은 요소가 먼저 나가게 된다.
-루트 노드가 가장 큰 값이 되는 최대 힙과 루트 노드가 가장 작은 값이 되는 최소힙이 있다.

-요소가 추가될 때는 트리의 가장 마지막 정점에 위치에 추가된다.
-추가 후, 부모 정점보다 우선순위가 높으면 부모 정점과 위치를 서로 바꾼다.
-계속 반복하면 결국 가장 우선순위가 높은 노드가 루트 노드에 위치하게 된다.
-완전 이진 트리의 높이는 log n이기에 힙의 요소 추가 알고리즘은 O(log n)의 시간 복잡도를 가지게 된다.

-요소 제거는 루트 노드만 가능하다.
-루트 노드가 제거되면 가장 마지막 정점의 노드가 루트로 이동한다.
-루트 노드와 자식 노드의 우선 순위를 비교해 더 우선 순위가 높은 노드를 위로 올린다.
-부모 노드보다 두 자식 노드의 우선 순위가 더 낮을 때까지 반복
-완전 이진 트리의 높이는 log n이기에 힙의 요소 제거 알고리즘은 O(log n)의 시간 복잡도를 가지게 된다.

class MaxHeap {
  constructor() {
    this.heap = [null];
  }

  push(value) { // 새 요소를 마지막 위치에 추가하고 부모와 계속 비교하며 순서를 바꿈
    this.heap.push(value);
    let currentIndex = this.heap.length - 1;
    let parentIndex = Math.floor(currentIndex / 2);

    while (parentIndex !== 0 && this.heap[parentIndex] < value) { // 부모가 더 우선 순위가 낮거나 루트 노드가 아닐 때까지 계속 루프를 돌아~
      const temp = this.heap[parentIndex]; 
      this.heap[parentIndex] = value; // 부모와 자리를 바꿈
      this.heap[currentIndex] = temp;

      currentIndex = parentIndex;
      parentIndex = Math.floor(currentIndex / 2); // 인덱스 재설정
    }
  }

  pop() {
    if (this.heap.length === 2) return this.heap.pop(); // 루트 노드만 남은 경우

    const returnValue = this.heap[1]; // 루투 노드를 반환하기 위해 임시로 저장
    this.heap[1] = this.heap.pop(); // 루트 노드를 가장 마지막 노드로 대체

    let currentIndex = 1;
    let leftIndex = 2;
    let rightIndex = 3;
    while (
      this.heap[currentIndex] < this.heap[leftIndex] ||
      this.heap[currentIndex] < this.heap[rightIndex]
    ) {
      if (this.heap[leftIndex] < this.heap[rightIndex]) {
        const temp = this.heap[currentIndex];
        this.heap[currentIndex] = this.heap[rightIndex];
        this.heap[rightIndex] = temp;
        currentIndex = rightIndex;
      } else {
        const temp = this.heap[currentIndex];
        this.heap[currentIndex] = this.heap[leftIndex];
        this.heap[leftIndex] = temp;
        currentIndex = leftIndex;
      }
      leftIndex = currentIndex * 2;
      rightIndex = currentIndex * 2 + 1;
    }ㄴ

    return returnValue;
  }
}