더북(TheBook)

힙을 저장한 컨테이너에 어떤 작업을 해서 힙을 깨트릴 수도 있으므로 STL에는 순차열이 힙인지 검사하는 방법도 있다.

if (std::is_heap(std::begin(numbers), std::end(numbers)))
  std::cout << "Great! We still have a heap.\n";
else
  std::cout << "Oh bother! We messed up the heap.\n";

is_heap() 함수는 지정된 범위가 힙이면 true를 반환한다. 여기서는 기본 비교 조건자 less<>의 인스턴스를 사용해 힙 순서를 점검한다. greater<> 인스턴스를 사용해 힙을 생성했다면 결과가 틀려진다. greater<>로 힙을 생성했을 때 올바른 결과를 얻으려면 다음과 같이 사용해야 한다.

std::is_heap(std::begin(numbers), std::end(numbers), std::greater<>()).

특정 범위까지만 힙인지 확인할 수 있는 검사 기능도 있다.

std::vector<double> numbers {2.5, 10.0, 3.5, 6.5, 8.0, 12.0, 1.5, 6.0};
std::make_heap(std::begin(numbers), std::end(numbers),
                                      std::greater<>()); // 결과: 1.5 6 2.5 6.5 8 12 3.5 10
std::pop_heap(std::begin(numbers), std::end(numbers),
                                      std::greater<>()); // 결과: 2.5 6 3.5 6.5 8 12 10 1.5
auto iter = std::is_heap_until(std::begin(numbers), std::end(numbers), std::greater<>());
if(iter != std::end(numbers))
  std::cout << "numbers is a heap up to " << *iter << std::endl;

is_heap_until() 함수는 범위에서 힙이 아닌 원소의 첫 번째 위치를 반환한다. 이 코드에서는 마지막 원소의 값 1.5만 출력되는데, 이는 pop_heap()을 호출한 이후에는 마지막 원소만 힙 순차열이 아니기 때문이다.

신간 소식 구독하기
뉴스레터에 가입하시고 이메일로 신간 소식을 받아 보세요.