이 섹션에서는 C++ STL에 있는 힙 데이터 구조를 볼 것입니다. 이것은 힙에 더 빠른 입력을 허용하고 숫자를 검색하면 항상 가장 큰 숫자가 나옵니다. 즉, 매번 나머지 숫자 중 가장 큰 숫자가 튀어 나옵니다. 힙의 다른 요소는 구현에 따라 정렬됩니다. 힙 작업은 다음과 같습니다 -
-
make_heap() − 이것은 컨테이너의 범위를 힙으로 변환합니다.
-
앞() − 힙의 가장 큰 숫자인 첫 번째 요소를 반환합니다.
예
이해를 돕기 위해 다음 구현을 살펴보겠습니다. −
#include<bits/stdc++.h>
using namespace std;
int main() {
vector<int> heap = {33, 43, 53, 38, 28};
make_heap(heap.begin(), heap.end());
cout <<"Top element is : " << heap.front() << endl;
} 출력
Top element is : 53
-
push_heap() − 이는 힙에 요소를 삽입한 후 힙을 다시 힙화하는 데 도움이 됩니다. 힙의 크기는 1씩 증가합니다. 힙에 새 요소가 적절하게 배치됩니다.
-
팝_힙() − 이는 힙의 가장 큰 요소를 삭제한 후 힙을 다시 힙에 쌓는 데 도움이 됩니다. 힙의 크기는 1씩 감소합니다. 요소를 삭제한 후 힙 요소는 그에 따라 재구성됩니다.
예시
이해를 돕기 위해 다음 구현을 살펴보겠습니다. −
#include<bits/stdc++.h>
using namespace std;
int main() {
vector<int> heap = {33, 43, 53, 38, 28};
make_heap(heap.begin(), heap.end());
cout <<"Top element is : " << heap.front() << endl;
heap.push_back(60);
push_heap(heap.begin(), heap.end());
cout <<"Top element after insert : " << heap.front() << endl;
pop_heap(heap.begin(), heap.end());
heap.pop_back();
cout <<"Top element after deletion : " << heap.front() << endl;
} 출력
Top element is : 53 Top element after insert : 60 Top element after deletion : 53
-
sort_heap() :heapsorting 기법에 의해 heap element를 오름차순으로 정렬합니다.
예시(C++)
이해를 돕기 위해 다음 구현을 살펴보겠습니다. −
#include<bits/stdc++.h>
using namespace std;
int main() {
vector<int> heap = {33, 43, 53, 38, 28};
make_heap(heap.begin(), heap.end());
cout <<"Before Sort : ";
for (const auto &i : heap) {
cout << i << ' ';
}
sort_heap(heap.begin(), heap.end());
cout <<"\nAfter Sort : ";
for (const auto &i : heap) {
cout << i << ' ';
}
} 출력
Before Sort : 53 43 33 38 28 After Sort : 28 33 38 43 53
-
is_heap() − 컨테이너가 힙인지 여부를 확인하기 위해 사용합니다. 대부분의 구현에서 역으로 정렬된 컨테이너는 힙으로 처리됩니다. 이 함수는 이것이 힙이면 true 힙을 반환하고 그렇지 않으면 false를 반환합니다.
-
is_heap_until() − 컨테이너가 힙이 될 때까지 해당 위치의 반복자를 찾는 데 사용됩니다.
예
이해를 돕기 위해 다음 구현을 살펴보겠습니다. −
#include<bits/stdc++.h>
using namespace std;
int main() {
vector<int> heap = {33, 43, 53, 38, 28};
vector<int>::iterator iter;
is_heap(heap.begin(), heap.end()) ? cout <<"The is a heap ": cout <<"The is not a heap";
cout << endl;
cout < "Heapify" << endl;
make_heap(heap.begin(), heap.end());
is_heap(heap.begin(), heap.end()) ? cout <<"The is a heap ": cout <<"The is not a heap";
cout << endl;
vector<int>::iterator iter2 = is_heap_until(heap.begin(), heap.end());
cout <<"The heap elements are : ";
for (iter=heap.begin(); iter!=iter2; iter++)
cout << *iter <<" ";
} 출력
The is not a heap Heapify The is a heap The heap elements are : 53 43 33 38 28