is_heap
is_heap (힙 성질 검사)
범위가 힙(heap) 성질을 만족하는지 검사하는 알고리즘이에요. <algorithm> 헤더에 있어요.
출처: cppreference
본문
is_heap은 범위 [first, last)가 최대 힙인지 검사해요.
template< class RandomIt >
bool is_heap( RandomIt first, RandomIt last ); // (1)
비교기 comp를 받는 버전도 있어요.
template< class RandomIt, class Compare >
bool is_heap( RandomIt first, RandomIt last, Compare comp ); // (2)
힙이란 부모가 자식보다 크거나 같도록(기본 operator< 기준) 배열로 표현된 완전 이진 트리 구조예요. std::make_heap, std::push_heap, std::pop_heap 등이 만든 상태와 일치하는지 확인할 때 써요.
std::vector<int> v{3, 1, 4, 1, 5};
std::make_heap(v.begin(), v.end());
bool ok = std::is_heap(v.begin(), v.end()); // true
- 반환 값:
[first, last)가 최대 힙이면true. - 복잡도:
last - first에 선형.
드물게, 힙 관련 연산 후 상태가 올바른지 디버깅·검증할 때 쓰는 알고리즘이에요.