is_heap_until
is_heap_until (힙 성질이 깨지는 지점 찾기)
범위의 시작부터 힙 성질을 만족하는 가장 긴 접두 구간의 끝을 찾는 알고리즘이에요. <algorithm> 헤더에 있어요.
출처: cppreference
본문
is_heap_until은 [first, last)에서 힙 성질을 만족하는 가장 긴 접두 구간 [first, it)의 끝 it를 반환해요.
template< class RandomIt >
RandomIt is_heap_until( RandomIt first, RandomIt last ); // (1)
비교기 버전도 있어요.
template< class RandomIt, class Compare >
RandomIt is_heap_until( RandomIt first, RandomIt last, Compare comp ); // (2)
즉 it는 마지막으로 힙 성질을 유지하는 요소 다음을 가리켜요. [first, it)은 힙이고, it 이후부터는 힙 성질이 깨져요. 범위 전체가 힙이면 last를 반환해요.
std::vector<int> v{5, 4, 3, 1, 2, 9}; // 처음 4개는 힙, 2 다음에 9가 깨뜨림
auto it = std::is_heap_until(v.begin(), v.end());
// it는 9를 가리킴
전체가 힙인지(그러면 반환값 == last) 뿐 아니라 "어디까지 힙인지"를 알려줘요. 힙 정렬 상태의 손상을 진단할 때 유용해요.