우선순위 큐 (Priority Queue)과 힙(Heap)

우선순위 큐(Priority Queue)

우선순위 큐는 먼저 들어오는 데이터가 아닌, 우선순위가 높은 데이터가 먼저 나가는 형태의 자료구조이다.
일반적으로 힙(Heap)을 이용해서 구현한다.

힙(Heap)

힙은 완전 이진 트리 형태의 자료구조이다. 여러 개의 값 중 최댓값 또는 최솟값을 효율적으로 찾기 위해 만들어졌다.

NOTE: 우선순위 큐 !== 힙
우선순위 큐를 힙이 아닌 배열, 연결 리스트 등을 이용하여 구현할 수 있다.
배열이나 리스트의 값을 탐색해서 정렬로 구현할 수 있다는 뜻이다.
배열과 연결 리스트는 선형 구조이므로 삽입 또는 삭제 연산의 시간 복잡도는 O(n)이다.
반면 힙은 완전 이진트리이므로, 시간복잡도가 O(logN)이기 때문에 더 효율적이다.

힙의 특징

• 완전 이진 트리로 구성됨
• 부모노드와 서브 트리 간 대소관계가 성립 (반정렬)
• 이진 탐색 트리(BST)와 달리 중복된 값이 허용된다.

최대 힙

부모 노드의 키 값이 자식 노드보다 크거나 같은 완전 이진 트리이다.
부모 노드 값 >= 자식 노드 값

최소 힙

부모 노드의 키 값이 자식 노드보다 작거나 같은 완전 이진 트리이다.
부모 노드 값 <= 자식 노드 값

최소 힙 저장 (in)

힙에 새로운 노드가 들어온다.
1. 트리의 맨 뒤의 리프 노드에 저장한다.
2. 부모 노드와 값을 비교한다.
3. 새로운 노드가 부모 노드보다 작다면, 위치를 교체한다.
4. 더 이상 교체할 필요가 없을 때 까지 2, 3번을 반복한다.

최악의 경우 트리의 높이가 연산의 횟수가 되기 때문에, 시간 복잡도는 O(logN)이다.

최소 힙 삭제 (out)

힙에서 가장 우선순위가 높은 데이터(루트)를 꺼낸다.
1. 비어있는 루트에 트리의 마지막 노드를 루트 노드로 옮긴다.
2. 루트의 왼쪽, 오른쪽 자식 노드와 비교 후 값이 작은 노드와 값을 비교한다.
3. 자식 노드의 값이 더 작다면, 위치를 교체한다.
4. 더 이상 교체할 필요가 없을 때 까지, 2, 3번을 반복한다.

최악의 경우 트리의 높이가 연산의 횟수가 되기 때문에, 시간 복잡도는 O(logN)이다.

2, 3번 과정을 Heapify라고 한다.

힙은 보통 배열로 구현한다.

힙의 부모와 자식 간 다음과 같은 관계가 성립한다.
노드의 index는 1부터 시작이다.

왼쪽 자식의 index = 부모의 index 2
오른쪽 자식의 index = 부모의 index 2 + 1
부모의 index = Math.floor((자식의 index) / 2)

자바스크립트에서는 당연하게도 기본적으로 힙을 제공해주지 않는다. 따라서 직접 구현해야 한다.

아래는 자체적으로 구현한 최소힙이다.

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

    size(){
        return this.heap.length - 1
    }

    #swap(idx1, idx2){
        [this.heap[idx1], this.heap[idx2]] = [this.heap[idx2], this.heap[idx1]]
    }
    heappush(value){
        this.heap.push(value);
        if(this.size() === 1){
            return;
        }

        let curIdx = this.size();
        let parentIdx = Math.floor(curIdx / 2)

        while(this.heap[parentIdx] > this.heap[curIdx]){
            this.#swap(curIdx, parentIdx);
            curIdx = parentIdx;
            parentIdx = Math.floor(curIdx / 2)
        }
    }
    heappop(){
        if(this.size() === 0) return 0;
        if(this.size() === 1) return this.heap.pop();

        this.#swap(1, this.heap.length - 1);
        const returnValue = this.heap.pop();

        let curIdx = 1;
        let leftIdx = curIdx * 2;
        let rightIdx = curIdx * 2 + 1;

        while ((this.heap[leftIdx] && this.heap[curIdx] > this.heap[leftIdx] )|| (this.heap[rightIdx] && this.heap[curIdx] > this.heap[rightIdx])){
            if(!this.heap[rightIdx]){
                this.#swap(curIdx, leftIdx);
                curIdx = leftIdx;
            }else if(this.heap[rightIdx] > this.heap[leftIdx]){
                this.#swap(curIdx, leftIdx);
                curIdx = leftIdx;
            }else{
                this.#swap(curIdx, rightIdx);
                curIdx = rightIdx;
            }
             leftIdx = curIdx * 2;
             rightIdx = curIdx * 2 + 1;
        }
        return returnValue;
    }
}