algorithm_make_heap
algorithm_make_heap (힙 생성)
std::make_heap는 대상 범위 [first, last)를 힙으로 만들어요. 범위 안의 요소를 재배열해 최대 힙 성질을 만족시켜요.
출처: cppreference
본문
std::make_heap는 대상 범위 [first, last)로부터 힙을 구성해요. <algorithm> 헤더에 정의되어 있어요.
template< class RandomIt >
void make_heap( RandomIt first, RandomIt last );
template< class RandomIt, class Compare >
void make_heap( RandomIt first, RandomIt last, Compare comp );
- 1번 오버로드 —
operator<(즉std::less{})를 기준으로 힙을 구성해요. - 2번 오버로드 — 비교 함수
comp를 기준으로 힙을 구성해요.
복잡도 (Complexity)
N을 std::distance(first, last)라고 하면 최대 3·N번의 비교가 필요해요.
예제 (Example)
#include <algorithm>
#include <iostream>
#include <vector>
int main()
{
std::vector<int> v{6, 1, 5, 3, 8, 2};
std::make_heap(v.begin(), v.end());
std::cout << "heap: ";
for (int x : v) std::cout << x << ' ';
std::cout << "\nmax: " << v.front() << '\n';
}
출력 예:
heap: 8 6 5 3 1 2
max: 8