C++에서 STL 힙 알고리즘 사용
이 기사에서는 C++에서 STL 힙 알고리즘을 활용하는 방법을 보여줍니다.
std::make_heap함수를 사용하여 범위를 힙으로 변환
std::make_heap함수는 STL 알고리즘으로 제공되며 주어진 범위에서 이진 힙 데이터 구조를 구성하는 데 사용할 수 있습니다. 일반적으로 힙 데이터 구조는 트리 기반이며 두 가지 일반적인 유형은 최대 힙 및 최소 힙으로 알려져 있습니다.
최대 힙에서 모든 하위 노드의 경우 상위 노드의 키가 하위 키보다 크거나 같습니다. 반면에 부모의 키는 자녀의 키보다 작습니다. 이제make_heap함수로 구성된 힙 구조는 이진 트리 데이터 구조와 유사한 이진 힙입니다. 힙은 대수 시간으로 수행 할 수있는 요소 삽입 및 제거 작업에 효율적입니다.
다음 예제는std::vector프로세스를 힙으로 변환 한 다음 일반적인printVector함수를 사용하여 내용을 인쇄하는 방법을 보여줍니다. 요소의 순서는 약간 신비합니다. 실제로 첫 번째 요소가 루트 키 값인 이진 트리 구조로 읽을 수 있습니다.
이진 트리의 모든 노드에 대해 최대 두 개의 하위 항목 만 있기 때문에82및39는 하위 항목으로 루트를 따릅니다. 다음 두 요소는82의 하위 노드이고 다른 두 요소는39아래에 있습니다. 이 계층은 부모 요소가 자식보다 크거나 같은 키를 갖는 최대 힙 속성을 충족합니다.
#include <algorithm>
#include <iostream>
#include <vector>
using std::cout;
using std::endl;
using std::string;
using std::vector;
template <typename T>
void printVector(const vector<T> &vec) {
for (auto &i : vec) {
cout << i << "; ";
}
cout << endl;
}
int main() {
vector<int> vec1{11, 82, 39, 72, 51, 32, 91};
cout << "vec1 original: ";
printVector(vec1);
std::make_heap(vec1.begin(), vec1.end());
cout << "vec1 make_heap: ";
printVector(vec1);
return EXIT_SUCCESS;
}
출력:
vec1 original: 11; 82; 39; 72; 51; 32; 91;
vec1 make_heap: 91; 82; 39; 72; 51; 32; 11;
std::sort_heap함수를 사용하여 힙 범위 정렬
std::sort_heap함수를 사용하여std::make_heap함수를 사용하여 이전에 변환 된 범위를 정렬 할 수 있습니다. 두 개의 반복기 인수 만 취하는std::sort_heap함수의 단순한 오버로드는 rang을 오름차순으로 정렬합니다. 함수의 다른 오버로드는bool cmp(const Type1 &a, const Type2 &b);시그니처를 사용하여 비교 함수의 세 번째 인수를 허용 할 수 있습니다. 범위가 정렬 된 후에는 더 이상 힙 속성이 없습니다.
#include <algorithm>
#include <iostream>
#include <vector>
using std::cout;
using std::endl;
using std::string;
using std::vector;
template <typename T>
void printVector(const vector<T> &vec) {
for (auto &i : vec) {
cout << i << "; ";
}
cout << endl;
}
int main() {
vector<int> vec1{11, 82, 39, 72, 51, 32, 91};
std::make_heap(vec1.begin(), vec1.end());
printVector(vec1);
std::sort_heap(vec1.begin(), vec1.end());
printVector(vec1);
return EXIT_SUCCESS;
}
출력:
91; 82; 39; 72; 51; 32; 11;
11; 32; 39; 51; 72; 82; 91;
std::pop_heap함수를 사용하여 힙에서 다음 요소 제거
힙 구조는 일반적으로 빠른 요소 삽입 및 제거 작업을 지원합니다. std::push_heap및std::pop_heap함수는 해당 힙 범위에 대해 이러한 작업을 수행합니다. std::push_heap명령이 힙 범위에서 호출되면 첫 번째 요소가 마지막 위치로 교체되고 나머지 요소로 새 힙이 구성됩니다. 힙은 기본 매개 변수에 따라 최대 힙으로 구성됩니다. 선택적인 비교 함수를 세 번째 인수로 전달하여 그에 따라 힙 계층을 수정할 수 있습니다.
#include <algorithm>
#include <iostream>
#include <vector>
using std::cout;
using std::endl;
using std::string;
using std::vector;
template <typename T>
void printVector(const vector<T> &vec) {
for (auto &i : vec) {
cout << i << "; ";
}
cout << endl;
}
int main() {
vector<int> vec1{11, 82, 39, 72, 51, 32, 91};
std::make_heap(vec1.begin(), vec1.end());
printVector(vec1);
std::pop_heap(vec1.begin(), vec1.end());
printVector(vec1);
return EXIT_SUCCESS;
}
출력:
91; 82; 39; 72; 51; 32; 11;
82; 72; 39; 11; 51; 32; 91;
Founder of DelftStack.com. Jinku has worked in the robotics and automotive industries for over 8 years. He sharpened his coding skills when he needed to do the automatic testing, data collection from remote servers and report creation from the endurance test. He is from an electrical/electronics engineering background but has expanded his interest to embedded electronics, embedded programming and front-/back-end programming.
LinkedIn Facebook