(1) 히프?

히프(Heap)는 최댓값 및 최솟값을 찾아내는 연산을 하기 위한 완전이진트리를 기본으로 한 자료구조이며 다음과 같은 특징을 가지고 있다.

완전 이진 트리
부모 노드의 키 값이 자식 노드의 키 값보다 크다(최대 히프) or 작다(최소 히프)

(2) 노드 삽입

히프에 노드를 삽입할 땐, 우선 삽입하려는 노드를 완전 이진 트리의 맨 마지막 자리에 추가한 뒤, 부모 노드와 크기를 비교해가면서 대소 관계가 맞지 않으면 노드를 교환하여 히프로 다시 만드는 과정을 거친다.

위의 트리는 최대값 히프 트리다. 이 트리에 99의 값을 가지고 있는 노드를 삽입해보자.

히프의 마지막 자리에 99 노드를 추가한다.

그런데, 최대값 히프인데 부모노드 45가 자식노드 99보다 작다. 이렇게 대소 관계가 올바르지 않은 노드는 자리 교환을 통해 올바른 대소관계를 만들어줘야 다시 히프트리가 된다.

45와 99를 교환하였다. 그러나 또 부모노드 54와 대소관계가 맞지 않기 때문에, 54와 99의 자리를 바꿔줘야한다.

54와 99의 자리를 바꾼 모습이다. 여기서 또 다시 루트노드 81과 대소관계가 맞지 않으므로 자리를 교환해준다.

루트노드 81과 99노드의 자리를 바꾼 모습이다. 모든 노드의 대소 관계가 올바르므로 99노드가 삽입된 뒤 최대값 히프가 다시 완성되었다.

(3) 노드 삭제

히프에서 노드의 삭제는 루트 노드를 삭제하면서 반환한다는 의미이다. 최대값이나 최솟값을 찾아내는 연산을 하기 위해 고안된 트리이기 때문이다. 노드에 노드가 하나도 남지 않을 때 까지 삭제 연산을 반복해 반환된 노드들을 순서대로 늘어놓으면 오름차순 혹은 내림차순으로 정렬된 배열이 된다. 이렇게 정렬하는 것을 히프 정렬이라고 한다.

위의 트리는 히프이다. 이 히프에서 루트 노드를 삭제해보자.

루트노드와 히프의 맨 마지막 자리의 노드 45의 자리를 바꾼다. 이렇게 맨 마지막 자리로 오게 된 루트 노드 99는 삭제되고 반환된다.

삭제하려던 99 노드가 삭제되었으니, 이제 다시 히프를 재구축해야한다. 45 노드의 자식 노드 81과 61 모두 45보다 크기 때문에 대소 관계가 옳지 않다.

이런 경우에는 둘 중 더 큰 노드와 자리를 바꾼다. 즉, 45와 81의 자리를 바꾼다.

81과 45의 자리를 바꾼 모습이다. 45와 자식노드들의 대소 관계를 다시 비교해보자.

왼쪽 자식 노드는 42이므로 대소 관계가 올바르다. 하지만, 오른쪽 자식 노드는 54이므로 자리를 바꿔주어야 한다.

54노드와 45노드의 자리를 바꾼 모습이다.

모든 노드의 대소 관계가 히프의 규칙에 위배되지 않게 재정렬 되었다.

이 일련의 과정이 삭제 연산의 한 싸이클이다.

(4) 구현

class Heap {

    constructor() {
        this.array = [];
        this.size = 0;
    }

    insert(data) {
        let currentIndex = this.size + 1; // 계산의 편의성을 위해 배열의 0번째 인덱스는 사용하지 않는다.
        let parentIndex = Math.floor(currentIndex / 2); // 자식노드 입장에서 부모노드의 인덱스는 자신의 인덱스를 2로 나눈 값.
        this.array[currentIndex] = data; // 배열의 마지막 인덱스에 노드를 삽입한다.

        while (this.array[parentIndex] < this.array[currentIndex]) { // 부모노드와 값을 비교하면서 큰 값이 위로 가도록 정렬한다. (최소힙의 경우 반대)
            this.swap(currentIndex, parentIndex);
            currentIndex = parentIndex;
            parentIndex = Math.floor(currentIndex / 2);
        }

        this.size ++;
    }

    delete() {
        const root = this.array[1];
        const getChildIndex = currentIndex => this.array[currentIndex * 2] > this.array[currentIndex * 2 + 1] ? currentIndex * 2 : currentIndex * 2 + 1;
        if (root) {
            if (this.size > 1) {
                this.swap(1, this.size);
                this.array[this.size] = '';
                let currentIndex = 1;
                let childIndex = getChildIndex(currentIndex);
                while (this.array[currentIndex] < this.array[childIndex]) {
                    this.swap(currentIndex, childIndex);
                    currentIndex = childIndex;
                    childIndex = getChildIndex(currentIndex);
                }
            } else {
                this.array[1] = '';
            }
        }
        this.size --;
        return this.array[1];
    }

    swap(idx1, idx2) {
        const temp1 = this.array[idx1];
        const temp2 = this.array[idx2];
        this.array[idx1] = temp2;
        this.array[idx2] = temp1;
    }

    print() {
        const tree = this.array;
        const level = Math.floor(Math.log2(this.size));
        let text = '';
        for (let t = 1; t < tree.length; t ++) {
            const currentLevel = Math.floor(Math.log2(t));
            const space = (level - currentLevel + 1) * 4;
            if (Math.log2(t) - currentLevel === 0) {
                text += '\n';
            }
            for (let s = 0; s < space; s ++) {
                text += ' ';
            }
            text += `${tree[t]}`;
        }
        console.log(text);
    }

}