힙(Heap) 구현해보기

힙이란?

최댓값 혹은 최솟값을 빠르게 찾기 위해 완전이진트리 형태로 연산을 수행하는 자료구조

⇒ 완전이진트리: 마지막 레벨 전까지 노드가 가득 차있고, 마지막 레벨에서는 왼쪽부터 순차적으로 노드가 채워져있는 트리를 의미한다.

힙 대표 속성

• 정렬: 각 노드의 값은 자식 노드가 가진 값보다 작거나 혹은 큰 순서대로 정렬
• 형태: 트리의 형태는 완전이진트리 모양

힙 종류

• 최소 힙: 부모 노드의 값이 자식 노드의 값보다, 작거나 같은 완전이진트리
• 최대 힙: 부모 노드의 값이 자식 노드의 값보다, 크거나 같은 완전이진트리

힙 구현

• 완전이진트리 성질을 만족하기 때문에 1차원 배열로 표현 가능
• 인덱스 기준 ⇒ 현재 노드: N, 부모 노드: (N - 1) / 2, 왼쪽 자식 노드: (N X 2) + 1, 오른쪽 자식 노드: (N X 2) + 2
  즉, 가장 아래 3을 기준으로 하면 부모 노드는 (3 - 1) / 2 = 1, 1을 기준으로 했을 때 오른쪽 자식 노드는 1 * 2 + 2 = 4가 된다.
  출처: https://jinyisland.kr/
  

구현 메서드

• 노드 위치 계산: Heap.parentIndex(), Heap,leftChildIndex(), Heap.rightChildIndex()
• 노드 값 확인: Heap.parent(), Heap.leftChild(), Heap.rightChild()
• 노드 추가/삭제: Heap.insert(), Heap.bubbleUp(), Heap.extract(), Heap.bubbleDown(

노드 추가/삭제를 제외한 메서드는 동일하다.

class Heap {
    constructor () {
        this.items = [];
    }

    swap (index1, index2) {
        let temp = this.items[index1];
        this.items[index1] = this.items[index2];
        this.items[index2] = temp;
    }

    parentIndex (index) {
        return Math.floor((index - 1) / 2);
    }

    leftChildIndex (index) {
        return index * 2 + 1;
    }

    rightChildIndex (index) {
        return index * 2 + 2;
    }

    parent (index) {
        return this.items[this.parentIndex(index)];
    }

    leftChild (index) {
        return this.items[this.leftChildIndex(index)];
    }

    rightChild (index) {
        return this.items[this.rightChildIndex(index)];
    }

    peek () {
        return this.items[0];
    }

    size () {
        return this.items.length;
    }
}

최대 힙

1. 신규 노드 추가(insert()) 및 신규 노드 위치 변경 (bubbleUp())

1. 노드의 가장 마지막 위치에 신규 노드를 넣는다.
2. 부모가 있는지 확인하고, 넣을 노드가 부모보다 클 경우 위치가 위로 변경되어야 하므로 this.items[index]가 this.parent(index) 보다 작을 때까지 swap해준다.

insert (item) {
        this.items[this.size()] = item;
        this.bubbleUp();
    }

bubbleUp () {
    let index = this.size() - 1;
    while (this.parent(index) && this.parent(index) < this.items[index]) {
        this.swap(this.parentIndex(index), index);
        index = this.parentIndex(index);
    }
}

2. 노드 제거 (extract()) 및 대체된 root노드의 위치 정렬 (bubbleDown())

1. root 노드를 임시 변수에 저장해둔다.

2. root 노드를 제거한다.

3. 가장 마지막 노드를 root 노드에 저장한다.

4. leftChildNode가 존재하고, leftChild가 루트 노드보다 크거나 rightChild가 루트 노드보다 클 때까지 leftChildIndex와 index를 계속 바꿔준다.

5. rightChildNode가 바꾸려는 index의 값보다 클 경우 childIndex에는 오른쪽 index값을 넣어준다.

extract () {
        let item = this.items[0];
        this.items[0] = this.items[this.size() - 1];
        this.items.pop();

        this.bubbleDown();
        return item;
    }

bubbleDown () {
    let index = 0;

    while (
        this.leftChild(index) &&
        (this.leftChild(index) > this.items[index] 
        || this.rightChild(index) > this.items[index])) {
            let childIndex = this.leftChildIndex(index);

            if (this.rightChild(index) && this.rightChild(index) > this.items[childIndex]) {
                childIndex = this.rightChildIndex(index);
            }

            this.swap(childIndex, index);
            index = childIndex;
        }
}

최소 힙

최소 힙의 경우 가장 작은 값이 가장 위에 위치해야 하므로, 최대 힙의 bubbleUp()과 bubbleDown() 에서 부등호의 방향만 변경해주면 된다.

insert (item) {
        this.items[this.size()] = item;
        this.bubbleUp();
    }

bubbleUp () {
    let index = this.size() - 1;

    while (this.parent(index) && this.parent(index) > this.items[index]) {
            this.swap(this.parentIndex(index), index);
            index = this.parentIndex(index);
    }
}

extract () {
    let item = this.items[0];
    this.items[0] = this.items[this.size() - 1];
    this.items.pop();
    this.bubbleDown();
    return item;
}

bubbleDown () {
    let index = 0;

    while (
        this.leftChild(index) &&
        (this.leftChild(index) < this.items[index] 
        || this.rightChild(index) < this.items[index])) {
            let childIndex = this.leftChildIndex(index);

            if (this.rightChild(index) && this.rightChild(index) < this.items[childIndex]) {
                childIndex = this.rightChildIndex(index);
            }
            this.swap(childIndex, index);
            index = childIndex;
        }
}

관련 전체 코드는 Git에 업로드 해두었습니다.
Github_HeapMaxVersion
Github_HeapMinVersion