6.5가 10이 아니라 6의 자식이므로 순차열의 마지막 원소가 된 것이고, 힙 구조에서는 이게 정상적인 모습이다.
가장 큰 원소를 제거하는 과정은 힙에 원소를 추가하는 과정과 비슷하지만, 방식은 정반대다. 먼저 pop_heap()을 호출하고, 그다음에 컨테이너에서 가장 큰 원소를 제거한다.
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)); // 결과: 12 10 3.5 6.5 8 2.5 1.5 6 std::pop_heap(std::begin(numbers), std::end(numbers)); // 결과: 10 8 3.5 6.5 6 2.5 1.5 12 numbers.pop_back(); // 결과: 10 8 3.5 6.5 6 2.5 1.5
pop_heap() 함수는 첫 번째 원소를 끝으로 보내고 끝으로 보낸 마지막 원소를 제외한 나머지 원소들로 힙을 만든다. 그다음에 vector의 pop_back() 멤버를 호출해서 마지막 원소를 제거한다. make_heap()에 비교 함수를 지정해 힙을 생성했다면 pop_heap()의 세 번째 인수에도 같은 비교 함수를 지정해야 한다.
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 numbers.pop_back(); // 결과: 2.5 6 3.5 6.5 8 12 10
pop_heap()에 비교 함수를 지정해야 하는 이유는 주석에 표시한 연산 결과에서 알 수 있다. pop_heap() 함수는 첫 번째 원소와 마지막 원소를 교환하는 게 아니다. begin(numbers)에서 end(numbers)-1까지의 범위에 있는 원소들의 순서를 재정리해서 힙 순서를 유지할 뿐이다. 이를 올바르게 수행하려면 pop_heap()에도 make_heap()에 사용한 것과 같은 비교 함수를 반드시 사용해야 한다.