namespace std {
template <class RandomAccessIterator>
void pop_heap(RandomAccessIterator first,
RandomAccessIterator last); // (1) C++03
template <class RandomAccessIterator>
constexpr void pop_heap(RandomAccessIterator first,
RandomAccessIterator last); // (1) C++20
template <class RandomAccessIterator, class Compare>
void pop_heap(RandomAccessIterator first,
RandomAccessIterator last,
Compare comp); // (2) C++03
template <class RandomAccessIterator, class Compare>
constexpr void pop_heap(RandomAccessIterator first,
RandomAccessIterator last,
Compare comp); // (2) C++20
}
概要
ヒープ化されたイテレータ範囲[first, last)
の先頭と末尾を入れ替え、ヒープ範囲を作り直す
テンプレートパラメータ制約
RandomAccessIterator
はValueSwappable
の要件を満たしていること*first
の型はMoveConstructible
とMoveAssignable
の要件を満たしていること
事前条件
[first,last)
は空でないヒープであること
効果
first
にある値を last - 1
と交換し、その後 [first,last - 1)
が有効な heap となるように配置する。
戻り値
なし
計算量
最大で 2 * log(last - first)
回比較する
例
#include <iostream>
#include <vector>
#include <algorithm>
int main()
{
std::vector<int> v = {3, 1, 4};
std::make_heap(v.begin(), v.end());
// 最後尾要素を削除してヒープ化
std::pop_heap(v.begin(), v.end());
v.pop_back();
std::sort_heap(v.begin(), v.end());
std::for_each(v.begin(), v.end(), [](int x) {
std::cout << x << std::endl;
});
}
21
#include <iostream>
#include <vector>
#include <algorithm>
int main()
{
std::vector<int> v = {3, 1, 4};
std::make_heap(v.begin(), v.end());
// 最後尾要素を削除してヒープ化
std::pop_heap(v.begin(), v.end());
v.pop_back();
std::sort_heap(v.begin(), v.end());
std::for_each(v.begin(), v.end(), [](int x) {
std::cout << x << std::endl;
出力
1
3
実装例
template <class RandomAccessIterator>
void pop_heap(RandomAccessIterator first, RandomAccessIterator last)
{
using difference_type = typename std::iterator_traits<RandomAccessIterator>::difference_type;
using value_type = typename std::iterator_traits<RandomAccessIterator>::value_type;
--last;
difference_type len = last - first;
if (len > 0) {
value_type v = std::move(*last);
*last = std::move(*first);
difference_type p = 0;
for (difference_type c = 1; c < len; c = p * 2 + 1) {
if (c + 1 < len && first[c] < first[c + 1])
++c;
if (!bool(v < first[c]))
break;
first[p] = std::move(first[c]);
p = c;
}
first[p] = std::move(v);
}
}
template <class RandomAccessIterator, class Compare>
void pop_heap(RandomAccessIterator first, RandomAccessIterator last, Compare comp)
{
using difference_type = typename std::iterator_traits<RandomAccessIterator>::difference_type;
using value_type = typename std::iterator_traits<RandomAccessIterator>::value_type;
--last;
difference_type len = last - first;
if (len > 0) {
value_type v = std::move(*last);
*last = std::move(*first);
difference_type p = 0;
for (difference_type c = 1; c < len; c = p * 2 + 1) {
if (c + 1 < len && comp(first[c], first[c + 1]))
++c;
if (!bool(comp(v, first[c])))
break;
first[p] = std::move(first[c]);
p = c;
}
first[p] = std::move(v);
}
}