[자료구조] 이진 힙 (Binary Heaps) - javascript

들어가기 전에...

해당 글은 유데미 JavaScript 알고리즘 & 자료구조 마스터클래스 강의를 바탕으로 작성되었으며, 좀 더 효율적이고 간결하게 수정된 부분이 있다.

✅ 이진 힙이란?

이진 트리를 이용해서 만든 자료구조로 완전 이진 트리이고, 가능한 적은 용량을 차지하기 때문에 효율적임

1. 각 노드는 최대 두 개의 자식을 가짐
2. 최대 이진 힙 : 부모의 값이 자식보다 큼
   최소 이진 힙: 자식의 값이 부모보다 큼
3. 형제 사이에는 크기 규칙이 없음
4. 왼쪽부터 오른쪽으로 값을 채워야 함

📌 배열을 이용한 구현

인덱스 규칙

• 왼쪽 자식 = 부모x2 + 1
• 오른쪽 자식 = 부모x2 + 2
• 부모 = Math.floor(자식index-1 / 2)

📝 최대 힙

class MaxBinaryHeap {
    constructor() {
        this.values = [];
    }

    // 삽입
    insert(value) {
        // 값을 맨 끝에 추가 -> (bubbleUp) 부모 값과 비교해서 자리 바꿈 반복
        this.values.push(value);
        if(this.values.length > 1) this.bubbleUp(value);
        return this.values;
    }

    bubbleUp(element) {
        let idx = this.values.length-1; // 넣은 값이 존재하는 인덱스

        while(idx > 0) {
            let parentIdx = Math.floor((idx - 1)/2);
            let parentVal = this.values[parentIdx];

            if(element <= parentVal) break;
            [this.values[parentIdx], this.values[idx]] = [element, parentVal];
            idx = parentIdx;
        }
    }

    // 루트 제거
    extractMax() {
        let root = this.values[0];
        let end = this.values.pop();
        if(this.values.length > 0) {
            // 루트에 맨 끝 값 넣기
            this.values[0] = end;
            // 루트와 자식들 크기 비교하면서 재정렬
            this.sinkDown();
        }
        return root;
    }

    sinkDown() {
        let idx = 0;
        let element = this.values[0];
        let lgth = this.values.length;

        while(true) {
            let leftChildIdx = idx * 2 + 1;
            let rightChildIdx = idx * 2 + 2;
            let leftChild, rightChild;
            let swap = null;

            // 왼쪽자식, 오른쪽자식이 하나는 존재 or 하나 안 존재할 수 있으니 각자 존재 여부 검사해야함
            // 자식이 더 크면 swap으로 변경할 자식 표시
            if(leftChildIdx < lgth) {
                leftChild = this.values[leftChildIdx];
                if(leftChild > element) swap = leftChildIdx;
            }

            if(rightChildIdx < lgth) {
                rightChild = this.values[rightChildIdx];
                if(
                    (swap === null && rightChild > element) || // 왼쪽 안 크고 오른쪽만 큰 경우
                    (swap !== null && rightChild > leftChild) // 왼쪽도 큰데 오른쪽이 왼쪽보다도 큰 경우
                ) swap = rightChildIdx;
            }

            if(swap === null) break; // 루트가 제일 크면 반복문 종료
            [this.values[swap], this.values[idx]] = [element, this.values[swap]]; // 아니라면 자리 바꾸기
            idx = swap; // 바꾼 자리에서 다시 자식들과 비교하기 위해 값 변경
        }
    }
}

📝 우선순위 큐 (최소 힙)

1. 각 요소가 그에 해당하는 우선순위를 가지는 데이터 구조
2. 더 높은 우선순위를 가진 요소가 먼저 처리됨
3. 순서대로 데이터가 들어오지 않으며, 우선순위가 우선인 사람이 먼저 처리됨
4. 추상적인 개념이라 배열 or 리스트로도 만들수 있으나 최소 힙이 가장 효율적임

class Node {
    constructor(val, priority) {
        this.val = val;
        this.priority = priority;
    }
}

class PriorityQueue {
    constructor() {
        this.values = [];
    }

    // 노드 삽입
    enqueue(val, priority) {
        let newNode = new Node(val, priority)
        this.values.push(newNode);

        if(this.values.length > 1) this.bubbleUp(newNode);

        return this.values;
    }

    bubbleUp(element) {
        let idx = this.values.length-1;
        let parentIdx, parentPriority;

        while(idx > 0) {
            parentIdx = Math.floor((idx-1)/2);
            parent = this.values[parentIdx];
            if(parent.priority <= element.priority) break;
            [this.values[parentIdx], this.values[idx]] = [element, parent];
            idx = parentIdx;
        }
    }

    // 루트 삭제 (우선순위 따져서 내보냄)
    dequeue() {
        if(this.values.length === 0) return false;

        let root = this.values[0];
        let end = this.values.pop();
        if(this.values.length > 0) {
            this.values[0] = end;
            this.sinkDown();
        }
        return root;
    }

    sinkDown() {
        let element = this.values[0];
        let priority = element.priority;
        let idx = 0;
        let lgth = this.values.length;

        while(true) {
            let leftChildIdx = idx * 2 + 1;
            let rightChildIdx = idx * 2 + 2;
            let leftChildPry, rightChildPry;
            let swap = null;

            if(leftChildIdx < lgth) {
                leftChildPry = this.values[leftChildIdx].priority;
                if(leftChildPry < priority) swap = leftChildIdx;
            }
            if(rightChildIdx < lgth) {
                rightChildPry = this.values[rightChildIdx].priority;
                if((swap === null && rightChildPry < priority) ||
                   (swap !== null && rightChildPry < leftChildPry)) swap = rightChildIdx;
            }

            if(swap === null) break;
            [this.values[swap], this.values[idx]] = [element, this.values[swap]];
            idx = swap;
        }
    }
}

📌 시간복잡도

• 삽입: O(logN)
  • 맨 끝에 넣고 제자리를 찾으려면 레벨 당 한 번씩만 비교하면 됨
  • 이진트리와 달리 왼쪽에서 오른쪽으로 채워지고, 형제 간에는 순서 규칙이 없음 -> 다음 레벨로 넘어가기 위해서는 한 레벨이 다 채워져야 함 -> 트리가 한 쪽으로 치우치는 최악의 경우 발생하지 않음
• 삭제: O(logN)
• 검색: O(N)
  • 형제 간의 순서 규칙이 없으니 왼쪽, 오른쪽 모두 방문해야하니 다소 느림