기술 블로그

js heapq 본문

알고리즘

js heapq

jaegwan 2023. 11. 14. 15:44
반응형
class Heap {
    constructor() {
        this.heap = [null]; //0인덱스비워두기
    }
    size() {
        return this.heap.length;
    }
    swap(i, j) {
        [this.heap[i], this.heap[j]] = [this.heap[j], this.heap[i]];
    }
    heappush(value) {
        this.heap.push(value);
        let curIdx = this.heap.length - 1; // 현 노드 (위 value가 들어간 값)
        let parIdx = (curIdx / 2) >> 0; // 부모노드
        while (curIdx > 1 && this.heap[curIdx] < this.heap[parIdx]) {
            //현 노드가 루트노드가 아니며, 동시에 부모가 더 값이 크면
            this.swap(curIdx, parIdx); // 해당 값들 스왑
            curIdx = parIdx; // 이제 위로 올라간게 현 노드
            parIdx = (curIdx / 2) >> 0;
        }
    }
    heappop() {
        const min = this.heap[1]; //최솟값
        if (this.heap.length <= 2) {
            // 1개 이하 값만 남았다면
            this.heap = [null]; //비우다/
        } else {
            //아니라면
            this.heap[1] = this.heap.pop(); // 제일마지막 원소를 1번쨰 원소로
        }

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

        if (!this.heap[leftIdx]) {
            // 루트의 자식이 없으면
            return min;
        }
        if (!this.heap[rightIdx]) {
            if (this.heap[curIdx] > this.heap[leftIdx]) {
                // 좌측 자식만 있다면
                //자식이 더 작으면
                this.swap(curIdx, leftIdx);
            }
            return min;
        }

        //이제 자식이 둘다 있는 경우 그리고 그 자식중 하나 이상이 부모보다 작은경우
        while (
            this.heap[leftIdx] < this.heap[curIdx] ||
            this.heap[rightIdx] < this.heap[curIdx]
        ) {
            const minIdx = //더 작은 인덱스를 구하고
                this.heap[leftIdx] > this.heap[rightIdx] ? rightIdx : leftIdx;
            this.swap(minIdx, curIdx);
            curIdx = minIdx;
            leftIdx = curIdx * 2;
            rightIdx = curIdx * 2 + 1;
        }
        return min;
    }
}

const h = new Heap();

h.heappush(10);
console.log(h.heap);
h.heappush(11);
console.log(h.heap);
h.heappush(12);
console.log(h.heap);
h.heappush(13);
console.log(h.heap);
console.log(h.heappop());
console.log(h.heap);
h.heappop();
console.log(h.heap);
h.heappop();
console.log(h.heap);
h.heappop();
console.log(h.heap);
반응형
Comments