sort_heap
sort_heap (힙 정렬 변환)
힙을 정렬된 범위로 변환하는 알고리즘이에요. <algorithm> 헤더에 있어요.
출처: cppreference
본문
sort_heap은 힙 [first, last)을 정렬된 비감소 범위로 변환해요.
template< class RandomIt >
void sort_heap( RandomIt first, RandomIt last ); // (1)
비교기 버전도 있어요.
template< class RandomIt, class Compare >
void sort_heap( RandomIt first, RandomIt last, Compare comp ); // (2)
- 복잡도: 최악의 경우
N·log N번의 비교. - 힙이 아니면 동작이 미정의예요.
std::vector<int> v{9, 5, 6, 1, 3};
std::make_heap(v.begin(), v.end());
std::sort_heap(v.begin(), v.end());
// v == {1,3,5,6,9} 정렬됨
힙을 정렬 순서로 바꾸는 함수예요. 힙 정렬(heapsort)의 마지막 단계에 해당해요. 어떤 알고리즘은 이 방식으로 정렬을 구현하기도 해요.