std::pop_heap

Определено в заголовке `<algorithm>`
	(1)
template< class RandomIt > void pop_heap( RandomIt first, RandomIt last );		(до C++20)
template< class RandomIt > constexpr void pop_heap( RandomIt first, RandomIt last );		(с C++20)
	(2)
template< class RandomIt, class Compare > void pop_heap( RandomIt first, RandomIt last, Compare comp );		(до C++20)
template< class RandomIt, class Compare > constexpr void pop_heap( RandomIt first, RandomIt last, Compare comp );		(с C++20)

Меняет значения в позиции first и позиции last - 1 и преобразует поддиапазон [first, last - 1) в кучу. Это эквивалентно удалению первого элемента из кучи [first, last).

1) [first, last) является кучей относительно operator<.

2) [first, last) является кучей относительно comp.

Если [first, last) не является непустой кучей, поведение не определено.

Параметры

first, last	-	непустая куча для изменения
comp	-	объект-функция сравнения (т.е. объект, удовлетворяющий требованиям Compare), возвращающий `true` если первый аргумент меньше второго. Подпись функции сравнения должна быть эквивалентна следующему: `bool cmp(const Type1& a, const Type2& b);` Хотя подпись не обязательно должна иметь `const&`, функция не должна изменять передаваемые ей объекты и должна уметь принимать все значения типа (возможно, const) `Type1` и `Type2` независимо от категории значения (следовательно, `Type1&` не допускается, также как и `Type1` за исключением случаев, когда для `Type1` перемещение эквивалентно копированию(с C++11)). Типы Type1 и Type2 должны быть такими, чтобы объект типа RandomIt можно было разыменовать и затем неявно преобразовать в оба из них.
Требования к типу
-`RandomIt` должен удовлетворять требованиям ValueSwappable и LegacyRandomAccessIterator.
-Тип разыменованного `RandomIt` должен удовлетворять требованиям MoveAssignable и MoveConstructible.
-`Compare` должен удовлетворять требованиям Compare.

Возвращаемое значение

(нет)

Сложность

Дано \(\scriptsize N\)N как std::distance(first, last):

1) Не более \(\scriptsize 2 \cdot log(N)\)2·log(N) сравнений с использованием operator<.

2) Не более \(\scriptsize 2 \cdot log(N)\)2·log(N) применений функции сравнения comp.

Примечания

Куча относительно comp (max-куча) — это произвольный доступный диапазон [first, last) со следующими свойствами:

Дано \(\scriptsize N\)N как last - first, для всех целых i где \(\scriptsize 0 < i < N\)0 < i < N, bool(comp(first[(i - 1) / 2], first[i])) является false.
Новый элемент может быть добавлен с помощью std::push_heap, за время \(\scriptsize \mathcal{O}(\log N)\)𝓞(log N).
*first может быть удален с помощью std::pop_heap, за время \(\scriptsize \mathcal{O}(\log N)\)𝓞(log N).

Пример

#include <algorithm>
#include <iostream>
#include <string_view>
#include <type_traits>
#include <vector>
 
void println(std::string_view rem, auto const& 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 193	C++98	куча требовала `*first` быть наибольшим элементом	могут быть элементы, равные `*first`
LWG 1205	C++98	поведение было неясно, если `[first,` `last)` пусто	поведение в этом случае не определено
LWG 2166	C++98	требование к куче не достаточно точно соответствовало определению max-кучи	улучшенное требование

См. также

push_heap	добавляет элемент в max-кучу (функция-шаблон)
is_heap (C++11)	проверяет, является ли данный диапазон max-кучей (функция-шаблон)
is_heap_until (C++11)	находит наибольший поддиапазон, являющийся max-кучей (функция-шаблон)
make_heap	создает max-кучу из диапазона элементов (функция-шаблон)
sort_heap	преобразует max-кучу в диапазон элементов, отсортированных в порядке возрастания (функция-шаблон)
ranges::pop_heap (C++20)	удаляет наибольший элемент из max-кучи (niebloid)

© cppreference.com
Licensed under the Creative Commons Attribution-ShareAlike Unported License v3.0.
https://en.cppreference.com/w/cpp/algorithm/pop_heap