JavaScript Priority Queue 구현

JavaScript에는 Priority Queue가 없다. 참으로 슬프다.

Priority Queue는 코딩테스트에서 자주 쓰이는 자료 구조이므로 직접 구현해보기로 했다. Priority Queue는 Heap이라는 자료구조를 바탕으로 구현이된다. 그래서 Heap의 구현과 Priority Queue를 따로 클래스를 만들어서 분리를 하는 것이 맞지만, 알고리즘 문제풀이를 위해서만 사용하므로 간단하게 둘을 합쳐서 구현하였다.

Heap은 Binary트리의 일종으로 2가지 특징이 있다. 

1. Root 노드는 가장 작거나 큰 노드가 오도록 저장이 되는 것이다. 이는 Comparator 구현에 따라서 다르며 원하는 값을 Root노드에 위치 시킬 수 있다.

2. 두번째는 Complete Binary Tree라는 것이다. Complete Binary Tree는 쉽게 설명하면 왼쪽부터 노드가 차곡차곡 쌓여진 Tree를 말한다.

아래는 PriorityQueue의 구현 클래스이다.

class PriorityQueue{
    constructor(comp){
        this.heap = [];
        this.comp = comp;
        if(comp == undefined){
            this.comp = (a,b) =>{
                return a - b;
            }
        }
    }
    removeMin(){
        if(this.isEmpty()){
            return null;
        }
        let min = this.heap[0];
        let last = this.heap.pop();
        if(this.size() != 0){
            this.heap[0] = last;
            this.downHeap(0);
        }
        return min;
    }
    downHeap(pos){
        while(this.isInternal(pos)){
            let s = null;

            //왼쪽과 오른쪽 자식중에 작은 것을 s에 넣는다.
            if(!this.hasRight(pos)){
                s = this.left(pos);
            }else if(this.comp(this.heap[this.left(pos)], this.heap[this.right(pos)])<= 0){
                s = this.left(pos);
            }else{
                s = this.right(pos);
            }
            if(this.comp(this.heap[s], this.heap[pos]) < 0){
                this.swap(pos, s);
                pos = s;
            }else{
                break;
            }
        }
    }
    upHeap(pos){
        while(!this.isRoot(pos)){
            let p = this.parent(pos);
            if(this.comp(this.heap[p], this.heap[pos])<= 0){
                break;
            }
            this.swap(p, pos);
            pos = p;
        }
    }
    swap(x, y){
        let tmp = this.heap[x];
        this.heap[x] = this.heap[y];
        this.heap[y] = tmp;
    }
    parent(pos){
        return parseInt((pos - 1)/2);
    }
    left(pos){
        return 2*pos + 1;
    }
    right(pos){
        return 2*pos + 2;
    }
    size(){
        return this.heap.length;
    }
    isInternal(pos){
        return this.hasLeft(pos) ;
    }
    isRoot(pos){
        if(pos == 0) return true;
        return false;
    }
    hasLeft(pos){
        if(this.left(pos) < this.size()){
            return true;
        }
        return false;
    }
    hasRight(pos){
        if(this.right(pos) < this.size()){
            return true;
        }
        return false;
    }
    isEmpty(){
        return this.heap.length == 0;
    }
    insert(value){
        this.heap.push(value);
        this.upHeap(this.size() - 1);
    }
    min(){
        return this.heap[0];
    }
}

 

 

기본적으로 minHeap으로 구성되며, 생성할 때 파라미터로 comp 함수를 넣어주면 maxHeap구성도 가능하다. 

내가 구현한 PriorityQueue class가 제대로 동작하는지 확인하기 위해 백준 1655번 가운데를 말해요를 풀어보았다.

www.acmicpc.net/problem/1655

1655번: 가운데를 말해요

github에 해당 솔루션을 올려 놓았으니, 궁금하면 확인해보시라.

github.com/JH-Ha/Algorithm/blob/master/baekjoon/1655/ans.js

JH-Ha/Algorithm