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