[알고리즘] Binary Heaps

이진 힙(Binary Heap) 은 이진트리 형식을 취하는 힙 데이터 구조입니다.
바이너리 힙은 우선순위 대기열을 구현하는 일반적인 방법입니다.

상위 키가 하위 키보다 크거나 같은(≥) 힙을 최대 힙이라고 합니다.
작거나 같은 것을 최소 힙이라고 합니다.

https://en.wikipedia.org/wiki/Binary_heap

Binary heap - Wikipedia

---

위키피디아의 최대 힙에 삽입, 추출 작업하는 코드를 작성해 보자.

---

삽입

heap에 숫자 15를 추가할 때의 pseudo-code

1. 맨 왼쪽 열린 공간에서 힙의 맨 아래 레벨에 요소 15를 추가하십시오.
2. 추가된 요소 15를 부모 8과 비교합니다. 순서가 맞으면 (부모가 더 크면) 중지합니다.
3. 그렇지 않은 경우 요소를 부모 8과 15를 교체하고 이전 단계로 돌아갑니다.
4. 이번엔 15를 루트 11과 비교합니다. 순서가 맞으면 (부모가 더 크면) 중지합니다.
5. 그렇지 않은 경우 요소를 루트 11과 15를 교체하고 이전 단계로 돌아갑니다.
6. 15를 루트 11과 비교해서, 순서가 맞으므로 (부모가 더 크므로) 중지되었습니다.

class MaxBinaryHeap {
    constructor(){
        this.values = [11, 5, 8, 3, 4];
    }
    insert(element){
        this.values.push(element)
        this.bubbleUp()
    }
    bubbleUp(){
        let idx = this.values.length -1;
        const element = this.values[idx];
        while(idx > 0){
            let parentIdx = Math.floor((idx - 1)/2);
            let parent = this.values[parentIdx]
            if(element <= parent) break;
            this.values[idx] = parent;
            this.values[parentIdx] = element;
            idx = parentIdx;
        }
    }
}

let heap = new MaxBinaryHeap();
heap.insert(15);

---

추출

heap 속성을 유지하면서 heap에서 루트를 삭제할 때의 pseudo-code

1. 힙의 루트 11을 마지막 수준의 마지막 요소 4로 바꿉니다.
2. swap의 유무를 기준으로 잡을 변수를 하나 생성합니다. (기본값 null)
3. 왼쪽의 자식요소가 존재할 경우, 새 루트를 비교합니다.
   만약 왼쪽의 자식요소가 새 루트보다 크다면,  swap에 왼쪽 자식요소의 index값을 저장합니다.
4. 오른쪽 자식요소가 존재할 경우, 새 루트를 비교합니다.
   a. swap이 null이고(왼쪽 자식요소가 새 루트보다 작고),
   오른쪽 자식요소가 새 루트보다 크다면, 오른쪽 자식요소의 index값을 저장합니다.
   b. swap이 왼쪽 자식요소의 index값이 저장되어 있지만,
   오른쪽 자식요소가 왼쪽 자식요소보다 크다면 오른쪽 자식요소의 index 값을 저장합니다.
   
5. swap이 null이라면, 오른쪽 또는 왼쪽 자식요소보다 순서가 맞으므로 (새 루트가 제일 크므로) 중지합니다.
6. swap을 통해 오른쪽 또는 왼쪽 자식요소의 index 값을 설정하고,
   그 index값에 루트를 넣고, 루트에 오른쪽 또는 왼쪽 자식요소를 대입합니다.

class MaxBinaryHeap {
    constructor(){
        this.values = [11, 5, 8, 3, 4];
    }
    extractMax(){
        const max = this.values[0];
        const end = this.values.pop();
        if(this.values.length > 0) {
            this.values[0] = end;
            this.sinkDown();
        }
        return max;
    }
    sinkDown(){
        let idx = 0;
        const length = this.values.length;
        const element = this.values[0];
        while(true){
            let leftChildIdx = 2 * idx + 1;
            let rightChildIdx = 2 * idx + 2;
            let leftChild, rightChild;
            let swap = null;

            if(leftChildIdx < length){
               leftChild = this.values[leftChildIdx];
                if(leftChild > element) {
                    swap = leftChildIdx;
                }
            }
            if(rightChildIdx < length){
                rightChild = this.values[rightChildIdx];
                if((swap === null && rightChild > element) || 
                    (swap !== null && rightChild > leftChild)) {
                    swap = rightChildIdx
                }
            }
            if(swap === null)break;
            this.values[idx] = this.values[swap];
            this.values[swap] = element;
            idx = swap;
        }
    }
}

let heap = new MaxBinaryHeap();

swap을 통해서 왼쪽 자식요소와 오른쪽 자식요소를 한 번씩 비교하는 것이 비효율적인 것 같아서 리팩토링을 시도했는데,
일단 조건문을 통해 각 자식요소들이 존재하는지부터 알고 난 후에 idx값을 받아와야해서 더 간결하게 만들 수 있는 코드가 떠오르지 않는다ㅠ 구글링해봐도 비슷하게 구현 된 코드만 나오는 상태.
나중에 문제풀면서 더 좋은 코드를 발견한다면 업데이트 해봐야지.

---

[udemy : JavaScript 알고리즘 & 자료구조 마스터클래스]
https://www.digitalocean.com/community/tutorials/js-binary-heaps