벡터 힙과 priority_queue 중 뭘 쓰나요?

중간 삽입·임의 제거가 잦지 않고 최댓값만 꺼내면 priority_queue가 간단합니다. 같은 범위를 다른 알고리즘과 섞어 쓰려면 힙 알고리즘을 직접 다룰 때가 많습니다.

push_heap 후 벡터가 항상 정렬되나요?

아니요, 힙 속성만 만족합니다. 전체 정렬은 sort_heap으로 마무리합니다.

최소 힙을 만들려면?

비교자를 반대로 두거나 값에 부호를 뒤집는 트릭을 씁니다. priority_queue의 템플릿 인자 세 번째 타입으로 비교를 지정할 수 있습니다.

상위 K개만 필요할 때는?

N이 크면 전체 정렬 대신 크기 K 힙이나 nth_element 계열이 유리할 수 있습니다. 데이터 분포를 보고 고르세요.

C++ Algorithm Heap | '힙 알고리즘' 가이드

2026년 3월 12일 · 16분 읽기 · 수정 2026년 3월 30일 중급 튜토리얼

이 글의 핵심

make_heap·push_heap·pop_heap·sort_heap으로 벡터를 힙으로 다루는 방법, priority_queue와의 관계, 커스텀 비교자, 상위 K개·힙 정렬까지 정리합니다.

힙 알고리즘

힙 자료구조 (최대 힙)

#include <algorithm>
#include <vector>

std::vector<int> v = {3, 1, 4, 1, 5};

// 힙 생성
std::make_heap(v.begin(), v.end());

// 최대값
std::cout << v.front() << std::endl;  // 5

make_heap, push_heap, pop_heap이 하는 일

C++ 표준의 기본 힙은 최대 힙(max-heap) 입니다. 비교 객체가 기본(std::less)일 때, v.front()가 항상 가장 “큰” 원소를 가리킵니다(동률이면 구현에 따라 어느 쪽이든).

연산	전제	효과	복잡도(대략)
`make_heap(b, e)`	없음	`[b,e)`를 힙 구조로 재배열	선형
`push_heap(b, e)`	`[b,e-1)`가 이미 힙, 새 값은 `e-1`	새 원소를 끼워 넣어 다시 힙으로	로그
`pop_heap(b, e)`	`[b,e)`가 힙	최상단(최대)을 `e-1` 위치로 보내고 나머지를 힙으로	로그
`sort_heap(b, e)`	`[b,e)`가 힙	전체를 오름차순 정렬(최대 힙 기준)	O(n log n)

중요한 사용 순서:

삽입: v.push_back(x); 후 push_heap(v.begin(), v.end()) — 새 원소가 마지막에 있어야 합니다.
추출: pop_heap(v.begin(), v.end()); 후 v.pop_back(); — pop_heap이 “가장 큰 값”을 끝으로 보낸 뒤, 물리적으로 제거는 pop_back으로 합니다.

is_heap, is_heap_until로 디버깅 시 힙 속성이 깨졌는지 확인할 수 있습니다.

priority_queue와의 관계

std::priority_queue는 컨테이너 어댑터로, 내부적으로 보통 vector + push_heap / pop_heap 과 같은 힙 연산을 씁니다. 차이는 인터페이스입니다.

priority_queue: push/top/pop만 노출하고, 내부 벡터의 나머지 원소는 캡슐화됩니다. 가장 큰(또는 비교자에 따른 최우선) 하나만 꺼내는 큐로 쓰기 좋습니다.
힙 알고리즘 직접 사용: 같은 vector를 힙 구간과 비힙 구간으로 나누거나, 중간 상태를 직접 순회·수정해야 할 때 유리합니다(예: 힙 일부만 유지, 커스텀 파이프라인).

// 개념적으로 유사: pq.push(3) ≈ v.push_back(3); push_heap(...)
// 실행 예제
std::priority_queue<int> pq;
std::vector<int> v;

pq.push(3);
v.push_back(3);
std::push_heap(v.begin(), v.end());

최소 힙이 필요하면 priority_queue<int, vector<int>, greater<int>>처럼 비교자를 주면 되고, 아래 커스텀 비교자와 동일한 규칙을 힙 함수들에도 일관되게 적용해야 합니다.

커스텀 비교자(Comparator)와 주의점

make_heap, push_heap, pop_heap, sort_heap은 모두 선택적 Compare 인자를 받습니다. std::priority_queue의 Compare와 마찬가지로, 힙에서 “가장 앞에 올” 원소가 비교 의미상 “가장 우선”인 쪽이 됩니다.

기본 std::less → 최대 힙(가장 큰 값이 front).
std::greater → 최소 힙(가장 작은 값이 front).

std::vector<int> v = {3, 1, 4};
std::make_heap(v.begin(), v.end(), std::greater<>()); // 최소 힙

모든 힙 연산에 동일한 Compare를 넘겨야 합니다. 하나만 다르면 힙 불변식이 깨져 이후 pop_heap 등이 UB입니다.

사용자 정의 타입이면 operator< 또는 람다로 “정렬 기준”을 명확히 하세요.

struct Task { int id; int priority; };

std::vector<Task> tasks = /* ....*/;
auto cmp = [](const Task& a, const Task& b) {
    return a.priority < b.priority; // priority 큰 것이 top
};
std::make_heap(tasks.begin(), tasks.end(), cmp);

실전: 상위 K개 찾기 (Top-K)

전체를 정렬하면 O(n log n)이지만, K가 작을 때 크기 K의 힙을 유지하면 O(n log K) 로 줄일 수 있습니다. “가장 큰 K개”를 원하면 최소 힙(가장 작은 값이 루트) 을 K개 유지하고, 더 큰 값이 들어오면 루트를 교체합니다(기존 예시와 동일한 패턴).

K ≪ n 이면 전체 정렬보다 유리한 경우가 많습니다.
K가 n에 가깝다면 partial_sort나 nth_element가 나을 수 있어, 프로파일링으로 선택하세요.
동일 값이 많을 때 순서가 중요하면 stable_sort 등 다른 요구와 맞는지 확인합니다.

힙 정렬(Heap sort) 정리

make_heap으로 최대 힙을 만든 뒤, pop_heap을 반복하면 큰 값부터 뒤로 정렬되고, 결국 sort_heap 한 번으로 오름차순 전체 정렬이 됩니다. 교과서적인 힙 정렬과 동일하며, 실무에서는 보통 std::sort 가 더 빠른 경우가 많아 학습·인터뷰·제약 환경에서 선택하는 경우가 많습니다.

std::vector<int> v = {3, 1, 4, 1, 5, 9, 2, 6};
std::make_heap(v.begin(), v.end());
std::sort_heap(v.begin(), v.end());
// v는 비교자에 따른 정렬 순서(기본은 오름차순)

sort_heap은 이미 힙인 구간에 대해 동작합니다. 힙이 아닌 벡터에 바로 sort_heap만 호출하면 안 됩니다. 먼저 make_heap이 필요합니다.

기본 사용

#include <algorithm>

std::vector<int> v = {3, 1, 4, 1, 5};

// 힙 생성
std::make_heap(v.begin(), v.end());

// 최대값 제거
std::pop_heap(v.begin(), v.end());
v.pop_back();

// 값 추가
v.push_back(9);
std::push_heap(v.begin(), v.end());

실전 예시

예시 1: 최대 힙

#include <algorithm>
#include <vector>

int main() {
    std::vector<int> heap;
    
    // 요소 추가
    for (int x : {3, 1, 4, 1, 5, 9, 2, 6}) {
        heap.push_back(x);
        std::push_heap(heap.begin(), heap.end());
    }
    
    // 최대값부터 제거
    while (!heap.empty()) {
        std::cout << heap.front() << " ";
        std::pop_heap(heap.begin(), heap.end());
        heap.pop_back();
    }
    // 9 6 5 4 3 2 1 1
}

예시 2: 최소 힙

#include <algorithm>
#include <vector>
#include <functional>

int main() {
    std::vector<int> heap = {3, 1, 4, 1, 5};
    
    // 최소 힙
    std::make_heap(heap.begin(), heap.end(), std::greater<>());
    
    std::cout << "최소: " << heap.front() << std::endl;  // 1
}

예시 3: 상위 k개

#include <algorithm>
#include <vector>

std::vector<int> topK(const std::vector<int>& data, size_t k) {
    std::vector<int> heap;
    
    for (int x : data) {
        if (heap.size() < k) {
            heap.push_back(x);
            std::push_heap(heap.begin(), heap.end(), std::greater<>());
        } else if (x > heap.front()) {
            std::pop_heap(heap.begin(), heap.end(), std::greater<>());
            heap.back() = x;
            std::push_heap(heap.begin(), heap.end(), std::greater<>());
        }
    }
    
    std::sort_heap(heap.begin(), heap.end(), std::greater<>());
    return heap;
}

int main() {
    std::vector<int> data = {3, 1, 4, 1, 5, 9, 2, 6, 5, 3};
    auto top3 = topK(data, 3);
    
    for (int x : top3) {
        std::cout << x << " ";  // 9 6 5
    }
}

예시 4: 힙 정렬

#include <algorithm>

int main() {
    std::vector<int> v = {3, 1, 4, 1, 5, 9, 2, 6};
    
    // 힙 생성
    std::make_heap(v.begin(), v.end());
    
    // 힙 정렬
    std::sort_heap(v.begin(), v.end());
    
    for (int x : v) {
        std::cout << x << " ";  // 1 1 2 3 4 5 6 9
    }
}

힙 연산

// 힙 생성
std::make_heap(begin, end)

// 요소 추가
v.push_back(value);
std::push_heap(begin, end)

// 요소 제거
std::pop_heap(begin, end)
v.pop_back()

// 힙 정렬
std::sort_heap(begin, end)

// 힙 확인
bool isHeap = std::is_heap(begin, end)

자주 발생하는 문제

문제 1: 힙 속성

std::vector<int> v = {3, 1, 4, 1, 5};

// ❌ 힙 아님
// std::pop_heap(v.begin(), v.end());  // 정의되지 않은 동작

// ✅ 힙 생성 후
std::make_heap(v.begin(), v.end());
std::pop_heap(v.begin(), v.end());

문제 2: push_heap 순서

std::vector<int> heap = {3, 1, 4};
std::make_heap(heap.begin(), heap.end());

// ❌ 잘못된 순서
// std::push_heap(heap.begin(), heap.end());
// heap.push_back(5);  // 늦게 추가

// ✅ 올바른 순서
heap.push_back(5);
std::push_heap(heap.begin(), heap.end());

문제 3: pop_heap 순서

std::vector<int> heap = {5, 4, 3, 1, 1};

// ✅ 올바른 순서
std::pop_heap(heap.begin(), heap.end());  // 최대값을 끝으로
heap.pop_back();  // 제거

// ❌ 잘못된 순서
// heap.pop_back();
// std::pop_heap(heap.begin(), heap.end());

문제 4: 비교 함수

// 최대 힙 (기본)
std::make_heap(v.begin(), v.end());

// 최소 힙
std::make_heap(v.begin(), v.end(), std::greater<>());

// 모든 힙 연산에 같은 비교 함수 사용
std::push_heap(v.begin(), v.end(), std::greater<>());
std::pop_heap(v.begin(), v.end(), std::greater<>());

priority_queue vs 힙

// priority_queue: 래퍼
std::priority_queue<int> pq;
pq.push(3);
pq.push(1);
pq.push(4);
std::cout << pq.top() << std::endl;  // 4

// 힙 알고리즘: 직접 제어
std::vector<int> heap;
heap.push_back(3);
std::push_heap(heap.begin(), heap.end());
heap.push_back(1);
std::push_heap(heap.begin(), heap.end());
std::cout << heap.front() << std::endl;  // 4

FAQ

Q1: 힙은?

A: 최대/최소 힙 자료구조.

Q2: make_heap?

A: 벡터를 힙으로 변환.

Q3: push_heap?

A: 힙에 요소 추가.

Q4: pop_heap?

A: 최대값 제거 (끝으로 이동).

Q5: priority_queue?

A: 힙 래퍼. 편리함.

Q6: 학습 리소스는?

“Introduction to Algorithms”
“Effective STL”
cppreference.com

같이 보면 좋은 글 (내부 링크)

이 주제와 연결되는 다른 글입니다.

실전 팁 (C++)

컴파일러 경고를 최대로 켜고(-Wall -Wextra 등 팀 합의), Sanitizer(ASan/UBSan)로 미정의 동작을 조기에 잡습니다.
최적화는 프로파일 결과를 본 뒤에 합니다.
STL <algorithm> 사용 시 반복자 무효화·비교자 일관성을 함께 검토합니다.

실전 체크리스트 (C++)

경고·정적 분석에서 새로운 이슈가 없는가?
빈 범위·단일 원소 등 경계 조건을 테스트했는가?

이 글에서 다루는 키워드 (관련 검색어)

C++, algorithm, heap, priority-queue, STL 등으로 검색하시면 이 글이 도움이 됩니다.

심화 부록: 구현·운영 관점

이 부록은 앞선 본문에서 다룬 주제(「C++ Algorithm Heap | ‘힙 알고리즘’ 가이드」)를 구현·런타임·운영 관점에서 다시 압축합니다. 도메인별 세부 구현은 글마다 다르지만, 입력 검증 → 핵심 연산 → 부작용(I/O·네트워크·동시성) → 관측의 흐름으로 장애를 나누면 원인 추적이 빨라집니다.

내부 동작과 핵심 메커니즘

flowchart TD
  A[입력·요청·이벤트] --> B[파싱·검증·디코딩]
  B --> C[핵심 연산·상태 전이]
  C --> D[부작용: I/O·네트워크·동시성]
  D --> E[결과·관측·저장]

sequenceDiagram
  participant C as 클라이언트/호출자
  participant B as 경계(런타임·게이트웨이·프로세스)
  participant D as 의존성(API·DB·큐·파일)
  C->>B: 요청/이벤트
  B->>D: 조회·쓰기·RPC
  D-->>B: 지연·부분 실패·재시도 가능
  B-->>C: 응답 또는 오류(코드·상관 ID)

불변 조건(Invariant): 버퍼 경계, 프로토콜 상태, 트랜잭션 격리, FD 상한 등 단계별로 문장으로 적어 두면 디버깅 비용이 줄어듭니다.
결정성: 순수 층과 시간·네트워크·스케줄에 의존하는 층을 분리해야 테스트와 장애 분석이 쉬워집니다.
경계 비용: 직렬화, 인코딩, syscall 횟수, 락 경합, 할당·GC, 캐시 미스를 의심 목록에 둡니다.
백프레셔: 생산자가 소비자보다 빠를 때 버퍼·큐·스트림에서 속도를 줄이는 신호를 어디에 둘지 정의합니다.

프로덕션 운영 패턴

영역	운영 관점 질문
관측성	요청 단위 상관 ID, 에러율·지연 p95/p99, 의존성 타임아웃·재시도가 대시보드에 보이는가
안전성	입력 검증·권한·비밀·감사 로그가 코드 경로마다 일관적인가
신뢰성	재시도는 멱등 연산에만 적용되는가, 서킷 브레이커·백오프·DLQ가 있는가
성능	캐시·배치 크기·커넥션 풀·인덱스·백프레셔가 데이터 규모에 맞는가
배포	롤백 룬북, 카나리/블루그린, 마이그레이션·피처 플래그가 문서화되어 있는가
용량	피크 트래픽·디스크·FD·스레드 풀 상한을 주기적으로 검증하는가

스테이징은 데이터 양·네트워크 RTT·동시성을 프로덕션에 가깝게 맞출수록 재현율이 올라갑니다.

확장 예시: 엔드투엔드 미니 시나리오

앞선 본문 주제(「C++ Algorithm Heap | ‘힙 알고리즘’ 가이드」)를 배포·운영 흐름에 맞춰 옮긴 체크리스트입니다. 도메인에 맞게 단계 이름만 바꿔 적용할 수 있습니다.

입력 계약 고정: 스키마·버전·최대 페이로드·타임아웃·에러 코드를 경계에 둔다.
핵심 경로 계측: 요청 ID, 단계별 지연, 외부 호출 결과 코드를 로그·메트릭·트레이스에서 한 흐름으로 본다.
실패 주입: 의존성 타임아웃·5xx·부분 데이터·락 대기를 스테이징에서 재현한다.
호환·롤백: 설정/마이그레이션/클라이언트 버전을 되돌릴 수 있는지 확인한다.
부하 후 검증: 피크 대비 p95/p99, 에러율, 리소스 상한, 알림 임계값을 점검한다.

handle(request):
  ctx = newCorrelationId()
  validated = validateSchema(request)
  authorize(validated, ctx)
  result = domainCore(validated)
  persistOrEmit(result, idempotentKey)
  recordMetrics(ctx, latency, outcome)
  return result

문제 해결(Troubleshooting)

증상	가능 원인	조치
간헐적 실패	레이스, 타임아웃, 외부 의존성, DNS	최소 재현 스크립트, 분산 트레이스·로그 상관관계, 재시도·서킷 설정 점검
성능 저하	N+1, 동기 I/O, 락 경합, 과도한 직렬화, 캐시 미스	프로파일러·APM으로 핫스팟 확인 후 한 가지씩 제거
메모리 증가	캐시 무제한, 구독/리스너 누수, 대용량 버퍼, 커넥션 미반납	상한·TTL·힙/FD 스냅샷 비교
빌드·배포만 실패	환경 변수, 권한, 플랫폼 차이, lockfile	CI 로그와 로컬 diff, 런타임·이미지 버전 핀
설정 불일치	프로필·시크릿·기본값, 리전	스키마 검증된 설정 단일 소스와 배포 매트릭스 표준화
데이터 불일치	비멱등 재시도, 부분 쓰기, 캐시 무효화 누락	멱등 키·아웃박스·트랜잭션 경계 재검토

권장 순서: (1) 최소 재현 (2) 최근 변경 범위 축소 (3) 환경·의존성 차이 (4) 관측으로 가설 검증 (5) 수정 후 회귀·부하 테스트.

배포 전에는 git add → git commit → git push 후 npm run deploy 순서를 권장합니다.

이 글이 도움이 되셨나요?

여러분의 피드백은 더 나은 콘텐츠를 만드는 데 도움이 됩니다

문제가 있거나 개선 제안이 있으시면 연락처로 알려주세요.

Keyboard Shortcuts