8. 힙 & 우선순위 큐 (Heap)

개념

힙(Heap)은 완전 이진 트리 기반의 자료구조로, 부모-자식 간의 대소 관계를 유지한다.

힙의 종류

종류	조건	루트
최대 힙 (Max Heap)	부모 ≥ 자식	최댓값
최소 힙 (Min Heap)	부모 ≤ 자식	최솟값

힙의 특징

• 완전 이진 트리: 마지막 레벨 제외 모두 채워지고, 왼쪽부터 채워짐
• 배열로 구현: 인덱스 계산으로 부모/자식 접근
• 반정렬 상태: 형제 간의 순서는 보장 안 됨

배열 인덱스 규칙 (1-based)

관계	인덱스
부모	i / 2
왼쪽 자식	i * 2
오른쪽 자식	i * 2 + 1

핵심 연산 & 시간복잡도

연산	시간복잡도	설명
삽입 (push)	O(log N)	맨 끝에 삽입 후 위로 이동 (heapify-up)
삭제 (pop)	O(log N)	루트 제거, 맨 끝을 루트로 이동 후 아래로 (heapify-down)
최솟값/최댓값 조회 (top)	O(1)	루트 반환
힙 구성 (heapify)	O(N)	배열을 힙으로 변환

구현 (No-STL)

최소 힙 (Min Heap)

const int MAX_SIZE = 100001;

int heap[MAX_SIZE];
int heapSize = 0;

void init() {
    heapSize = 0;
}

bool isEmpty() {
    return heapSize == 0;
}

void push(int x) {
    heap[++heapSize] = x;

    // Heapify-up
    int cur = heapSize;
    while (cur > 1) {
        int parent = cur / 2;
        if (heap[parent] <= heap[cur]) break;
        // swap
        int temp = heap[parent];
        heap[parent] = heap[cur];
        heap[cur] = temp;
        cur = parent;
    }
}

int pop() {
    if (isEmpty()) return -1;

    int ret = heap[1];
    heap[1] = heap[heapSize--];

    // Heapify-down
    int cur = 1;
    while (cur * 2 <= heapSize) {
        int child = cur * 2;
        // 오른쪽 자식이 더 작으면 선택
        if (child + 1 <= heapSize && heap[child + 1] < heap[child]) {
            child++;
        }
        if (heap[cur] <= heap[child]) break;
        // swap
        int temp = heap[cur];
        heap[cur] = heap[child];
        heap[child] = temp;
        cur = child;
    }

    return ret;
}

int top() {
    if (isEmpty()) return -1;
    return heap[1];
}

최대 힙 (Max Heap)

const int MAX_SIZE = 100001;

int heap[MAX_SIZE];
int heapSize = 0;

void push(int x) {
    heap[++heapSize] = x;

    int cur = heapSize;
    while (cur > 1) {
        int parent = cur / 2;
        if (heap[parent] >= heap[cur]) break;  // 부등호 반대
        int temp = heap[parent];
        heap[parent] = heap[cur];
        heap[cur] = temp;
        cur = parent;
    }
}

int pop() {
    if (heapSize == 0) return -1;

    int ret = heap[1];
    heap[1] = heap[heapSize--];

    int cur = 1;
    while (cur * 2 <= heapSize) {
        int child = cur * 2;
        // 오른쪽 자식이 더 크면 선택
        if (child + 1 <= heapSize && heap[child + 1] > heap[child]) {
            child++;
        }
        if (heap[cur] >= heap[child]) break;  // 부등호 반대
        int temp = heap[cur];
        heap[cur] = heap[child];
        heap[child] = temp;
        cur = child;
    }

    return ret;
}

구조체로 캡슐화

const int MAX_SIZE = 100001;

struct MinHeap {
    int data[MAX_SIZE];
    int size;

    void init() { size = 0; }
    bool isEmpty() { return size == 0; }

    void push(int x) {
        data[++size] = x;
        int cur = size;
        while (cur > 1 && data[cur / 2] > data[cur]) {
            int temp = data[cur / 2];
            data[cur / 2] = data[cur];
            data[cur] = temp;
            cur /= 2;
        }
    }

    int pop() {
        if (isEmpty()) return -1;
        int ret = data[1];
        data[1] = data[size--];
        int cur = 1;
        while (cur * 2 <= size) {
            int child = cur * 2;
            if (child + 1 <= size && data[child + 1] < data[child]) child++;
            if (data[cur] <= data[child]) break;
            int temp = data[cur];
            data[cur] = data[child];
            data[child] = temp;
            cur = child;
        }
        return ret;
    }

    int top() { return isEmpty() ? -1 : data[1]; }
};

배열을 힙으로 변환 (Heapify) - O(N)

// 아래에서 위로 heapify-down 수행
void buildMinHeap(int arr[], int n) {
    // 배열 복사 (1-indexed)
    for (int i = 0; i < n; i++) {
        heap[i + 1] = arr[i];
    }
    heapSize = n;

    // 마지막 내부 노드부터 루트까지
    for (int i = heapSize / 2; i >= 1; i--) {
        heapifyDown(i);
    }
}

void heapifyDown(int cur) {
    while (cur * 2 <= heapSize) {
        int child = cur * 2;
        if (child + 1 <= heapSize && heap[child + 1] < heap[child]) {
            child++;
        }
        if (heap[cur] <= heap[child]) break;
        int temp = heap[cur];
        heap[cur] = heap[child];
        heap[child] = temp;
        cur = child;
    }
}

커스텀 비교 힙 (구조체)

struct Item {
    int priority;
    int data;
};

Item heap[MAX_SIZE];
int heapSize = 0;

// 우선순위가 낮은 것이 먼저 (min heap 기준)
bool compare(Item a, Item b) {
    return a.priority < b.priority;  // a가 우선
}

void push(Item x) {
    heap[++heapSize] = x;
    int cur = heapSize;
    while (cur > 1 && compare(heap[cur], heap[cur / 2])) {
        Item temp = heap[cur / 2];
        heap[cur / 2] = heap[cur];
        heap[cur] = temp;
        cur /= 2;
    }
}

Item pop() {
    Item ret = heap[1];
    heap[1] = heap[heapSize--];
    int cur = 1;
    while (cur * 2 <= heapSize) {
        int child = cur * 2;
        if (child + 1 <= heapSize && compare(heap[child + 1], heap[child])) {
            child++;
        }
        if (compare(heap[cur], heap[child])) break;
        Item temp = heap[cur];
        heap[cur] = heap[child];
        heap[child] = temp;
        cur = child;
    }
    return ret;
}

STL

std::priority_queue (기본: 최대 힙)

#include <queue>

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

maxPQ.push(3);
maxPQ.push(1);
maxPQ.push(4);

maxPQ.top();   // 4 (최댓값)
maxPQ.pop();   // 4 제거
maxPQ.size();  // 2
maxPQ.empty(); // false

최소 힙

#include <queue>
#include <vector>
#include <functional>

// 방법 1: greater 사용
std::priority_queue<int, std::vector<int>, std::greater<int>> minPQ;

minPQ.push(3);
minPQ.push(1);
minPQ.push(4);

minPQ.top();  // 1 (최솟값)

커스텀 비교 함수

#include <queue>
#include <vector>

struct Item {
    int priority;
    int data;
};

// 방법 1: 비교 구조체
struct Compare {
    bool operator()(const Item& a, const Item& b) {
        // true면 a가 b보다 뒤에 옴 (우선순위 낮음)
        return a.priority > b.priority;  // priority 작은 게 먼저
    }
};

std::priority_queue<Item, std::vector<Item>, Compare> pq;

// 방법 2: pair 사용 (first로 정렬)
// first = 우선순위, second = 데이터
std::priority_queue<std::pair<int, int>,
                    std::vector<std::pair<int, int>>,
                    std::greater<std::pair<int, int>>> pq2;

pq2.push({3, 100});  // priority 3, data 100
pq2.push({1, 200});  // priority 1, data 200

auto [priority, data] = pq2.top();  // {1, 200}

다중 조건 정렬

struct Task {
    int deadline;
    int difficulty;
    int id;
};

struct Compare {
    bool operator()(const Task& a, const Task& b) {
        // deadline 오름차순, 같으면 difficulty 내림차순
        if (a.deadline != b.deadline) {
            return a.deadline > b.deadline;  // 작은 게 먼저
        }
        return a.difficulty < b.difficulty;  // 큰 게 먼저
    }
};

std::priority_queue<Task, std::vector<Task>, Compare> pq;

사용 예시

힙 정렬 (Heap Sort)

void heapSort(int arr[], int n) {
    // 1. 최대 힙 구성
    for (int i = 0; i < n; i++) {
        heap[i + 1] = arr[i];
    }
    heapSize = n;

    for (int i = heapSize / 2; i >= 1; i--) {
        int cur = i;
        while (cur * 2 <= heapSize) {
            int child = cur * 2;
            if (child + 1 <= heapSize && heap[child + 1] > heap[child]) child++;
            if (heap[cur] >= heap[child]) break;
            int temp = heap[cur];
            heap[cur] = heap[child];
            heap[child] = temp;
            cur = child;
        }
    }

    // 2. 하나씩 추출하여 정렬
    for (int i = n - 1; i >= 0; i--) {
        arr[i] = heap[1];
        heap[1] = heap[heapSize--];
        // heapify-down
        int cur = 1;
        while (cur * 2 <= heapSize) {
            int child = cur * 2;
            if (child + 1 <= heapSize && heap[child + 1] > heap[child]) child++;
            if (heap[cur] >= heap[child]) break;
            int temp = heap[cur];
            heap[cur] = heap[child];
            heap[child] = temp;
            cur = child;
        }
    }
}

K번째 작은/큰 원소

#include <queue>
#include <vector>

// K번째 작은 원소 - 최대 힙 사용
int kthSmallest(std::vector<int>& arr, int k) {
    std::priority_queue<int> maxPQ;

    for (int x : arr) {
        maxPQ.push(x);
        if (maxPQ.size() > k) {
            maxPQ.pop();  // 가장 큰 거 제거
        }
    }

    return maxPQ.top();  // K번째 작은 원소
}

// K번째 큰 원소 - 최소 힙 사용
int kthLargest(std::vector<int>& arr, int k) {
    std::priority_queue<int, std::vector<int>, std::greater<int>> minPQ;

    for (int x : arr) {
        minPQ.push(x);
        if (minPQ.size() > k) {
            minPQ.pop();
        }
    }

    return minPQ.top();
}

다익스트라 알고리즘

#include <queue>
#include <vector>

const int INF = 1e9;

std::vector<int> dijkstra(int start, std::vector<std::vector<std::pair<int, int>>>& adj) {
    int n = adj.size();
    std::vector<int> dist(n, INF);
    std::priority_queue<std::pair<int, int>,
                        std::vector<std::pair<int, int>>,
                        std::greater<std::pair<int, int>>> pq;

    dist[start] = 0;
    pq.push({0, start});  // {거리, 노드}

    while (!pq.empty()) {
        auto [d, cur] = pq.top();
        pq.pop();

        if (d > dist[cur]) continue;  // 이미 처리됨

        for (auto [next, weight] : adj[cur]) {
            if (dist[cur] + weight < dist[next]) {
                dist[next] = dist[cur] + weight;
                pq.push({dist[next], next});
            }
        }
    }

    return dist;
}

중앙값 유지 (Two Heaps)

#include <queue>

std::priority_queue<int> maxHeap;  // 왼쪽 절반 (작은 값들)
std::priority_queue<int, std::vector<int>, std::greater<int>> minHeap;  // 오른쪽 절반

void addNum(int num) {
    if (maxHeap.empty() || num <= maxHeap.top()) {
        maxHeap.push(num);
    } else {
        minHeap.push(num);
    }

    // 균형 유지 (maxHeap 크기 >= minHeap 크기)
    if (maxHeap.size() > minHeap.size() + 1) {
        minHeap.push(maxHeap.top());
        maxHeap.pop();
    } else if (minHeap.size() > maxHeap.size()) {
        maxHeap.push(minHeap.top());
        minHeap.pop();
    }
}

double getMedian() {
    if (maxHeap.size() == minHeap.size()) {
        return (maxHeap.top() + minHeap.top()) / 2.0;
    }
    return maxHeap.top();
}

주의사항 / Edge Cases

priority_queue는 최대 힙이 기본

// 흔한 실수: 최소 힙이라고 착각
std::priority_queue<int> pq;
pq.push(1);
pq.push(3);
pq.top();  // 3 (최댓값!)

// 최소 힙이 필요하면 명시적으로
std::priority_queue<int, std::vector<int>, std::greater<int>> minPQ;

비교 함수 방향

// STL priority_queue의 Compare: true면 우선순위 "낮음"
// 직관과 반대이므로 주의

struct Compare {
    bool operator()(int a, int b) {
        return a > b;  // a가 b보다 뒤에 → 작은 게 먼저 (min heap)
    }
};

// 정렬의 Compare와 반대라고 생각하면 됨

빈 힙 접근

std::priority_queue<int> pq;

// 위험: Undefined Behavior
// int x = pq.top();  // 빈 힙에서 top

// 안전한 코드
if (!pq.empty()) {
    int x = pq.top();
    pq.pop();
}

힙에서 특정 원소 삭제/수정

// priority_queue는 top 외에는 접근/삭제 불가
// 특정 원소 삭제가 필요하면:

// 방법 1: Lazy Deletion
std::priority_queue<int> pq;
std::set<int> deleted;

void lazyPop() {
    while (!pq.empty() && deleted.count(pq.top())) {
        deleted.erase(pq.top());
        pq.pop();
    }
}

// 방법 2: std::set 사용 (O(log N) 삭제)
std::multiset<int> ms;
ms.erase(ms.find(x));  // 특정 원소 하나 삭제

0-indexed vs 1-indexed

// 직접 구현 시 인덱스 규칙 확인

// 1-indexed (권장)
// parent = i / 2
// left = i * 2
// right = i * 2 + 1

// 0-indexed
// parent = (i - 1) / 2
// left = i * 2 + 1
// right = i * 2 + 2

추천 문제

난이도	문제	링크
Silver	최소 힙	BOJ 1927
Silver	최대 힙	BOJ 11279
Gold	가운데를 말해요	BOJ 1655
Gold	이중 우선순위 큐	BOJ 7662
Gold	최소비용 구하기	BOJ 1916