🔎 우선순위 큐

우선순위 큐에 대하여 알아보고 힙 자료구조를 통하여
JS 코드로 어떻게 짜는지에 대하여 알아보자.

---

📌 우선순위 큐란?

• 우선순위가 가장 높은 데이터를 가장 먼저 삭제하는 자료구조
• 우선순위 큐는 데이터를 우선순위에 따라 처리하고 싶을 때 사용한다.

---

📌 구현

1. 배열 및 연결리스트로 구현
   간단히 구현이 가능한 장점이 있지만 데이터를 삭제 및 삽입해야할 경우 모든 인덱스를 탐색하는 과정이 있기 때문에 시간복잡도가 O(N)이 되므로 상대적으로 부족한 성능이 될 수 있다.

2. 힙으로 구현
   상대적으로 구현이 어렵지만 시간 복잡도가 O(logN)이기 때문에 좋은 성능을 보여준다.
   단순히 N개의 데이터를 힙에 넣었다가 모두 꺼내는 작업은 힙 정렬과 동일하며 이 경우엔 O(NlogN)이다.

---

📌 구현 방법에 따른 시간 복잡도

---

📌 힙의 특징

• 완전 이진 트리 자료구조이다.
  완전 이진 트리란 마지막 레벨을 제외하고 모든 레벨이 모두 채워져있으며, 마지막 레벨의 모든 노드는 가능한 왼쪽에 있다.
  즉 루트 노드로부터 시작하여 왼쪽에서 오른쪽 자식 노드 순서대로 데이터가 순차적으로 삽입되는 트리를 의미한다.

• 최소힙
  루트 노드가 가장 작은 값을 가지며 값이 작은 데이터가 우선적으로 제거된다.
  최소 힙은 부모노드가 항상 자식노드보다 값이 작다.

• 최대힙
  루트 노드가 가장 큰 값을 가지며 값이 큰 데이터가 우선적으로 제거된다.
  최대 힙은 부모노드가 항상 자식노드보다 값이 크다.

• 힙의 인덱스 관계
  좌측 자식 노드의 인덱스 : (부모 노드의 인덱스 2 ) + 1
  우측 자식 노드의 인덱스 : (부모 노드의 인덱스 2 ) + 2
  부모 노드의 인덱스 : Math.floor( 자식노드의 인덱스 - 1 / 2 )

---

📌 힙의 구현 ( 최대 힙)

class MaxHeap {
    constructor() {
        this.heap = [null];
    }
    heap_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] = this.heap[currentIndex];
            this.heap[currentIndex] = temp;
            currentIndex = parentIndex;
            parentIndex = Math.floor(currentIndex / 2);
        }
    }
    heap_pop() {
        if (this.heap.length === 2) return this.heap.pop(); // 루트 정점만 남은 경우
        // 위에서 아래로
        let 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]
        ) {
            const temp = this.heap[currentIndex];
            if (this.heap[leftIndex] < this.heap[rightIndex]) {
                this.heap[currentIndex] = this.heap[rightIndex]
                this.heap[rightIndex] = temp;
                currentIndex = rightIndex;
            } else {
                this.heap[currentIndex] = this.heap[leftIndex]
                this.heap[leftIndex] = temp;
                currentIndex = leftIndex;
            }
            leftIndex = currentIndex * 2;
            rightIndex = leftIndex + 1;
        }
        return returnValue;
    }
    heap_return() {
        return this.heap;
    }
}