우선순위 큐 (최소 힙) 구현하기

프로그래머스에서 자바스크립트로 코테 문제 풀면서 힙큐를 직접 구현해야 하는 김에 블로그에 정리 함.

힙의 필요 기능 2개 push,pop

힙에서의 각각의 원소들은 배열로 이루어져 있고 최소힙과 최대힙을 구현할 때 값의 기준은

들어가는 배열의 첫번 째 인덱스 값을 비교값으로 구현함

1. 삽입(push)

힙은 트리 형태로 되어 있지만 배열로도 구현 하는게 더 편함.

인덱스로 접근하면 root부터 left right가 존재함.

삽입을 구현할려면 일단 배열 제일 마지막에 현재 삽입값을 넣어준다.

이후 자신의 부모 노드를 비교해가며 부모 노드가 현재의 값보다 작다면 swap해줄것.

이것을 루트까지 반복 ( 작은 값을 만난다면 멈추고 )

push(a) {
        this.heap.push(a);
        if (this.heap.length === 1) return;
        let curIdx = this.heap.length - 1;
        let parentIdx = Math.floor((curIdx - 1) / 2);

        while (
            parentIdx >= 0 &&
            this.heap[parentIdx][0] > this.heap[curIdx][0]
        ) {
            this.swap(curIdx, parentIdx);
            curIdx = parentIdx;
            parentIdx = Math.floor((curIdx - 1) / 2);
        }
}

2. 삭제 (pop)

최소 힙에서 pop을 한다면 루트를 끄집어 내는 거임

루트의 값을 빼버린다면 트리 형태는 깨지게 되니까 이 모양을 유지하기 위해서는 하나의 로직이 필요.

힙에서의 가장 마지막 값을 루트에 넣고 2개의 자식들과 비교해가며 알맞은 자리까지 down 해주면 됨.

이 때, 자식 2개 모두 현재의 부모 값보다 작다면 두 자식 중 더 작은 위치와 교환을 해준다.

pop() {
        if (this.heap.length === 0) {
            console.log('empty');
            return;
        }
        if (this.heap.length === 1) return this.heap.pop();

        const pivot = this.heap[0];
        const last = this.heap.pop();
        const N = this.heap.length;

        this.heap[0] = last;

        let cur = 0;
        let left = 1
        let right = 2
        while (
            (this.heap[left] && this.heap[cur][0] > this.heap[left][0]) ||
            (this.heap[right] && this.heap[cur][0] > this.heap[right][0])
        ) {
            let small = left;
            if (this.heap[right] && this.heap[small][0] > this.heap[right][0]) {
                small = right;
            }
            this.swap(cur, small);
            cur = small;
            left = (cur+1) * 2 ;
            right = (cur+1) * 2 + 1;
            if (cur >= N) {
                break;
            }
        }

        return pivot;
}

 

3. 전체 코드

class Heap {
    constructor() {
        this.heap = [];
    }
    get() {
        return this.heap;
    }
    swap(idx1, idx2) {
        [this.heap[idx1], this.heap[idx2]] = [this.heap[idx2], this.heap[idx1]];
    }

    push(a) {
        this.heap.push(a);
        if (this.heap.length === 1) return;
        let curIdx = this.heap.length - 1;
        let parentIdx = Math.floor((curIdx - 1) / 2);

        while (
            parentIdx >= 0 &&
            this.heap[parentIdx][0] > this.heap[curIdx][0]
        ) {
            this.swap(curIdx, parentIdx);
            curIdx = parentIdx;
            parentIdx = Math.floor((curIdx - 1) / 2);
        }
    }
    pop() {
        if (this.heap.length === 0) {
            console.log('empty');
            return;
        }
        if (this.heap.length === 1) return this.heap.pop();

        const pivot = this.heap[0];
        const last = this.heap.pop();
        const N = this.heap.length;

        this.heap[0] = last;

        let cur = 0;
        let left = 1;
        let right = 2;
        while (
            (this.heap[left] && this.heap[cur][0] > this.heap[left][0]) ||
            (this.heap[right] && this.heap[cur][0] > this.heap[right][0])
        ) {
            let small = left;
            if (this.heap[right] && this.heap[small][0] > this.heap[right][0]) {
                small = right;
            }
            this.swap(cur, small);
            cur = small;
            left = (cur+1) * 2 ;
            right = (cur+1) * 2 + 1;
            if (cur >= N) {
                break;
            }
        }

        return pivot;
    }
}