[Data Structure] 힙(Heap)

힙(Heap) 자료구조에 대해 정리하였습니다.

---

< 힙(Heap) >

힙(Heap) 자료구조는 트리 기반의 완전 이진 트리로, 특정한 순서 속성을 유지하는 데이터 구조입니다. 최대 힙(Max Heap)과 최소 힙(Min Heap)으로 구분됩니다.

일반적으로 배열을 통해 구현합니다.

 

최대 힙 (Max Heap):

• 각 부모 노드의 값이 자식 노드의 값보다 크거나 같습니다.
• 트리의 루트(root) 노드는 항상 최대값을 가집니다.

 

최소 힙 (Min Heap):

• 각 부모 노드의 값이 자식 노드의 값보다 작거나 같습니다.
• 트리의 루트 노드는 항상 최소값을 가집니다.

 

---

[ 힙의 배열 표현 ]

: 힙은 배열로 쉽게 표현할 수 있습니다. 배열 인덱스를 이용하여 부모와 자식 노드 간의 관계를 정의할 수 있습니다:

• 부모 노드 인덱스: i
• 왼쪽 자식 노드 인덱스: 2 * i + 1
• 오른쪽 자식 노드 인덱스: 2 * i + 2

 

힙의 배열 표현

 

 

---

< 구현 :최대 힙 >

class MaxHeap {
    constructor() {
        this.heap = []; // 힙을 배열로 구현합니다.
    }

    // 부모 노드의 인덱스를 반환합니다.
    getParentIndex(index) {
        return Math.floor((index - 1) / 2);
    }

    // 왼쪽 자식 노드의 인덱스를 반환합니다.
    getLeftChildIndex(index) {
        return 2 * index + 1;
    }

    // 오른쪽 자식 노드의 인덱스를 반환합니다.
    getRightChildIndex(index) {
        return 2 * index + 2;
    }

    // 두 노드의 위치를 바꿉니다.
    swap(index1, index2) {
        [this.heap[index1], this.heap[index2]] = [this.heap[index2], this.heap[index1]];
    }

    // 새로운 요소를 삽입합니다.
    insert(value) {
        this.heap.push(value); // 힙의 맨 끝에 요소를 추가합니다.
        this.heapifyUp(); // 요소를 위로 올려서 힙 속성을 유지합니다.
    }

    // 삽입한 요소를 위로 올려서 힙 속성을 유지합니다.
    heapifyUp() {
        let index = this.heap.length - 1;
        while (index > 0) {
            const parentIndex = this.getParentIndex(index);
            if (this.heap[index] <= this.heap[parentIndex]) break; // 부모와 비교하여 힙 속성을 만족하면 종료합니다.
            this.swap(index, parentIndex); // 부모와 자식을 교환합니다.
            index = parentIndex; // 현재 인덱스를 부모의 인덱스로 업데이트합니다.
        }
    }

    // 최대값을 제거하고 반환합니다.
    extractMax() {
        if (this.heap.length === 0) return null; // 힙이 비어있으면 null을 반환합니다.
        if (this.heap.length === 1) return this.heap.pop(); // 힙에 요소가 하나만 있으면 그 값을 반환하고 힙을 비웁니다.

        const max = this.heap[0]; // 최대값은 항상 루트에 위치합니다.
        this.heap[0] = this.heap.pop(); // 힙의 맨 끝 요소를 루트로 옮기고 배열에서 제거합니다.
        this.heapifyDown(0); // 루트에서부터 아래로 내려가면서 힙 속성을 유지합니다.
        return max; // 최대값을 반환합니다.
    }

    // 루트에서부터 아래로 내려가면서 힙 속성을 유지합니다.
    heapifyDown(index) {
        let largest = index;
        const leftChildIndex = this.getLeftChildIndex(index);
        const rightChildIndex = this.getRightChildIndex(index);

        // 왼쪽 자식과 비교하여 가장 큰 값을 찾습니다.
        if (leftChildIndex < this.heap.length && this.heap[leftChildIndex] > this.heap[largest]) {
            largest = leftChildIndex;
        }

        // 오른쪽 자식과 비교하여 가장 큰 값을 찾습니다.
        if (rightChildIndex < this.heap.length && this.heap[rightChildIndex] > this.heap[largest]) {
            largest = rightChildIndex;
        }

        if (largest !== index) {
            this.swap(index, largest); // 가장 큰 자식과 부모를 교환합니다.
            this.heapifyDown(largest); // 교환한 자식 위치에서부터 다시 heapifyDown을 호출합니다.
        }
    }
}

// 사용 예제
const maxHeap = new MaxHeap();
maxHeap.insert(10);
maxHeap.insert(20);
maxHeap.insert(5);
maxHeap.insert(30);

console.log(maxHeap.extractMax()); // 30
console.log(maxHeap.extractMax()); // 20
console.log(maxHeap.extractMax()); // 10
console.log(maxHeap.extractMax()); // 5