algorithm_pop_heap
algorithm_pop_heap (힙에서 최대 제거)
std::pop_heap는 힙의 첫 번째 요소(최대 요소)를 제거해서 [first, last - 1)을 다시 힙으로 유지해요. 보통 std::pop_back()과 함께 써요.
출처: cppreference
본문
std::pop_heap는 대상 범위 [first, last)가 나타내는 (비어 있지 않은) 힙에서 첫 번째 요소를 제거해요. first의 값과 last - 1의 값을 교환하고, 제거 후의 힙은 [first, last - 1)이 돼요. <algorithm> 헤더에 정의되어 있어요.
template< class RandomIt >
void pop_heap( RandomIt first, RandomIt last );
template< class RandomIt, class Compare >
void pop_heap( RandomIt first, RandomIt last, Compare comp );
- 1번 오버로드 — 힙이
operator<(즉std::less{})를 기준으로 구성되어 있어요. - 2번 오버로드 — 힙이 비교 함수
comp를 기준으로 구성되어 있어요.
[first, last)가 유효한 비어 있지 않은 힙이 아니면 동작이 정의되지 않아요.
복잡도 (Complexity)
N을 std::distance(first, last)라고 하면 𝓞(log N)번의 비교가 필요해요.
예제 (Example)
#include <algorithm>
#include <iostream>
#include <vector>
int main()
{
std::vector<int> v{1, 2, 3, 4, 5};
std::make_heap(v.begin(), v.end());
std::pop_heap(v.begin(), v.end());
int largest = v.back();
v.pop_back();
std::cout << "largest element: " << largest << '\n';
}