Heap

Heap이란?

 

우선순위 큐를 위하여 고안된 자료구조이다.

완전 이진 트리의 일종이며 반 정렬 상태이다. 삽입과 삭제의 시간 복잡도가 O(logN)이다.

종류로는 Max Heap과 Min Heap이 있다.

 

아래는 JavaScript버전으로 Heap을 구현하였으며 하나는 Class버전으로 하나는 Array버전으로 작성하였다.

Class버전은 Max Heap, Array버전은 Min Heap이다.

 

(1)Class 버전

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

    swap(a,b){
        [this.heap[a],this.heap[b]] = [this.heap[b],this.heap[a]];
    }

    size(){
        return this.heap.length;
    }

    add(value){
        this.heap.push(value);
        let ind = this.size() - 1;
        let parent = Math.floor((ind-1)/2);
        while(value > this.heap[parent]){
            this.swap(ind,parent);
            ind = parent;
            parent = Math.floor((ind-1)/2);
        }
    }

    del(){
        if(this.size() === 0)
            return -1
        const last = this.size() - 1;
        let ind = 0;
        this.swap(ind,last);
        const temp = this.heap.pop();

        while(ind < last){
            let left = ind * 2 + 1, right = ind * 2 + 2;
            if(left >= last)
                break
            else if(right >= last){
                if(this.heap[left] > this.heap[ind]){
                    this.swap(ind,left);
                    ind = left;
                }
                else
                    break;
            }
            else{
                if(this.heap[left] < this.heap[right]){
                    if(this.heap[right] > this.heap[ind]){
                        this.swap(right,ind);
                        ind = right;
                    }
                    else
                        break;
                }
                else{
                    if(this.heap[left] > this.heap[ind]){
                        this.swap(left,ind);
                        ind = left;
                    }
                    else
                        break;
                }
            }
        }
        return temp;
    }
}

 

(2) Array버전

let minheap = [];

function insert(heap, num){
    heap.push(num);
    let ind = heap.length;
    while(ind>1){
        if(heap[Math.floor(ind/2)-1]>heap[ind-1]){
                const temp = heap[ind-1];
                heap[ind-1] = heap[Math.floor(ind/2)-1];
                heap[Math.floor(ind/2)-1] = temp;
                ind = Math.floor(ind/2);
        }
        else{
            break;
        }
    }
    return heap;
}

function del(heap){
    heap[0] = heap[heap.length-1];
    heap.pop();
    const len = heap.length;
    let ind = 1;
    while(ind*2<=len){
        if(heap[ind-1]>heap[ind*2-1] && (heap[2*ind]===undefined ||heap[ind*2-1] < heap[ind*2])){
            const temp = heap[ind*2-1];
            heap[ind*2-1] = heap[ind-1];
            heap[ind-1] = temp;
            ind = ind*2
        }
        else if(heap[ind-1]>heap[ind*2]){
            const temp = heap[ind*2];
            heap[ind*2] = heap[ind-1];
            heap[ind-1] = temp;
            ind = ind*2+1
        }
        else
            break;
    }
    return heap
}

 

 

---

추가적으로 Tree버전으로 Min Heap을 작성하였습니다.

class Node{
    constructor(value){
        this.left = null;
        this.right = null;
        this.parent = null;
        this.value = value;
    }
}

class MinHeap{
    #root;
    #length;

    constructor(){
        this.#root = null;
        this.#length = 0;
    }

    get root(){
        return this.#root;
    }

    get length(){
        return this.#length;
    }

    get top(){
        return this.root.value;
    }

    static from(node){
        if(!(node instanceof Node)){
            throw Error(`${node} is not Node Type.`);
        }
        const minHeap = new MinHeap();
        minHeap.#root = node;
        minHeap.#length++;
        return minHeap;
    }

    /**
     * 
     * @param {Node} parentNode 
     * @param {Node} childNode 
     */
    #swapValue(parentNode, childNode){
        const value = childNode.value;
        childNode.value = parentNode.value;
        parentNode.value = value;
    }

    add(value){
        if(this.length === 0){
            const newNode = new Node(value);
            this.#root = newNode;
        }
        else{
            const newNode = new Node(value);
            const len = (this.length + 1).toString(2);

            let current = this.root;

            for(let i = 1; i < len.length - 1; i++){
                current = (len[i] === '0' ? current.left : current.right);
            }

            len[len.length - 1] === '0' ? current.left = newNode : current.right = newNode;
            newNode.parent = current;
            current = newNode;

            let parent = current.parent;

            while(current.parent !== null && current.value < parent.value){
                this.#swapValue(parent, current);
                current = parent;
                parent = current.parent;
            }
        }
        this.#length++;
    }

    remove(){
        if(this.root === null){
            throw Error('Heap is empty.');
        }
        const value = this.root.value;
        const len = (this.length).toString(2);

        let current = this.root;

        for(let i = 1; i < len.length; i++){
            current = (len[i] === '0' ? current.left : current.right);
        }

        this.#root.value = current.value;

        if(current !== this.root){
            if(len[len.length - 1] === '0'){
                current.parent.left = null;
            }
            else{
                current.parent.right = null;
            }
        }
        this.#length--;

        current = this.root;

        while(current.left || current.right){
            if(current.left && current.right){
                if(current.left.value > current.right.value){
                    if(current.value > current.right.value){
                        this.#swapValue(current, current.right);
                        current = current.right;
                    }
                    else{
                        break;
                    }
                }
                else{
                    if(current.value > current.left.value){
                        this.#swapValue(current, current.left);
                        current = current.left;
                    }
                    else{
                        break;
                    }
                }
            }
            else{
                if(current.value > current.left.value){
                    this.#swapValue(current, current.left);
                    current = current.left;
                }
                else{
                    break;
                }
            }
        }
        return value;
    }
}

 

---

속도를 측정해보니 Array버전으로 작성된 코드가 가장 빠르게 동작했습니다...