Max-Heap 알고리즘

1.기본개념

• Max-Heap은 이진 트리의 일종으로, 부모 노드가 자식 노드보다 항상 크거나 같은 값을 가지는 특성을 가짐
• Max-Heap의 규칙:
  • 완전 이진 트리(Complete Binary Tree): 마지막 레벨을 제외한 모든 레벨이 완전히 채워져 있으며, 마지막 레벨은 왼쪽에서 오른쪽으로 채워짐
  • 부모 노드의 값이 자식 노드의 값보다 크거나 같음

Max-Heap 배열로 표현

인덱스 i의 노드는 다음과 같은 자식 노드와 부모 노드의 관계를 가짐

• 왼쪽 자식 노드: 2i + 1
• 오른쪽 자식 노드: 2i + 2
• 부모 노드: (i - 1) // 2 ( // : 정수 나눗셈 연산자 - 소수점 이하를 버리고 정수 부분만을 반환)

Index: 0 1 2 3 4 5 6 7 8
Array: [20, 15, 18, 8, 10, 5, 7, 3, 6]

이진 트리 표현

         20 (0)
        /     \
     15 (1)  18 (2)
     /  \    /  \
  8 (3) 10(4) 5 (5) 7 (6)
  /  \
3 (7) 6 (8)

 

완전 이진 트리와 Max-Heap의 관계

Max-Heap은 완전 이진 트리의 특성을 가지고 있으므로, 모든 노드가 왼쪽에서 오른쪽으로 순차적으로 채워짐. 이를 통해 힙의 효율적인 삽입과 삭제 연산이 가능! 완전 이진 트리는 배열로 쉽게 표현할 수 있어 힙을 배열로 구현하는 데 유리.

구현

 

class MaxHeap {
    constructor() {
        this.heap = [];
    }

    insert(val) {
        this.heap.push(val);
        this._siftUp(this.heap.length - 1);
    }

    deleteMax() {
        if (this.heap.length === 0) return null;
        if (this.heap.length === 1) return this.heap.pop();

        const maxVal = this.heap[0];
        this.heap[0] = this.heap.pop();
        this._siftDown(0);
        return maxVal;
    }

    _siftUp(index) {
        let parent = Math.floor((index - 1) / 2);
        while (index > 0 && this.heap[index] > this.heap[parent]) {
            [this.heap[index], this.heap[parent]] = [this.heap[parent], this.heap[index]];
            index = parent;
            parent = Math.floor((index - 1) / 2);
        }
    }

    _siftDown(index) {
        let largest = index;
        const left = 2 * index + 1;
        const right = 2 * index + 2;

        if (left < this.heap.length && this.heap[left] > this.heap[largest]) {
            largest = left;
        }
        if (right < this.heap.length && this.heap[right] > this.heap[largest]) {
            largest = right;
        }
        if (largest !== index) {
            [this.heap[index], this.heap[largest]] = [this.heap[largest], this.heap[index]];
            this._siftDown(largest);
        }
    }
}

 

insert(val): 새로운 값을 힙에 추가하고 _siftUp을 호출하여 힙 속성을 유지
_siftUp(index): 삽입된 값을 부모 노드와 비교하여 힙 속성이 유지되도록 위로 이동시킴
deleteMax(): 힙의 최대 값을 제거하고 마지막 원소를 루트로 이동시킨 후 _siftDown을 호출하여 힙 속성을 유지
_siftDown(index): 루트 값을 자식 노드와 비교하여 힙 속성이 유지되도록 아래로 이동시킴

예시문제

주어진 배열 [3, 1, 4, 1, 5, 9, 2, 6, 5, 3, 5]을 Max-Heap으로 변환하고, 최대 값을 제거한 후의 힙 상태를 출력하세요.

 

const heap = new MaxHeap();
const arr = [3, 1, 4, 1, 5, 9, 2, 6, 5, 3, 5];

// 배열의 모든 값을 힙에 삽입
arr.forEach(num => heap.insert(num));

console.log("Max-Heap:", heap.heap);

// 최대 값 제거
const maxVal = heap.deleteMax();
console.log("Removed Max Value:", maxVal);
console.log("Heap after removing max value:", heap.heap);

 

출력

Max-Heap: [ 9, 6, 5, 5, 5, 4, 2, 1, 3, 1, 3 ]
Removed Max Value: 9
Heap after removing max value: [ 6, 5, 5, 3, 5, 4, 2, 1, 3, 1 ]

결론

Max-Heap은 우선순위 큐와 힙 정렬을 구현하는 데 필수적인 자료구조이다. 삽입과 삭제 연산이 효율적이며, 완전 이진 트리의 특성을 가지므로 배열을 이용한 구현이 용이하다.