Heap

• 힙은 우선순위 큐를 구현한다.
• 일종의 완전이진트리다 (삽입과 삭제에 O(logN)의 시간이 소요), 배열도 구현 가능하다
• 최대힙(Max Heap) 또는 최소힙(Min Heap)으로 구분할 수 있고 빠른 시간 안에 최대값 또는 최소값을 찾아낼 수 있다

배열을 이용해 어떻게 힙을 구현할 수 있을까?

배열의 첫번째 값은 비워둔다

const heap = [null];

left child index = parent 2
right child index = parent 2 + 1
parent index = Math.floor(child index / 2)

기본생각

insert

1. push to last
2. switch with parents

delete

1. delete root first, and make last node as root (root 제일 먼저 정렬된거니까)
2. switch new root and children

Destructing Assignment

[a, b] = [b, a]; 

minHeap

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

        getMin() {
            return this.heap[1];
        }

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

        getSize() {
            return this.heap.length - 1;
        }

        insert(value) {
            this.heap.push(value);
            let currIdx = this.heap.length - 1;
            let parentIdx = Math.floor(currIdx / 2);

            while(this.heap[parentIdx] > this.heap[currIdx] && currIdx > 1) {
                // swap
                let temp = this.heap[parentIdx];
                this.heap[parentIdx] = this.heap[currIdx];
                this.heap[currIdx] = temp;
                // 
                [this.heap[parentIdx], this.heap[currIdx]] = [this.heap[currIdx], this.heap[parentIdx]]

                currIdx = parentIdx;
                parentIdx = Math.floor(currIdx / 2);
            }
        }

        delete(value) {
            const min = this.heap[1]; // smallest element is root
            
            // when there are more 2 elements in the array, put the right most at the first root.
            if(this.heap.length <= 2) this.heap = [null];
            else this.heap[1] = this.heap.pop();

            let currIdx = 1;
            let leftIdx = currIdx * 2;
            let rightIdx = currIdx * 2 + 1;

            // if there's no left, right doesn't exist too.
            if(!this.heap[leftIdx]) return min;
            // left && !right
            if(!this.heap[rightIdx]) {
                if(this.heap[currIdx] < this.heap[leftIdx]) {
                    [this.heap[currIdx], this.heap[leftIdx]] = [this.heap[leftIdx], this.heap[currIdx]];
                }
                return min;
            }
            
            // both left, right exist
            while(this.heap[currIdx] < this.heap[leftIdx] || this.heap[currIdx] < this.heap[rightIdx]) {
                const minChildIdx = this.heap[leftIdx] < this.heap[rightIdx] ? leftIdx : rightIdx;
                [this.heap[currIdx], this.heap[minChildIdx]] = [this.heap[minChildIdx], this.heap[currIdx]];

                currIdx = minChildIdx;
                leftIdx = currIdx * 2;
                rigthIdx = curridx * 2 + 1;
            }
        }
    }