[자료구조] C++로 이중 우선순위 큐 구현 - 2. 최대 힙

최대 힙에서 유지해야 할 조건

완전 이진 트리를 vector에 저장하는 방식과 부모·자식 인덱스 계산은 1편의 최소 힙 구현과 완전히 같습니다. 달라지는 것은 부모와 자식 사이에서 유지할 순서입니다.

최소 힙: parent <= child
최대 힙: parent >= child

최대 힙에서는 모든 부모가 자식보다 크거나 같아야 합니다. 따라서 루트 heap[0]에는 항상 최댓값이 있습니다. 최소 힙과 마찬가지로 형제 사이의 순서와 배열 전체의 정렬은 보장하지 않습니다.

최소 힙과 최대 힙 비교하기

구분	최소 힙	최대 힙
루트	최솟값	최댓값
부모/자식 조건	parent <= child	parent >= child
업힙 종료	부모가 작거나 같을 때	부모가 크거나 같을 때
다운힙 교환 대상	더 작은 자식	더 큰 자식
top()	최솟값 반환	최댓값 반환

비교 연산만 뒤집는다는 말은 힙의 순서 조건에 한정됩니다. 자식 인덱스의 범위 검사, 루트와 마지막 원소를 교환하는 삭제 절차, 업힙·다운힙이 이동하는 방향은 그대로 유지해야 합니다.

업힙: 부모보다 큰 값을 위로 올리기

삽입은 최소 힙과 동일하게 배열 끝에서 시작합니다. 부모가 현재 값보다 크거나 같으면 최대 힙 조건을 만족하므로 멈추고, 현재 값이 더 크면 부모와 교환합니다.

void heapifyUp(size_t index) {
    while (index > 0) {
        size_t parent = (index - 1) / 2;

        if (heap[parent] >= heap[index]) {
            break;
        }

        swap(heap[parent], heap[index]);
        index = parent;
    }
}

현재 힙 [10, 7, 8, 3, 5]에 12를 삽입하면 다음과 같이 이동합니다.

[10, 7, 8, 3, 5, 12]  // 배열 끝에 삽입
[10, 7, 12, 3, 5, 8]  // 부모 8과 교환
[12, 7, 10, 3, 5, 8]  // 부모 10과 교환

다운힙: 더 큰 자식과 교환하기

pop()은 루트와 마지막 원소를 교환하고 마지막 원소를 제거한 뒤 루트에서 다운힙합니다. 이때 두 자식 중 더 큰 자식을 선택해야 한 번의 교환으로 해당 위치의 최대 힙 조건이 복구됩니다.

void heapifyDown(size_t index) {
    while (true) {
        size_t left = index * 2 + 1;
        size_t right = index * 2 + 2;
        size_t largest = index;

        if (left < heap.size() && heap[left] > heap[largest]) {
            largest = left;
        }

        if (right < heap.size() && heap[right] > heap[largest]) {
            largest = right;
        }

        if (largest == index) {
            break;
        }

        swap(heap[index], heap[largest]);
        index = largest;
    }
}

[12, 9, 10, 4, 7, 8]에서 최댓값을 제거하면 다음과 같습니다.

[8, 9, 10, 4, 7, 12]  // 루트와 마지막 원소 교환
[8, 9, 10, 4, 7]      // 마지막 원소 제거
[10, 9, 8, 4, 7]      // 두 자식 중 더 큰 10과 교환

오른쪽 자식이 없는 경우도 있으므로 값을 읽기 전에 각 인덱스가 heap.size()보다 작은지 따로 검사합니다. 두 자식이 같은 값이면 어느 쪽을 선택해도 힙 조건을 만족합니다.

최종 구현

#include <cstddef>
#include <stdexcept>
#include <utility>
#include <vector>

using namespace std;

class MaxHeap {
private:
    vector<int> heap;

    void heapifyUp(size_t index) {
        while (index > 0) {
            size_t parent = (index - 1) / 2;

            if (heap[parent] >= heap[index]) {
                break;
            }

            swap(heap[parent], heap[index]);
            index = parent;
        }
    }

    void heapifyDown(size_t index) {
        while (true) {
            size_t left = index * 2 + 1;
            size_t right = index * 2 + 2;
            size_t largest = index;

            if (left < heap.size() && heap[left] > heap[largest]) {
                largest = left;
            }

            if (right < heap.size() && heap[right] > heap[largest]) {
                largest = right;
            }

            if (largest == index) {
                break;
            }

            swap(heap[index], heap[largest]);
            index = largest;
        }
    }

public:
    void push(int value) {
        heap.push_back(value);
        heapifyUp(heap.size() - 1);
    }

    void pop() {
        if (heap.empty()) {
            return;
        }

        swap(heap.front(), heap.back());
        heap.pop_back();

        if (!heap.empty()) {
            heapifyDown(0);
        }
    }

    int top() const {
        if (heap.empty()) {
            throw out_of_range("MaxHeap is empty");
        }

        return heap.front();
    }

    bool empty() const {
        return heap.empty();
    }
};

복잡도와 구현 체크포인트

• push()와 pop()은 O(log N)
• 업힙과 다운힙이 완전 이진 트리의 높이만큼 이동할 수 있습니다.
• top()과 empty()는 O(1)
• 루트 또는 벡터의 상태만 확인합니다.
• 다운힙은 더 큰 자식을 선택한다
• 아무 자식과 교환하면 반대편에 더 큰 자식이 남아 최대 힙 조건을 위반할 수 있습니다.
• 동등 비교에서 이동을 멈춘다
• 부모와 자식이 같으면 이미 조건을 만족하므로 불필요한 교환을 하지 않습니다.
• 배열 전체가 내림차순인 것은 아니다
• 최대 힙이 보장하는 것은 부모·자식 관계와 루트의 최댓값뿐입니다.

정리

• 최대 힙은 최소 힙과 배열 구조 및 삽입·삭제 절차가 같다.
• 업힙에서는 부모보다 큰 값을 위로 올린다.
• 다운힙에서는 두 자식 중 더 큰 값과 교환한다.
• 루트에서 최댓값을 O(1)에 조회할 수 있다.
• 삽입과 최댓값 삭제는 O(log N)이다.

최소 힙과 최대 힙을 나란히 구현해 보니 힙의 구조와 우선순위 기준이 분리되어 있다는 점이 분명해졌습니다. 다음 편에서는 두 힙을 함께 사용해 최솟값과 최댓값을 모두 삭제할 수 있는 이중 우선순위 큐를 구현할 예정입니다.