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