std::pop_heap
cppreference.net에서
| 헤더 <algorithm>
|
||
template< class RandomIt >
void pop_heap( RandomIt first, RandomIt last );
|
에 정의됨 (1) | (C++20부터 constexpr) |
template< class RandomIt, class Compare >
void pop_heap( RandomIt first, RandomIt last, Compare comp );
|
(2) | (C++20부터 constexpr) |
위치 first의 값과 위치 last - 1의 값을 교체하고 부분 범위 [first, last - 1)를 힙으로 만듭니다. 이는 힙 [first, last)에서 첫 번째 요소를 제거하는 효과를 냅니다.
1)
[first, last)는 operator<(C++20까지)std::less{}(C++20부터)에 대해 힙입니다.2)
[first, last)는 comp에 대해 힙입니다.다음 조건 중 하나라도 만족하면 동작이 정의되지 않습니다:
[first,last)가 비어 있습니다.[first,last)는 해당 비교자에 대한 힙이 아닙니다.
|
(C++11까지) |
|
(C++11부터) |
매개변수
| first, last | - | 수정할 (루트 항목 추출) 비어 있지 않은 이진 힙 범위의 요소를 정의하는 반복자 쌍 |
| comp | - | 비교 함수 객체 (즉, Compare의 요구사항을 만족하는 객체)로, 첫 번째 인수가 두 번째 인수보다 true작으면 를 반환합니다.비교 함수의 시그니처는 다음과 동등해야 합니다:
시그니처에 |
| 타입 요구사항 | ||
-RandomIt는 LegacyRandomAccessIterator의 요구사항을 충족해야 합니다.
| ||
-Compare는 Compare의 요구사항을 충족해야 합니다.
| ||
복잡도
주어진 N이 std::distance(first, last)일 때:
1) 최대 2log(N)번의
operator<(C++20까지)std::less{}(C++20부터) 비교.2) 최대 2log(N)번의 비교 함수
comp 적용.예시
이 코드 실행
#include <algorithm>
#include <iostream>
#include <string_view>
#include <type_traits>
#include <vector>
void println(std::string_view rem, const auto& v)
{
std::cout << rem;
if constexpr (std::is_scalar_v<std::decay_t<decltype(v)>>)
std::cout << v;
else
for (int e : v)
std::cout << e << ' ';
std::cout << '\n';
}
int main()
{
std::vector<int> v{3, 1, 4, 1, 5, 9};
std::make_heap(v.begin(), v.end());
println("after make_heap: ", v);
std::pop_heap(v.begin(), v.end()); // moves the largest to the end
println("after pop_heap: ", v);
int largest = v.back();
println("largest element: ", largest);
v.pop_back(); // actually removes the largest element
println("after pop_back: ", v);
}
출력:
after make_heap: 9 5 4 1 1 3
after pop_heap: 5 3 4 1 1 9
largest element: 9
after pop_back: 5 3 4 1 1
결함 보고서
다음 동작 변경 결함 보고서가 이전에 게시된 C++ 표준에 소급하여 적용되었습니다.
| DR | 적용 대상 | 게시된 동작 | 올바른 동작 |
|---|---|---|---|
| LWG 1205 | C++98 | [first, last)가 비어 있을 때 동작이 명확하지 않음
|
이 경우 동작이 정의되지 않음 |
참고 항목
| 최대 힙에 요소를 추가합니다 (함수 템플릿 & 알고리즘 함수 객체) | |
(C++20) |
|
(C++11) |
주어진 범위가 최대 힙인지 확인합니다 (함수 템플릿 & 알고리즘 함수 객체) |
(C++20) |
|
(C++11) |
최대 힙인 가장 큰 부분 범위를 찾습니다 (함수 템플릿 & 알고리즘 함수 객체) |
(C++20) |
|
| 요소 범위로 최대 힙을 만듭니다 (함수 템플릿 & 알고리즘 함수 객체) | |
(C++20) |
|
| 최대 힙을 오름차순으로 정렬된 요소 범위로 바꿉니다 (함수 템플릿 & 알고리즘 함수 객체) | |
(C++20) |
|
(C++20) |
최대 힙에서 가장 큰 요소를 제거합니다 (알고리즘 함수 객체) |