make_heap
make_heap (범위를 힙으로)
범위를 최대 힙(max-heap)으로 재배열하는 알고리즘이에요. <algorithm> 헤더에 있어요.
출처: cppreference
본문
make_heap은 범위 [first, last)를 최대 힙으로 재배열해요.
template< class RandomIt >
void make_heap( RandomIt first, RandomIt last ); // (1)
비교기 버전도 있어요.
template< class RandomIt, class Compare >
void make_heap( RandomIt first, RandomIt last, Compare comp ); // (2)
-
operator<로, 2)comp로 비교해요.
- 복잡도: 최악의 경우
3·(last - first)번의 비교(선형).
힙은 부모가 자식보다 크거나 같도록 배열로 표현된 완전 이진 트리예요. 최대 원소는 항상 first에 있어요.
std::vector<int> v{3, 1, 4, 1, 5, 9, 2, 6};
std::make_heap(v.begin(), v.end()); // 최대 힙이 됨, 최대값 9가 v[0]
힙을 만든 뒤 push_heap/pop_heap으로 우선순위 큐처럼 다룰 수 있어요. 사실 std::priority_queue가 내부적으로 이 힙 연산들을 사용해요. sort_heap으로 힙을 정렬로 변환할 수도 있어요.