Этот сайт использует cookies. Продолжение работы с сайтом означает, что Вы согласны!
Работа с двоичной кучей
Двоичная куча — это структура данных, позволяющая быстро добавлять и извлекать элемент с максимальным приоритетом, например, максимальным значением. Для работы с двоичной кучей предназначены следующие функции (вместо этих функций можно воспользоваться классом priority_queue
, который мы рассматривали в разд. 17.6):
make_heap()
— образует кучу из элементов диапазона междуfirst
иlast
. По умолчанию сравнение производится с помощью оператора<
. В параметреcomp
можно указать пользовательскую функцию сравнения двух элементов. Формат функции:
#include <algorithm>
void make_heap(first, last[, comp]);
Пример:
std::vector<int> arr = {1, 2, 3, 4, 5};
std::make_heap(arr.begin(), arr.end());
for (int &el : arr) std::cout << el << ' ';
std::cout << std::endl; // 5 4 3 1 2
// Получаем элемент с максимальным приоритетом
std::cout << arr.front() << std::endl; // 5
push_heap()
— добавляет последний элемент из диапазона междуfirst
иlast
в кучу из диапазона междуfirst
иlast-1
. По умолчанию сравнение производится с помощью оператора<
. В параметреcomp
можно указать пользовательскую функцию сравнения двух элементов. Формат функции:
#include <algorithm>
void push_heap(first, last[, comp]);
Пример добавления элемента в кучу:
arr.push_back(6);
std::push_heap(arr.begin(), arr.end());
for (int &el : arr) std::cout << el << ' ';
std::cout << std::endl; // 6 4 5 1 2 3
// Получаем элемент с максимальным приоритетом
std::cout << arr.front() << std::endl; // 6
pop_heap()
— перемещает элемент с максимальным приоритетом из кучи в конец диапазона и переупорядочивает диапазон междуfirst
иlast-1
. Таким образом элемент исключается из кучи и может быть удален, например, с помощью методаpop_back()
. По умолчанию сравнение производится с помощью оператора<
. В параметреcomp
можно указать пользовательскую функцию сравнения двух элементов. Формат функции:
#include <algorithm>
void pop_heap(first, last[, comp]);
Пример удаления элемента из кучи:
std::pop_heap(arr.begin(), arr.end());
arr.pop_back();
for (int &el : arr) std::cout << el << ' ';
std::cout << std::endl; // 5 4 3 1 2
// Получаем элемент с максимальным приоритетом
std::cout << arr.front() << std::endl; // 5
is_heap()
— возвращает значениеtrue
, если диапазон междуfirst
иlast
образует кучу, иfalse
— в противном случае. По умолчанию сравнение производится с помощью оператора<
. В параметреcomp
можно указать пользовательскую функцию сравнения двух элементов. Формат функции:
#include <algorithm>
bool is_heap(first, last[, comp]);
Пример проверки:
std::cout << std::boolalpha;
std::cout << std::is_heap(arr.begin(), arr.end())
<< std::endl; // true
is_heap_until()
— возвращает итератор, указывающий на первый элемент из диапазона междуfirst
иlast
, который не следует в порядке, образующем кучу. Если диапазон образует кучу, то функция вернет итераторlast
. По умолчанию сравнение производится с помощью оператора<
. В параметреcomp
можно указать пользовательскую функцию сравнения двух элементов. Формат функции:
#include <algorithm>
iterator is_heap_until(first, last[, comp]);
Пример:
auto it = std::is_heap_until(arr.begin(), arr.end());
if (it == arr.end()) {
std::cout << "heap" << std::endl; // heap
}
sort_heap()
— преобразует кучу в отсортированную последовательность в порядке возрастания. По умолчанию сравнение производится с помощью оператора<
. В параметреcomp
можно указать пользовательскую функцию сравнения двух элементов. Формат функции:
#include <algorithm>
void sort_heap(first, last[, comp]);
Пример:
std::sort_heap(arr.begin(), arr.end());
for (int &el : arr) std::cout << el << ' ';
std::cout << std::endl; // 1 2 3 4 5
std::cout << std::is_heap(arr.begin(), arr.end())
<< std::endl; // false
Реквизиты
ЮMoney (Yandex-деньги): 410011140483022
ПАО Сбербанк:
Счет: 40817810855006152256
Реквизиты банка:
Наименование: СЕВЕРО-ЗАПАДНЫЙ БАНК ПАО СБЕРБАНК
Корреспондентский счет: 30101810500000000653
БИК: 044030653
КПП: 784243001
ОКПО: 09171401
ОКОНХ: 96130
Скриншот реквизитов