Работа с двоичной кучей

Двоичная куча — это структура данных, позволяющая быстро добавлять и извлекать элемент с максимальным приоритетом, например, максимальным значением. Для работы с двоичной кучей предназначены следующие функции (вместо этих функций можно воспользоваться классом 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

Учебник C++ (Qt Creator и MinGW)
Учебник C++ (Qt Creator и MinGW) в формате PDF

Помощь сайту

ЮMoney (Yandex-деньги): 410011140483022

ПАО Сбербанк:
Счет: 40817810855006152256
Реквизиты банка:
Наименование: СЕВЕРО-ЗАПАДНЫЙ БАНК ПАО СБЕРБАНК
Корреспондентский счет: 30101810500000000653
БИК: 044030653
КПП: 784243001
ОКПО: 09171401
ОКОНХ: 96130
Скриншот реквизитов