힙(Heap)과 우선순위 큐 — 구조와 STL 활용

힙이란 무엇인가

힙(Heap)은 완전 이진 트리(Complete Binary Tree) 형태를 유지하면서 부모 노드가 자식 노드보다 항상 크거나(최대 힙) 작은(최소 힙) 성질을 만족하는 자료구조입니다.

핵심 특성은 “최솟값 또는 최댓값을 O(1)에 조회하고, 삽입/삭제를 O(log n)에 처리한다”는 점입니다.

배열로 구현하는 이유

힙은 완전 이진 트리이므로 포인터 없이 배열 인덱스만으로 부모-자식 관계를 계산할 수 있습니다.

인덱스 i인 노드에 대해:
  부모: (i - 1) / 2
  왼쪽 자식: 2 * i + 1
  오른쪽 자식: 2 * i + 2

이 성질 덕분에 메모리 할당 오버헤드 없이 캐시 친화적인 구현이 가능합니다.

---

최소 힙 직접 구현

#include <vector>
#include <stdexcept>

class MinHeap
{
    std::vector<int> data;

    // 삽입 후 위로 재정렬
    void siftUp(int idx)
    {
        while (idx > 0)
        {
            int parent = (idx - 1) / 2;
            if (data[parent] <= data[idx]) break;
            std::swap(data[parent], data[idx]);
            idx = parent;
        }
    }

    // 삭제 후 아래로 재정렬
    void siftDown(int idx)
    {
        int n = static_cast<int>(data.size());
        while (true)
        {
            int smallest = idx;
            int left  = 2 * idx + 1;
            int right = 2 * idx + 2;

            if (left  < n && data[left]  < data[smallest]) smallest = left;
            if (right < n && data[right] < data[smallest]) smallest = right;

            if (smallest == idx) break;

            std::swap(data[idx], data[smallest]);
            idx = smallest;
        }
    }

public:
    void push(int value)
    {
        data.push_back(value);
        siftUp(static_cast<int>(data.size()) - 1);
    }

    int top() const
    {
        if (data.empty()) throw std::runtime_error("Heap is empty");
        return data[0];
    }

    void pop()
    {
        if (data.empty()) throw std::runtime_error("Heap is empty");
        data[0] = data.back();
        data.pop_back();
        if (!data.empty()) siftDown(0);
    }

    bool empty() const { return data.empty(); }
    size_t size() const { return data.size(); }
};

---

STL 힙 알고리즘: <algorithm>

C++ 표준 라이브러리는 임의 접근 컨테이너(주로 std::vector)를 힙으로 다루는 네 가지 알고리즘을 제공합니다.

#include <algorithm>
#include <vector>
#include <iostream>

int main()
{
    std::vector<int> v = {3, 1, 4, 1, 5, 9, 2, 6};

    // 1. 벡터를 최대 힙으로 변환 O(n)
    std::make_heap(v.begin(), v.end());
    std::cout << "Max: " << v.front() << "\n"; // 9

    // 2. 힙에 요소 추가
    v.push_back(10);
    std::push_heap(v.begin(), v.end()); // 새 요소를 힙 성질에 맞게 정렬
    std::cout << "New Max: " << v.front() << "\n"; // 10

    // 3. 최대 요소 제거
    // 최댓값을 맨 뒤로 이동시킨 뒤 힙 범위를 줄임
    std::pop_heap(v.begin(), v.end());
    std::cout << "Popped: " << v.back() << "\n"; // 10
    v.pop_back();

    // 4. 힙 정렬 (오름차순, O(n log n))
    // sort_heap 후 v는 더 이상 힙이 아님
    std::sort_heap(v.begin(), v.end());
    for (int x : v) std::cout << x << " ";
    // 출력: 1 1 2 3 4 5 6 9
}

커스텀 비교 함수

// 최소 힙으로 동작하게 하려면 greater<> 사용
std::make_heap(v.begin(), v.end(), std::greater<int>{});
std::push_heap(v.begin(), v.end(), std::greater<int>{});
std::pop_heap(v.begin(), v.end(), std::greater<int>{});

주의: make_heap, push_heap, pop_heap, sort_heap 호출 시 동일한 비교 함수를 일관되게 전달해야 합니다. 불일치하면 힙 성질이 깨집니다.

---

std::priority_queue

std::priority_queue는 힙 알고리즘을 내부적으로 사용하는 어댑터 컨테이너입니다. 기본적으로 최대 힙입니다.

#include <queue>
#include <functional>

// 기본: 최대 힙
std::priority_queue<int> maxPQ;

// 최소 힙
std::priority_queue<int, std::vector<int>, std::greater<int>> minPQ;

// 커스텀 타입
struct Task
{
    int priority;
    std::string name;

    // 우선순위가 낮을수록 먼저 처리 (최소 힙 동작)
    bool operator>(const Task& other) const
    {
        return priority > other.priority;
    }
};

std::priority_queue<Task, std::vector<Task>, std::greater<Task>> taskQueue;
taskQueue.push({1, "Critical Bug Fix"});
taskQueue.push({3, "Refactoring"});
taskQueue.push({2, "Feature Request"});

while (!taskQueue.empty())
{
    auto [pri, name] = taskQueue.top();
    taskQueue.pop();
    // 출력 순서: Critical Bug Fix -> Feature Request -> Refactoring
}

---

게임 개발 응용 사례

1. A* 경로 탐색의 Open List

A* 알고리즘에서 탐색 후보를 F값 기준으로 정렬할 때 우선순위 큐가 필수입니다.

struct AStarNode
{
    float fCost; // g + h
    int   nodeId;

    bool operator>(const AStarNode& other) const
    {
        return fCost > other.fCost; // 낮은 fCost가 우선
    }
};

std::priority_queue<
    AStarNode,
    std::vector<AStarNode>,
    std::greater<AStarNode>> openList;

openList.push({0.f, startId});

while (!openList.empty())
{
    auto [cost, current] = openList.top();
    openList.pop();

    if (current == goalId) break;

    for (int neighbor : getNeighbors(current))
    {
        float newCost = cost + getEdgeCost(current, neighbor);
        openList.push({newCost + heuristic(neighbor, goalId), neighbor});
    }
}

2. 이벤트 스케줄러 (타임라인 기반)

게임 내 예약된 이벤트를 발생 시각 순서로 처리하는 타이머 시스템입니다.

struct TimedEvent
{
    float triggerTime;
    std::function<void()> callback;

    bool operator>(const TimedEvent& other) const
    {
        return triggerTime > other.triggerTime;
    }
};

class EventScheduler
{
    std::priority_queue<
        TimedEvent,
        std::vector<TimedEvent>,
        std::greater<TimedEvent>> eventQueue;

public:
    void scheduleAt(float time, std::function<void()> cb)
    {
        eventQueue.push({time, std::move(cb)});
    }

    void update(float currentTime)
    {
        while (!eventQueue.empty() &&
               eventQueue.top().triggerTime <= currentTime)
        {
            eventQueue.top().callback();
            eventQueue.pop();
        }
    }
};

3. 적 스폰 시스템 (난이도 우선순위)

현재 게임 점수와 플레이어 위치를 기반으로 가장 위협적인 적을 먼저 스폰합니다.

struct SpawnRequest
{
    float priority;  // 높을수록 긴급
    int   enemyType;
    float spawnX, spawnY;
};

std::priority_queue<SpawnRequest,
    std::vector<SpawnRequest>,
    // 람다를 비교자로 사용
    decltype([](const SpawnRequest& a, const SpawnRequest& b)
    {
        return a.priority < b.priority; // 최대 힙 유지
    })> spawnQueue;

---

성능 특성 요약

연산	시간 복잡도	설명
push	O(log n)	siftUp 수행
pop	O(log n)	siftDown 수행
top	O(1)	루트 노드 직접 접근
make_heap	O(n)	전체 배열을 힙으로 변환
sort_heap	O(n log n)	힙 정렬

std::priority_queue는 중간 요소 접근이 불가능합니다. 특정 요소의 우선순위를 변경하려면 내부 벡터를 직접 조작하거나, “Lazy Deletion” 기법(삭제 표시 후 pop 시 무시)을 사용해야 합니다.

---

마무리

힙은 단순한 자료구조이지만 우선순위 큐, 힙 정렬, A* 탐색, 이벤트 스케줄러 등 게임 개발 전반에서 핵심 역할을 합니다. C++ STL의 priority_queue와 <algorithm> 힙 함수를 이해하면 대부분의 우선순위 기반 문제를 간결하게 해결할 수 있습니다.

다음 단계로는 Fibonacci Heap을 이용한 Dijkstra 최적화, Indexed Priority Queue로 우선순위 업데이트 지원, 또는 Pairing Heap 같은 고급 힙 변형을 학습하는 것을 권장합니다.