pop_heap
범위에서 마지막 다음 위치에 힙 앞에서 가장 큰 요소를 제거 하 고 힙의 나머지 요소에서 새 폼.
template<class RandomAccessIterator>
void pop_heap(
RandomAccessIterator _First,
RandomAccessIterator _Last
);
template<class RandomAccessIterator, class BinaryPredicate>
void pop_heap(
RandomAccessIterator _First,
RandomAccessIterator _Last,
BinaryPredicate _Comp
);
매개 변수
_First
힙의 위치를 첫 번째 요소의 주소를 지정 하는 임의 액세스 반복기입니다._Last
위치 하나 최종 요소 과거 힙의 주소는 임의 액세스 반복기입니다._Comp
한 요소가 다른 보다 작은 것이 정의 조건자 함수의 사용자 정의 개체입니다.두 인수를 사용 하 고 반환 하는 이진 술 부 true 만족 스 러 우면 및 거짓 만족 하지 않을 때.
설명
pop_heap 알고리즘에 의해 수행 되는 작업의 역입니다는 push_heap 알고리즘을 범위의 마지막 다음 위치에 있는 요소를 추가 합니다 힙 힙에 추가 되는 요소 요소에 힙 보다 큰 경우에는 범위에서 이전 요소로 구성 합니다.
힙 두 가지 속성이 있습니다.
첫 번째 요소는 항상 가장입니다.
요소 추가 또는 로그 시간에 제거할 수 있습니다.
힙 우선 순위 큐를 구현 하는 이상적인 방법 이며 표준 템플릿 라이브러리 컨테이너 어댑터 구현에 사용 되는 priority_queue 클래스.
참조 범위 유효 해야 합니다. 모든 포인터는 dereferenceable 이어야 하며 마지막 위치에서 첫 번째 접근할 시퀀스 내에서 증분 합니다.
범위 끝에 새로 추가한 요소를 제외한 힙 이어야 합니다.
복잡 한 로그 최대 로그 요구 됩니다 (_Last – _First) 비교 합니다.
예제
// alg_pop_heap.cpp
// compile with: /EHsc
#include <vector>
#include <algorithm>
#include <functional>
#include <iostream>
int main( ) {
using namespace std;
vector <int> v1;
vector <int>::iterator Iter1, Iter2;
int i;
for ( i = 1 ; i <= 9 ; i++ )
v1.push_back( i );
// Make v1 a heap with default less than ordering
random_shuffle( v1.begin( ), v1.end( ) );
make_heap ( v1.begin( ), v1.end( ) );
cout << "The heaped version of vector v1 is ( " ;
for ( Iter1 = v1.begin( ) ; Iter1 != v1.end( ) ; Iter1++ )
cout << *Iter1 << " ";
cout << ")." << endl;
// Add an element to the back of the heap
v1.push_back( 10 );
push_heap( v1.begin( ), v1.end( ) );
cout << "The reheaped v1 with 10 added is ( " ;
for ( Iter1 = v1.begin( ) ; Iter1 != v1.end( ) ; Iter1++ )
cout << *Iter1 << " ";
cout << ")." << endl;
// Remove the largest element from the heap
pop_heap( v1.begin( ), v1.end( ) );
cout << "The heap v1 with 10 removed is ( " ;
for ( Iter1 = v1.begin( ) ; Iter1 != v1.end( ) ; Iter1++ )
cout << *Iter1 << " ";
cout << ")." << endl << endl;
// Make v1 a heap with greater-than ordering with a 0 element
make_heap ( v1.begin( ), v1.end( ), greater<int>( ) );
v1.push_back( 0 );
push_heap( v1.begin( ), v1.end( ), greater<int>( ) );
cout << "The 'greater than' reheaped v1 puts the smallest "
<< "element first:\n ( " ;
for ( Iter1 = v1.begin( ) ; Iter1 != v1.end( ) ; Iter1++ )
cout << *Iter1 << " ";
cout << ")." << endl;
// Application of pop_heap to remove the smallest element
pop_heap( v1.begin( ), v1.end( ), greater<int>( ) );
cout << "The 'greater than' heaped v1 with the smallest element\n "
<< "removed from the heap is: ( " ;
for ( Iter1 = v1.begin( ) ; Iter1 != v1.end( ) ; Iter1++ )
cout << *Iter1 << " ";
cout << ")." << endl;
}
샘플 출력
The heaped version of vector v1 is ( 9 5 8 4 1 6 7 2 3 ).
The reheaped v1 with 10 added is ( 10 9 8 4 5 6 7 2 3 1 ).
The heap v1 with 10 removed is ( 9 5 8 4 1 6 7 2 3 10 ).
The 'greater than' reheaped v1 puts the smallest element first:
( 0 1 6 3 2 8 7 4 9 10 5 ).
The 'greater than' heaped v1 with the smallest element
removed from the heap is: ( 1 2 6 3 5 8 7 4 9 10 0 ).
요구 사항
헤더: <algorithm>
네임 스페이스: std