pop_heap
pop_heap (힙에서 최대 원소 제거)
힙의 최대 원소(맨 앞)를 범위 끝으로 옮기고, 나머지를 다시 힙으로 만드는 알고리즘이에요. <algorithm> 헤더에 있어요.
출처: cppreference
본문
pop_heap은 힙 [first, last)의 최대 원소를 last - 1 위치로 이동시키고, [first, last-1)을 다시 힙으로 만들어요.
template< class RandomIt >
void pop_heap( RandomIt first, RandomIt last ); // (1)
비교기 버전도 있어요.
template< class RandomIt, class Compare >
void pop_heap( RandomIt first, RandomIt last, Compare comp ); // (2)
-
operator<로, 2)comp로 비교해요.
- 복잡도: 최악의 경우
2·log(last - first)번의 비교.
전형적인 사용은 우선순위 큐처럼 "최대값을 꺼내기"예요.
std::vector<int> v{9, 5, 6, 1, 3};
std::make_heap(v.begin(), v.end()); // 힙 구성
std::pop_heap(v.begin(), v.end()); // 최대값 9를 끝으로
int top = v.back(); // 9
v.pop_back(); // 끝에서 제거
// 나머지가 다시 힙 상태
push_heap(삽입)과 짝을 이뤄 힙을 우선순위 큐처럼 관리해요. std::priority_queue가 내부적으로 사용하는 연산이에요.