이진 힙(Binary Heaps)과 최대힙, 최소힙

이진 힙은 트리의 일종이다.

이진 힙은 이진 탐색 트리와 같이 두 개의 자식을 가진다.

두 자식이 부모보다 작은 경우, 즉 루트가 최대 크기가 되는 힙이 최대 힙이다.

자식들이 부모보다 큰 경우 최소 힙이며 이 경우, 루트가 최소값이 되는 최소힙이다.

이진 힙은 이진 탐색트리와는 다르게 두 자식을 나누는 기준이 없다. 좌우로 나누는 기준은 없다는 것이다. 그저 부모보다 크거나 작기만 하면 된다.

 

특정 인덱스를 가진 노드의 자식 노드의 인덱스를 확인하려면 아래와 같은 식을 따르면 된다.

• 왼쪽 자식: 2n + 1
• 오른쪽 자식: 2n + 2

 

역으로 자식 노드에서 부모 노드를 찾으려면

• 부모 노드의 인덱스를 사용해 자식 노드의 인덱스를 구하는 방식을 역으로 하면 된다. 즉 2n+1을 역으로 하면 된다.
• (n-1)/2 을 하고 소숫점을 날린다. 자바스크립트를 사용한다면  Math.floor( (index -1) / 2 )

 

이진 힙에 노드를 추가할 때는 먼저 노드를 추가하고 차례로 부모 노드와 비교하여 자리를 변경하는 Bubble up 방식을 사용한다. 

또한 힙에서 최대값 또는 최소값들을 제거하고 반환하는 경우 루트 노드가 반환되는데 이 때 배열의 마지막에 존재하는 노드가 루트 노드로 옮겨지고, 거기서부터 자식들과 크기를 비교하며 자리를 찾는 Sink down 을 수행한다.

 

 

최대힙 구현 예시

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

    insert(element) {
        this.values.push(element);
        this.bubbleUp();
    }

    /*  부모 노드와 값을 비교하는 메서   */
    bubbleUp(){
        let idx = this.values.length -1;    // insert로 추가한 요소(마지막)의 인덱스
        const element = this.values[idx]    // 해당 요소    

        while(idx > 0) {    // 인덱스가 0보다 큰 경우에만 순회
            let parentIdx = Math.floor( (idx - 1) / 2 );    // 부모 노드의 인덱스 계산
            let parent = this.values[parentIdx];    // 부모 노드

            if(element <= parent) break;    // 추가한 요소가 부모보다 작다면 순회문 탈출

            this.values[parentIdx] = element; // 부모 요소 위치에 신규 노드 할당
            this.values[idx] = parent;        // 원래 요소의 위치에 부모 요소 할당 즉 스왑.
            idx = parentIdx                   // 인덱스도 변경.
        }
    }

    /* 최댓값인 루트를 제거하고 반환하는 메서드 */
    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;                     // 자식 자리의 인덱스가 현재 인덱스가 됨.

            // 인덱스가 변경됨에 따라 해당 위치에서 다시 순
        }
    }
}

 

 

최소 힙 구현 예시

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

    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[parentIdx] = element;
            this.values[idx] = parent;
            idx = parentIdx;
        }
    }

    extractMin() {
        const min = this.values[0];
        const end = this.values.pop();
        
        if(this.values.length > 0) {
            this.values[0] = end;
            this.sinkDown();
        }
        
        return min;
    }

    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
                    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;
        }
    }
}