HOWTO · C++
C++에서 STL 힙 알고리즘 사용
이 기사에서는 C++에서 STL 힙 알고리즘을 활용하는 방법을 소개합니다.
이 페이지의 내용
C++ STL 힙 알고리즘을 사용하면 std::vector의 범위를 최대 힙으로 만들거나 정렬하거나, 가장 큰 값을 끝으로 옮길 수 있습니다. std::pop_heap은 값을 옮길 뿐이므로 벡터에서 실제로 제거하려면 별도로 지워야 합니다.
std::make_heap 함수로 범위를 힙으로 변환하기
힙은 부모와 자식 사이의 규칙을 만족하도록 배열한 범위입니다. 기본 비교를 사용하면 std::make_heap은 최대 힙을 만듭니다. 즉, 각 부모는 자식보다 크거나 같고 가장 큰 값은 맨 앞에 놓입니다. 벡터로 구현한 이진 힙에서 인덱스 i에 있는 원소의 자식은 해당 위치가 범위 안에 있을 때 2 * i + 1과 2 * i + 2에 있습니다. 최소 힙을 만들려면 std::greater<int>와 같은 다른 비교 함수를 사용합니다.
std::make_heap은 힙 속성을 만족하도록 원소를 재배열하지만, 범위 전체를 정렬하지는 않습니다. 같은 힙 속성을 만족하는 배열 방식은 여러 가지이므로, 호출 후의 특정 원소 순서를 가정하지 말고 맨 앞의 값과 부모·자식 간 비교에 의존해야 합니다.
다음 독립 실행형 예제는 힙을 만들고 부모·자식 규칙을 확인합니다. 예제는 성공적으로 실행되었으며, 아래에 관찰된 출력이 나옵니다. 출력 블록은 바이트 그대로 보존되므로 그 안의 레이블은 영어로 표시됩니다.
#include <algorithm>
#include <cstddef>
#include <iostream>
#include <vector>
int main() {
std::vector<int> values{11, 82, 39, 72, 51, 32, 91};
std::make_heap(values.begin(), values.end());
bool is_max_heap = true;
for (std::size_t child = 1; child < values.size(); ++child) {
const std::size_t parent = (child - 1) / 2;
if (values[parent] < values[child]) {
is_max_heap = false;
break;
}
}
std::cout << "max-heap: " << std::boolalpha << is_max_heap << '\n';
std::cout << "top: " << values.front() << '\n';
}
max-heap: true
top: 91
맨 앞의 원소가 힙의 최상위 값입니다. 벡터의 나머지 원소 순서는 힙 속성만 만족하면 되므로 오름차순이나 내림차순 목록으로 간주하면 안 됩니다.
std::sort_heap 함수로 힙 범위 정렬하기
이미 힙 속성을 만족하는 범위에 std::sort_heap을 호출합니다. 기본 비교를 사용하면 범위가 오름차순으로 재배열됩니다. 정렬 후에는 범위가 더 이상 힙 속성을 만족하지 않으므로, 전체 범위에 힙 연산을 다시 적용하기 전에 std::make_heap을 호출해야 합니다.
예를 들어 std::make_heap(values.begin(), values.end())를 호출한 뒤 std::sort_heap(values.begin(), values.end())를 호출하면 같은 범위를 정렬할 수 있습니다. 기본 비교에서는 오름차순으로 정렬됩니다.
비교자를 받는 오버로드에는 정렬 기준을 정의하는 함수나 함수 객체를 전달할 수 있습니다. 힙을 만들고 정렬할 때 같은 비교 기준을 사용하세요. 예를 들어 std::greater<int>로 만든 힙은 같은 비교자를 사용해 정렬해야 합니다. 오름차순 결과가 목적이라면 기본 오버로드를 사용하면 됩니다.
std::pop_heap 함수로 힙에서 다음 원소를 제거하기
std::pop_heap은 최상위 값을 범위의 마지막 위치로 옮기고, 그 앞부분의 힙 속성을 복원합니다. 벡터의 크기는 바뀌지 않습니다. 컨테이너에서 해당 값을 제거하려면 std::pop_heap을 호출한 다음 pop_back()을 호출하세요.
원소를 추가하려면 벡터 끝에 값을 넣고 std::push_heap을 호출합니다. 새로 추가한 원소를 제외한 기존 범위가 먼저 힙이어야 하며, std::push_heap은 원소가 추가된 전체 범위의 힙 속성을 복원합니다. 두 알고리즘 모두 해당 힙의 정렬 기준과 같은 비교자를 사용해야 합니다.
다음 독립 실행형 예제는 최상위 값이 옮겨졌는지 확인하고, 그 값을 별도로 지운 다음, 힙 속성을 유지하면서 새 값을 추가합니다. 예제는 성공적으로 실행되었으며, 아래에 관찰된 출력이 나옵니다. 출력 블록은 바이트 그대로 보존되므로 그 안의 레이블은 영어로 표시됩니다.
#include <algorithm>
#include <iostream>
#include <vector>
int main() {
std::vector<int> values{11, 82, 39, 72, 51, 32, 91};
std::make_heap(values.begin(), values.end());
std::pop_heap(values.begin(), values.end());
std::cout << "moved top: " << values.back() << '\n';
values.pop_back();
values.push_back(95);
std::push_heap(values.begin(), values.end());
std::cout << "new top: " << values.front() << '\n';
}
moved top: 91
new top: 95
std::pop_heap을 호출한 뒤에는 마지막 원소 직전까지의 앞부분이 재사용할 힙입니다. pop_back()으로 마지막 값을 지우면 벡터 전체가 다시 그 힙 범위가 됩니다. 이 속성을 먼저 보존하지 않고 원소를 추가하면 std::push_heap의 선행 조건을 만족하지 않습니다.