[c++] 최대 힙(Max Heap) 구현

12 Dec 2023

이번에는 C++로 최대 힙(Max Heap)을 구현해 보겠습니다. 최대 힙은 각 노드의 값이 해당 노드의 자식 노드들보다 크거나 같은 트리 구조입니다. 최대 힙은 보통 우선순위 큐 등의 자료구조에 사용됩니다.

최대 힙 구현

아래는 C++로 최대 힙을 구현하는 간단한 예제 코드입니다.

#include <iostream>
#include <vector>
using namespace std;

class MaxHeap {
private:
    vector<int> heap;

    int parent(int i) { return (i - 1) / 2; }
    int left(int i) { return 2 * i + 1; }
    int right(int i) { return 2 * i + 2; }

    void max_heapify(int i) {
        int largest = i;
        int l = left(i);
        int r = right(i);
        if (l < heap.size() && heap[l] > heap[largest])
            largest = l;
        if (r < heap.size() && heap[r] > heap[largest])
            largest = r;
        if (largest != i) {
            swap(heap[i], heap[largest]);
            max_heapify(largest);
        }
    }

public:
    void insert(int key) {
        int i = heap.size();
        heap.push_back(key);
        while (i != 0 && heap[parent(i)] < heap[i]) {
            swap(heap[i], heap[parent(i)]);
            i = parent(i);
        }
    }

    int extractMax() {
        if (heap.empty())
            return -1;
        int max = heap[0];
        heap[0] = heap.back();
        heap.pop_back();
        max_heapify(0);
        return max;
    }
};

위 코드는 MaxHeap 클래스를 정의하고, insert와 extractMax 메서드를 구현한 것입니다. max_heapify 메서드는 특정 인덱스의 노드를 최대 힙 속성에 맞게 재배열하는 역할을 합니다.

결론

이렇게 C++로 최대 힙을 구현할 수 있습니다. 최대 힙은 정렬 알고리즘이나 우선순위 큐 등 다양한 상황에서 사용되므로, 구현 방법을 숙지하는 것이 중요합니다.

참고 문헌: GeeksforGeeks