<algorithm> is_heap()

libstdc++: stl_heap.h Source File (gnu.org)

 

is_heap 함수의 기능은 주어진 컨테이너가 max heap인지 판단한다.

람다 함수에서 부등호 방향만 바꾸어주면 min heap인지 판단.

template<typename RandomAccessIterator>
RandomAccessIterator isHeapUntil(RandomAccessIterator first, RandomAccessIterator last)
{
	auto comp = [](RandomAccessIterator first, RandomAccessIterator last) {
		return *first < *last;
	};
	int dist = std::distance(first, last);
	return first + _isHeapUntil(first, dist, comp);
}

template<typename RandomAccessIterator, typename Compare>
int _isHeapUntil(RandomAccessIterator first, int dist, Compare& comp)
{
	int parent = 0;
	for (int child = 1; child < dist; ++child) {
		if (comp(first + parent, first + child))
			return child;
		if ((child & 1) == 0)
			++parent;
	}
	return dist;
}

template<typename RandomAccessIterator>
bool is_heap(RandomAccessIterator first, RandomAccessIterator last)
{
	return isHeapUntil(first, last) == last;
}