ranges::push_heap
ranges::push_heap (힙에 삽입 — ranges)
힙의 끝에 새 원소를 추가하고 전체를 다시 힙으로 만드는 ranges 버전 알고리즘이에요. <algorithm> 헤더에 있어요.
출처: cppreference
본문
std::ranges::push_heap은 [first, last-1)이 힙이라고 가정하고, last - 1의 새 원소를 포함해 전체를 힙으로 만들어요.
namespace std::ranges {
template< class R, class Comp = ranges::less, class Proj = std::identity >
requires std::random_access_range<R> && std::sortable<ranges::iterator_t<R>, Comp, Proj>
constexpr ranges::borrowed_iterator_t<R> push_heap( R&& r, Comp comp = {}, Proj proj = {} );
}
- 복잡도: 최악의 경우
log N번의 비교.
std::vector<int> v{9, 5, 6, 1, 3};
std::ranges::make_heap(v);
v.push_back(10);
std::ranges::push_heap(v); // 힙 복구
우선순위 큐처럼 새 값을 삽입하는 ranges 버전이에요.