힙(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 시 무시)을 사용해야 합니다.

---

Lazy Deletion — 우선순위 업데이트 처리

std::priority_queue는 임의 원소의 우선순위를 직접 변경하는 decrease_key 연산을 지원하지 않습니다. 가장 실용적인 해결책은 Lazy Deletion(지연 삭제) 패턴입니다. 변경된 항목을 다시 삽입하고, 꺼낼 때 구식 항목인지 확인 후 무시합니다.

#include <queue>
#include <unordered_map>
#include <functional>

// Lazy Deletion을 이용한 업데이트 가능 우선순위 큐
// Dijkstra에서 거리 업데이트 시 자주 사용되는 패턴
class UpdatablePriorityQueue
{
    struct Entry
    {
        float  priority;
        int    id;
        bool operator>(const Entry& other) const { return priority > other.priority; }
    };

    std::priority_queue<Entry, std::vector<Entry>, std::greater<Entry>> _heap;
    std::unordered_map<int, float> _bestPriority; // id -> 현재 최선 우선순위

public:
    void Push(int id, float priority)
    {
        _bestPriority[id] = priority;
        _heap.push({priority, id});
    }

    void UpdatePriority(int id, float newPriority)
    {
        // 구식 항목은 힙에 그대로 두고 최선 우선순위만 갱신
        // pop 시 구식 항목은 건너뜀
        if (!_bestPriority.count(id) || newPriority < _bestPriority[id])
        {
            _bestPriority[id] = newPriority;
            _heap.push({newPriority, id}); // 새 항목 추가 (구식 항목 공존)
        }
    }

    // 유효한 최솟값 항목 반환
    std::pair<float, int> Pop()
    {
        while (!_heap.empty())
        {
            auto [pri, id] = _heap.top();
            _heap.pop();

            // 현재 최선 우선순위와 일치하는 항목만 유효
            if (_bestPriority.count(id) && _bestPriority[id] == pri)
            {
                _bestPriority.erase(id);
                return {pri, id};
            }
            // 구식 항목이면 무시하고 계속
        }
        return {-1.f, -1}; // 비어있음
    }

    bool Empty() const { return _bestPriority.empty(); }
};

Lazy Deletion 트레이드오프:

• 장점: 구현이 단순하고 표준 priority_queue와 호환
• 단점: 힙 내부에 구식 항목이 쌓여 메모리 증가. 최악의 경우 O(E log E)까지 증가 가능
• Dijkstra 구현 시 if (d > dist[u]) continue; 패턴이 바로 Lazy Deletion

---

Unreal Engine TArray 힙 API

Unreal Engine의 TArray는 힙 연산을 내장하고 있어 별도의 자료구조 없이 우선순위 큐를 구현할 수 있습니다.

// Engine/Source/Runtime/Core/Public/Containers/Array.h 참조

// 1. Heapify: 기존 TArray를 힙으로 변환 — O(N)
TArray<int32> Values = {30, 10, 50, 20, 40};
Values.Heapify(); // 기본: Max-Heap (큰 값이 Top)

// 커스텀 비교자로 Min-Heap
Values.Heapify([](const int32& A, const int32& B) { return A < B; });

// 2. HeapPush: 힙 성질 유지하며 삽입 — O(log N)
Values.HeapPush(60);
Values.HeapPush(5, [](const int32& A, const int32& B) { return A < B; });

// 3. HeapTop: 루트 조회 (제거 없음) — O(1)
int32 Top = Values.HeapTop(); // Max-Heap이면 최댓값

// 4. HeapPop: 루트 제거 및 반환 — O(log N)
int32 Popped;
Values.HeapPop(Popped, /*bAllowShrinking=*/false);
// bAllowShrinking=false: 메모리 재할당 방지 (게임 루프에서 권장)

// 5. HeapRemoveAt: 특정 인덱스 원소 제거 — O(log N)
Values.HeapRemoveAt(2, /*bAllowShrinking=*/false);

실전 예시: AI 타깃 우선순위 큐

USTRUCT()
struct FAITarget
{
    GENERATED_BODY()
    TObjectPtr<AActor> Actor;
    float ThreatScore = 0.f; // 높을수록 우선
};

UCLASS()
class UAITargetingComponent : public UActorComponent
{
    GENERATED_BODY()

    TArray<FAITarget> _targetHeap;

    // Max-Heap 비교자: ThreatScore 높은 것이 Top
    static bool TargetCompare(const FAITarget& A, const FAITarget& B)
    {
        return A.ThreatScore > B.ThreatScore;
    }

public:
    void AddTarget(AActor* Actor, float ThreatScore)
    {
        FAITarget Target;
        Target.Actor = Actor;
        Target.ThreatScore = ThreatScore;
        _targetHeap.HeapPush(Target, TargetCompare); // O(log N)
    }

    AActor* GetHighestThreatTarget()
    {
        if (_targetHeap.IsEmpty()) return nullptr;
        return _targetHeap.HeapTop().Actor; // O(1)
    }

    void RemoveTopTarget()
    {
        FAITarget Removed;
        _targetHeap.HeapPop(Removed, TargetCompare, false); // O(log N)
    }

    // 전체 재정렬 (타깃 위협도가 대거 변경됐을 때)
    void RebuildHeap()
    {
        _targetHeap.Heapify(TargetCompare); // O(N)
    }
};

---

성능 특성 요약

연산	시간 복잡도	설명
push / HeapPush	O(log n)	siftUp 수행
pop / HeapPop	O(log n)	siftDown 수행
top / HeapTop	O(1)	루트 노드 직접 접근
make_heap / Heapify	O(n)	전체 배열을 힙으로 변환
sort_heap	O(n log n)	힙 정렬
우선순위 업데이트 (Lazy)	O(log n)	재삽입 + pop 시 무효 항목 건너뜀

std::priority_queue는 중간 원소 접근이 불가능합니다. 특정 원소의 우선순위를 변경하려면 Lazy Deletion 기법을 사용하거나, 인덱스 기반으로 힙 내 위치를 추적하는 Indexed Priority Queue를 직접 구현해야 합니다.

---

정리 — 힙 선택 가이드

상황	권장 방법
단순 최솟값/최댓값 반복 추출	std::priority_queue
우선순위 업데이트 필요 (간단)	Lazy Deletion + std::priority_queue
Unreal 게임플레이 코드	TArray::Heapify + HeapPush/HeapPop
동적 AI 타깃 우선순위 관리	TArray 힙 + Heapify 재구성
힙 정렬	std::sort_heap 또는 TArray::HeapSort

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