자바스크립트 Heap [최소힙 구현]

구현

class heapq {
    constructor() {
        this.heap = [];
    };
    size() {
        return this.heap.length;
    };
    swap(left, right) {
        [this.heap[left], this.heap[right]] = [this.heap[right], this.heap[left]];
    };
    heappush(value) {
        this.heap.push(value);
        this.bubbleUp();
    };
    bubbleUp() {
        let son = this.heap.length - 1;
        let parent = Math.floor((son - 1) / 2);
        while (parent >= 0 && this.heap[son] < this.heap[parent]) {
            this.swap(son, parent);
            son = parent;
            parent = Math.floor((son - 1) / 2);
        };
    };
    heappop() {
        if (this.heap.length == 1) {
            return this.heap.pop();
        };
        const value = this.heap[0];
        this.heap[0] = this.heap.pop();
        this.bubbleDown();
        return value;
    };
    bubbleDown() {
        let root = 0;
        let left = 2 * root + 1;
        let right = 2 * root + 2;
        while (
            (left < this.heap.length && this.heap[left] < this.heap[root]) ||
            (right < this.heap.length && this.heap[right] < this.heap[root])
        ) {
            let tmp = left;
            if (right < this.heap.length && this.heap[right] < this.heap[tmp]) {
                tmp = right;
            };
            this.swap(root, tmp);
            root = tmp;
            left = 2 * root + 1;
            right = 2 * root + 2;
        };
    };
};

const minHeap = new heapq();
minHeap.heappush(1);
console.log(minHeap); // heapq { heap: [ 1 ] }
minHeap.heappush(12);
console.log(minHeap); // heapq { heap: [ 1, 12 ] }
minHeap.heappush(51);
console.log(minHeap); // heapq { heap: [ 1, 12, 51 ] }
minHeap.heappush(14);
console.log(minHeap); // heapq { heap: [ 1, 12, 51, 14 ] }
minHeap.heappush(37);
console.log(minHeap); // heapq { heap: [ 1, 12, 51, 14, 37 ] }

console.log(minHeap, minHeap.heappop()) // heapq { heap: [ 12, 14, 51, 37 ] } 1
console.log(minHeap, minHeap.heappop()) // heapq { heap: [ 14, 37, 51 ] } 12
console.log(minHeap, minHeap.heappop()) // heapq { heap: [ 37, 51 ] } 14
console.log(minHeap, minHeap.heappop()) // heapq { heap: [ 51 ] } 37
console.log(minHeap, minHeap.heappop()) // heapq { heap: [] } 51

시간복잡도

구분	삽입 정렬	병합 정렬	퀵 정렬	힙 정렬
max	O(n^2)	O(n log n)	O(n**2)	O(n log n)
avg	O(n^2)	O(n log n)	O(n log n)	O(n log n)
min	O(n)	O(n log n)	O(n log n)	O(n log n)

특징

• 병합정렬은 안정적이지만 힙은 안정적이지 못하다.
• 최대힙 : 부모 노드가 자식 노드 보다 무조건 큰 값
• 최소힙 : 부모 노드가 자식 노드 보다 무조건 작은 값