algorithm_sort_heap
algorithm_sort_heap (힙 정렬)
std::sort_heap는 대상 범위가 나타내는 힙을 정렬된 범위로 변환해요. 정렬 후에는 힙 성질이 유지되지 않아요.
출처: cppreference
본문
std::sort_heap는 대상 범위 [first, last)가 나타내는 힙을 정렬된 범위로 변환해요. 힙 성질은 더 이상 유지되지 않아요. <algorithm> 헤더에 정의되어 있어요.
template< class RandomIt >
void sort_heap( RandomIt first, RandomIt last );
template< class RandomIt, class Compare >
void sort_heap( RandomIt first, RandomIt last, Compare comp );
- 1번 오버로드 — 대상 범위가
operator<(즉std::less{})를 기준으로 정렬돼요. - 2번 오버로드 — 대상 범위가 비교 함수
comp를 기준으로 정렬돼요.
대상 범위가 원래 힙을 나타내지 않으면 동작이 정의되지 않아요.
복잡도 (Complexity)
N을 std::distance(first, last)라고 하면 𝓞(N·log N)번의 비교가 최대로 필요해요.
예제 (Example)
#include <algorithm>
#include <iostream>
#include <vector>
int main()
{
std::vector<int> v{3, 1, 4, 1, 5, 9};
std::make_heap(v.begin(), v.end());
std::sort_heap(v.begin(), v.end());
for (int x : v) std::cout << x << ' ';
std::cout << '\n';
}
출력:
1 1 3 4 5 9