[Udemy] 이진 힙(Binary heap)과 우선순위 큐(Priority Queue)

정의

이진 힙은 힙의 한 종류이고, 힙(Heap)은 트리 자료구조의 한 종류이다.

 

이진 힙과 이진 검색 트리의 가장 큰 차이점은 이진 힙에 값이 추가될 때 항상 왼쪽먼저 채워진다는 점이다.

 

이진 검색 트리는 부모 노드와 값을 비교하여 작으면 왼쪽, 크면 오른쪽 자식 노드로 채워진다.

 

이진 힙에는 최대 이진 힙, 최소 이진 힙 두 가지로 나뉜다.

 

최대 이진 힙

부모 노드가 자식 노드보다 값이 커야만 한다.

 

최소 이진 힙

부모 노드가 자식 노드보다 값이 작아야만 한다.

 

우선 최대 이진 힙을 구현하여 이진 힙에 대해 알아보고,

최소 이집 힙을 통해 우선순위 큐에 대해 알아보자.

 

 

최대 이진 힙 구현

최대 이진 힙은 부모 노드보다 자식 노드 값이 커야만 한다.

function swap(arr,i,j) {
    [arr[i], arr[j]] = [arr[j], arr[i]]
}

class MaxBinaryHeap {
    constructor() {
        this.values = [];
    }
    
    insert(value) {        
        this.values.push(value)

        // bubbleUp
        while (true) {
            let childIdx = this.values.indexOf(value);
            let parentIdx = Math.floor((childIdx - 1) / 2);
            let parent = this.values[parentIdx];

            if (parent >= value || childIdx <= 0) break;
            swap(this.values, childIdx, parentIdx)
        }
        return this;
    }

    extractMax() {
        let lastElement = this.values.pop();
        if (this.values.length === 0) return this;

        this.values[0] = lastElement;
        this.sinkDown(lastElement);
        
        return this;
    }

    sinkDown(lastElement) {
        let idx = 0
        while (true) {
            let leftIdx = 2 * idx + 1;
            let rightIdx = 2 * idx + 2;
            let leftChild = this.values[leftIdx];
            let rightChild = this.values[rightIdx];
            let swaped = false;

            if (leftChild > rightChild && leftChild > lastElement) {
                swap(this.values,idx, leftIdx);
                idx = leftIdx;
                swaped = true
            } 
            if (rightChild > leftChild && rightChild > lastElement) {
                swap(this.values, idx, rightIdx)
                idx = rightIdx
                swaped = true
            }

            if (!swaped) break;
        }
    }
}

 

최대 이진 힙은 values라는 배열을 사용하여 인덱스를 통해 부모노드와 자식 노드의 관계를 나타낼 수 있다.

 

부모 노드의 인덱스를 n이라고 가정할 때, 아래의 상관관계를 가진다.

왼쪽 자식 노드의 인덱스: 2n + 1

오른쪽 자식 노드의 인덱스: 2n + 2

 

이러한 이유는 이진 힙에 값이 추가될 때 왼쪽 자식 노드부터 채워지는 특징 때문이다.

 

insert 메서드

insert 메서드는 최대 이진 힙에 값을 추가하는 메서드이다.

이 때, 배열의 끝에서부터 값을 추가하며 추가한 값과 부모 값을 비교하여

부모 값이 더 작다면 swap 해준다.

이를 루트 부모까지 반복하는 과정을 bubbleUp이라고 한다.

 

extractMax 메서드

extractMax 메서드는 최대 이진 힙에서 최댓값을 제거하는 메서드이다.

최대 이진 힙에서 최대값은 values 배열의 가장 첫번째 값이므로,

첫번째 값을 제거한 후 가장 작은 값으로 추론되는 마지막 요소를 첫번째 요소 위치로 옮긴다.

부모노드와 자식 노드를 비교하여 최대 이진 합의 특징을 충족시킬 때 까지 swap을 진행한다.

이러한 과정을 sinkDown이라고 한다.

 

sinkDown 시 유의할 점은 자식 노드와 swap 시 자식 노드들 끼리도 비교하여

둘 중 큰 자식 노드와 부모 노드를 교환해야한다는 점이다.

왜냐하면 둘 중 작은 자식 노드와 교환하면 최대 이진 힙 특징을 만족하지 못하기 때문이다.

 

 

우선 순위 큐 구현

우선순위 큐는 말 그대로 우선순위가 먼저인 요소가 먼저 나올 수 있는 자료구조이다.

보통은 우선순위는 숫자가 낮을 수록 우선순위가 높다고 판단하므로

최소 이진 힙을 통해 우선 순위 큐를 구현해보자.

 

function swap(arr,i,j) {
    [arr[i], arr[j]] = [arr[j], arr[i]]
}

class Node {
    constructor(val, priority) {
        this.val = val;
        this.priority = priority;
    }
}

// Using MinBinaryHeap
class PriorityQueue {
    constructor() {
        this.values = []
    }

    enqueue(val,priority) {
        let newNode = new Node(val,priority);

        this.values.push(newNode);

        while (true) {
            let idx = this.values.findIndex(value => value === newNode);
            let parentIdx = Math.floor((idx - 1) / 2);
            let parent = this.values[parentIdx];

            if (parentIdx < 0) break;
            if (parent.priority <= newNode.priority) break;
            swap(this.values,idx,parentIdx)
        }
        return this;
    }

    dequeue() {
        let lastElement = this.values.pop();
        if (this.values.length === 0) return this;

        this.values[0] = lastElement;
        this.sinkDown(lastElement);
        
        return this;
    }

    sinkDown(lastElement) {
        let idx = 0
        while (true) {
            let leftIdx = 2 * idx + 1;
            let rightIdx = 2 * idx + 2;
            let leftChild = this.values[leftIdx];
            let rightChild = this.values[rightIdx];
            let swaped = false;

            if (!leftChild || !rightChild) break;
            if (leftChild.priority < rightChild.priority && leftChild.priority < lastElement.priority) {
                swap(this.values,idx, leftIdx);
                idx = leftIdx;
                swaped = true
            } 
            if (rightChild.priority < leftChild.priority && rightChild.priority < lastElement.priority) {
                swap(this.values, idx, rightIdx)
                idx = rightIdx
                swaped = true
            }

            if (!swaped) break;
        }
    }
}

 

우선 순위 큐도 values 배열만 가지고 있는다.

하지만 최대 이진 힙의 차이점은 값(val), 우선순위(priority)를 가진 Node 객체를 포함한다는 점이다.

 

최소 이진 힙은 부모 노드가 자식 노드보다 작아야만 하므로

최대 이진 힙과 부등호만 변경해주면 된다.

 

추가로 priority 값을 비교해줘야하는데,

parentIdx가 -1인 경우와 leftChild, rightChild가 undefined 일 수 있으니 예외처리를 추가해주었다.

 

 

시간 복잡도

삽입 - O(log n)

제거 - O(log n)

검색 - O(n)

 

만약 16개의 요소가 있을 때, 새로운 요소를 추가 시

최악의 경우이더라도 최대 4번의 비교를 통해서 삽입이 이루어진다.

이는 2^4이므로, 삽입의 시간 복잡도는 O(log n)이다.

 

제거도 마찬가지이다.

단, 검색시에는 모든 요소를 확인 해야한다.

 

 

사용 목적

이진 힙을 사용하는 목적은 정렬과 우선순위 큐 같은 자료구조를 실행하기 위해 사용한다.

특히 검색 보다는 데이터의 삽입 및 제거 시 유용한 자료구조이다.

 

 

참조

Udemy - Js 알고리즘 & 자료구조 강의