알고리즘과 자료구조

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

devdiary-sj 2026. 7. 16. 22:13

최소 힙부터 이중 우선순위 큐까지

이전에 프로그래머스의 이중 우선순위 큐 문제를 풀 때는 C++의 multiset을 사용했습니다. 문제 해결에는 잘 맞았지만 자료구조가 내부에서 어떻게 동작하는지 다시 확인하고 싶어 직접 구현해 보기로 했습니다.

  1. 1편: 최소 힙 — 배열 표현과 업힙·다운힙의 기본을 구현한다.
  2. 2편: 최대 힙 — 비교 조건을 뒤집고 최소 힙과 구조를 비교한다.
  3. 3편: 이중 우선순위 큐 — 최소 힙과 최대 힙을 함께 사용하며 두 자료구조의 상태를 동기화한다.

이번 글에서는 세 구현의 기반이 되는 최소 힙에 집중합니다.

포인터 트리 대신 배열을 선택한 이유

예전에 C로 힙을 만들 때는 값과 부모·왼쪽 자식·오른쪽 자식 포인터를 가진 노드를 연결했습니다. 이 방식은 메모리 해제뿐 아니라 다음 삽입 위치와 마지막 노드 탐색, 포인터 연결, 완전 이진 트리 형태 유지까지 직접 관리해야 합니다.

하지만 이번 목표는 포인터 관리가 아니라 힙의 핵심 연산을 이해하는 것입니다. 완전 이진 트리는 빈자리 없이 왼쪽부터 채워지므로 배열에 저장하면 push_back()만으로 다음 삽입 위치를 얻을 수 있습니다. 노드 사이의 관계도 인덱스 계산만으로 찾을 수 있습니다.

배열은 완전 이진 트리의 형태를 별도 포인터 없이 보존합니다. 힙에서 배열을 사용하는 가장 큰 이유입니다.

완전 이진 트리를 배열로 표현하기

루트의 인덱스를 0으로 두면 인덱스 i의 부모와 자식은 다음 식으로 구할 수 있습니다.

leftChild  = 2 * i + 1;
rightChild = 2 * i + 2;
parent     = (i - 1) / 2;
배열: [2, 4, 3, 8, 7, 6]

             2(0)
           /      \
        4(1)      3(2)
       /   \      /
    8(3)  7(4)  6(5)

최소 힙은 모든 부모가 자식보다 작거나 같아야 합니다. 형제끼리의 순서나 같은 깊이에 있는 노드 전체의 정렬은 보장하지 않습니다. 따라서 배열 전체가 정렬되어 있지는 않지만 루트 heap[0]은 항상 최솟값입니다.

구현할 연산 정하기

class MinHeap {
private:
    vector<int> heap;

    void heapifyUp(size_t index);
    void heapifyDown(size_t index);

public:
    void push(int value);
    void pop();
    int top() const;
    bool empty() const;
};
  • push(value): 끝에 값을 넣고 위로 이동시킨다.
  • pop(): 루트의 최솟값을 제거하고 힙 조건을 복구한다.
  • top(): 루트에 있는 최솟값을 반환한다.
  • empty(): 힙이 비었는지 확인한다.

삽입: 끝에 넣고 업힙하기

새 값은 배열 끝에 추가합니다. 이 위치는 완전 이진 트리에서 다음 노드가 들어갈 자리입니다. 이후 부모와 비교하며 최소 힙 조건을 만족할 때까지 위로 올립니다.

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

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;
    }
}

현재 힙이 [3, 7, 5, 10, 8]이고 2를 삽입한다고 해보겠습니다.

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

루트에 도착했으므로 종료합니다. 한 번 교환할 때마다 트리의 높이를 한 단계 올라가므로 최대 이동 횟수는 O(log N)입니다.

삭제: 마지막 값을 루트로 옮기고 다운힙하기

루트를 바로 지우면 배열의 첫 위치가 비어 완전 이진 트리 형태가 깨집니다. 먼저 루트와 마지막 원소를 교환한 뒤 마지막 원소를 제거합니다. 새 루트는 자식보다 클 수 있으므로 더 작은 자식과 교환하며 아래로 내려갑니다.

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

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

    if (!heap.empty()) {
        heapifyDown(0);
    }
}
void heapifyDown(size_t index) {
    while (true) {
        size_t left = index * 2 + 1;
        size_t right = index * 2 + 2;
        size_t smallest = index;

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

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

        if (smallest == index) {
            break;
        }

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

[2, 4, 3, 8, 7, 6]에서 최솟값을 제거하는 과정은 다음과 같습니다.

[6, 4, 3, 8, 7, 2]  // 루트와 마지막 원소 교환
[6, 4, 3, 8, 7]     // 마지막 원소 제거
[3, 4, 6, 8, 7]     // 두 자식 중 더 작은 3과 교환

다운힙에서는 반드시 더 작은 자식과 교환해야 합니다. 예를 들어 부모가 10, 두 자식이 3과 5일 때 5와 교환하면 새 부모 5 아래에 더 작은 자식 3이 남아 최소 힙 조건을 여전히 위반합니다.

최종 구현

빈 힙에서 top()을 호출하는 잘못된 사용은 조용히 숨기지 않고 out_of_range 예외로 알리도록 했습니다.

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

using namespace std;

class MinHeap {
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 smallest = index;

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

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

            if (smallest == index) {
                break;
            }

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

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("MinHeap is empty");
        }

        return heap.front();
    }

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

복잡도와 구현 중 발견한 주의점

  • push()는 O(log N)
  • 배열 끝 삽입은 상각 O(1)이지만 업힙이 트리 높이만큼 이동할 수 있습니다.
  • pop()은 O(log N)
  • 끝 원소 제거는 O(1)이지만 다운힙이 트리 높이만큼 이동할 수 있습니다.
  • top()과 empty()는 O(1)
  • 루트나 벡터의 상태만 확인합니다.
  • 자식의 존재를 먼저 검사한다
  • heap[left]를 읽기 전에는 left < heap.size(), heap[right]를 읽기 전에는 right < heap.size()를 확인해야 합니다.
  • 빈 힙의 top() 계약을 정한다
  • 반환할 값이 없으므로 예외를 던지거나 호출 전에 empty()를 강제하는 등 명확한 정책이 필요합니다.

정리

  • 완전 이진 트리는 배열에 빈자리 없이 저장할 수 있어 힙 구현에 잘 맞는다.
  • 삽입은 배열 끝에서 시작해 부모와 비교하며 업힙한다.
  • 최솟값 삭제는 마지막 값을 루트로 옮긴 뒤 더 작은 자식과 비교하며 다운힙한다.
  • 최소 힙은 루트의 최솟값만 보장하며 배열 전체를 정렬하지 않는다.
  • 삽입과 삭제는 O(log N), 최솟값 조회는 O(1)이다.

포인터 연결 대신 배열 인덱스에 집중하니 힙의 본질은 “완전 이진 트리의 형태”와 “부모·자식 사이의 순서”라는 점이 더 분명해졌습니다. 다음 편에서는 같은 구조에서 비교 방향을 바꿔 최대 힙을 구현하고, 두 구현의 공통점과 차이를 살펴볼 예정입니다.

'알고리즘과 자료구조' 카테고리의 다른 글

[자료구조] C++로 이중 우선순위 큐 구현 - 3. 이중 우선순위 큐  (0) 2026.07.18
[자료구조] C++로 이중 우선순위 큐 구현 - 2. 최대 힙  (1) 2026.07.16
[TIL] DFS와 BFS: 그래프 탐색 방법과 선택 기준  (0) 2026.07.16
[TIL] 동적 계획법으로 중복 계산 줄이기  (0) 2026.07.10
[TIL] 시간복잡도, 빅오 표기법, 대표 자료구조 정리  (1) 2026.07.09

'알고리즘과 자료구조'의 다른글

  • 현재글[자료구조] C++로 이중 우선순위 큐 구현 - 1. 최소 힙

관련글

티스토리툴바