Алгоритмы работы с данными, которые представлены по принципу «кучи» (heap). Примеры

---

Содержание

• 1. Алгоритм make_heap. Подготовить последовательность для использования в качестве «кучи»
• 2. Алгоритм push_heap. Добавить последний элемент в существующую «кучу»
• 3. Алгоритм pop_heap. Удалить наибольший элемент с начала кучи до позиции, которая следует за последней в диапазоне, а затем формирует новую кучу из оставшихся элементов
• 4. Алгоритм sort_heap. Сортировать числа в «куче»
• Связанные темы

---

Поиск на других ресурсах:

1. Загальні відомості про клас vector. Огляд методів класу

Клас vector представляє собою динамічний масив, розмір якого у програмі може змінюватись при необхідності. Цей клас є одним з найбільш універсальних та поширених у використанні при написанні програм на C++. Доступ до елементів класу здійснюється як до звичайного масиву з допомогою квадратних дужок [ ].

1. Алгоритм make_heap. Подготовить последовательность для использования в качестве «кучи»

Алгоритм make_heap имеет две перегруженные реализации, которые объявлены следующим образом

template <class RandomAccessIterator>
void make_heap(
  RandomAccessIterator first,
  RandomAccessIterator last );

template <class RandomAccessIterator, class BinaryPredicate>
void make_heap(
  RandomAccessIterator first,
  RandomAccessIterator last,
  BinaryPredicate pred );

здесь

• first – итератор произвольного доступа. Этот итератор указывает на первый элемент диапазона, который нужно конвертировать в «кучу»;
• last – итератор произвольного доступа. Этот итератор указывает на позицию следующую за последним элементом диапазона, который конвертируется в «кучу»;
• pred – бинарный предикат, задающий условие при котором один элемент меньше другого. Если условие выполняется, то предикат возвращает true, в противном случае возвращается false.

Пример.

#include <iostream>
#include <queue>
#include <vector>
#include <list>
#include <functional>
#include <algorithm>
using namespace std;

int main()
{
  // Алгоритм make_heap - Создать кучу на основе заданной последовательности.
  // В куче первый элемент является наибольшим (наименьшим) а также критерий сортировки
  // может быть определен бинарным предикатом.

  // 1. Использование алгоритма без предиката
  // 1.1. Объявить вектор и вывести его
  vector<int> V1 = { 2, 1, 3, 2, 4, 5, 2, 1, 3, 0 };

  vector<int>::iterator it = V1.begin();
  cout << "V1 => ";
  while (it != V1.end())
  {
    cout << *it << " ";
    it++;
  }
  cout << endl;

  // 1.2. Создать "кучу" (heap) из последовательности
  make_heap(V1.begin(), V1.end());

  // 1.3. Вывести опять V1
  cout << "V1 => ";

  for (int i : V1)
    cout << i << " ";
  cout << endl;

  // 2. Использование алгоритма со стандартным предикатом
  // 2.1. Объявить еще один вектор и вывести его
  vector<int> V2 = { 2, 1, 3, 2, 4, 5, 2, 1, 3, 0 };

  it = V2.begin();
  cout << "V2 => ";
  while (it != V2.end())
  {
    cout << *it << " ";
    it++;
  }
  cout << endl;

  // 2.2. Создать кучу на основе стандартного предиката less
  make_heap(V2.begin(), V2.end(), less<int>());

  // 2.3. Вывести вектор
  it = V2.begin();
  cout << "V2 => ";
  while (it != V2.end())
  {
    cout << *it << " ";
    it++;
  }
  cout << endl;
}

Результат

V1 => 2 1 3 2 4 5 2 1 3 0
V1 => 5 4 3 3 1 2 2 1 2 0
V2 => 2 1 3 2 4 5 2 1 3 0
V2 => 5 4 3 3 1 2 2 1 2 0

  ⇑

2. Алгоритм push_heap. Добавить последний элемент в существующую «кучу»

Алгоритм имеет две реализации

template <class RandomAccessIterator>
void push_heap(
  RandomAccessIterator first,
  RandomAccessIterator last );

template <class RandomAccessIterator, class BinaryPredicate>
void push_heap(
  RandomAccessIterator first,
  RandomAccessIterator last,
  BinaryPredicate pred);

здесь

• first, last – итераторы произвольного доступа, указывающие соответственно на первый и последний элементы диапазона, который рассматривается как потенциальная «куча»;
• pred – бинарный предикат, возвращающий true, если первый элемент меньше другого.

Пример.

#include <iostream>
#include <queue>
#include <vector>
#include <list>
#include <functional>
#include <algorithm>
using namespace std;

void PrintVector(vector<int>& V, string msg)
{
  cout << msg << " => ";
  for (int i : V)
    cout << i << " ";
  cout << endl;
}

int main()
{
  // Алгоритм push_heap - Добавить элемент в существующую кучу, куча изменяется.
  // В куче первый элемент является наибольшим (наименьшим) а также критерий сортировки
  // может быть определен бинарным предикатом.

  // 1. Использование алгоритма без предиката
  // 1.1. Объявить вектор и вывести его
  vector<int> V1 = { 2, 1, 3, 4 };
  PrintVector(V1, "V1");

  // 1.2. Создать "кучу" (heap) из последовательности
  make_heap(V1.begin(), V1.end());
  PrintVector(V1, "make_heap(V1)");

  // 1.3. Добавить элемент в последовательность и вывести последовательность снова
  V1.push_back(23);
  PrintVector(V1, "V1+1");

  // 1.4. Добавить элемент в существующую кучу
  push_heap(V1.begin(), V1.end());
  PrintVector(V1, "V1.push_heap");

  // 2. Использование алгоритма со стандартным предикатом greater
  // 2.1. Создать вектор
  vector<int> V2 = { 5, 9, 7, 3 };
  PrintVector(V2, "V2");

  // 2.2. Создать кучу
  make_heap(V2.begin(), V2.end());
  PrintVector(V2, "make_heap(V2)");

  // 2.3. Добавить элемент к последовательности V2
  V2.push_back(4);
  PrintVector(V2, "V2+1");

  // 2.4. Добавить элемент в существующую кучу - предикат greater
  push_heap(V2.begin(), V2.end(), greater<int>());
  PrintVector(V2, "push_heap(V2)");
}

Результат

V1 => 2 1 3 4
make_heap(V1) => 4 2 3 1
V1+1 => 4 2 3 1 23
V1.push_heap => 23 4 3 1 2
V2 => 5 9 7 3
make_heap(V2) => 9 5 7 3
V2+1 => 9 5 7 3 4
push_heap(V2) => 4 9 7 3 5

  ⇑

3. Алгоритм pop_heap. Удалить наибольший элемент с начала кучи до позиции, которая следует за последней в диапазоне, а затем формирует новую кучу из оставшихся элементов

Алгоритм pop_heap имеет два перегруженных варианта реализации, отличающихся отсутствием/наличием предиката:

template <class RandomAccessIterator>
void pop_heap(
  RandomAccessIterator first,
  RandomAccessIterator last);

template <class RandomAccessIterator, class BinaryPredicate>
void pop_heap(
  RandomAccessIterator first,
  RandomAccessIterator last,
  BinaryPredicate pred);

здесь

• first, last – итераторы произвольного доступа, указывающие соответственно на первый и последний элементы диапазона, который рассматривается как потенциальная «куча»;
• pred – бинарный предикат, возвращающий true, если первый элемент меньше другого.

Пример.

#include <iostream>
#include <queue>
#include <vector>
#include <list>
#include <functional>
#include <algorithm>
using namespace std;

void PrintVector(vector<int>& V, string msg)
{
  cout << msg << " => ";
  for (int i : V)
    cout << i << " ";
  cout << endl;
}

int main()
{
  // Алгоритм pop_heap - удалить наибольший элемент из кучи с ее дальнейшим переформированием.
  // В куче первый элемент является наибольшим (наименьшим) а также критерий сортировки
  // может быть определен бинарным предикатом.

  // 1. Использование алгоритма без предиката
  // 1.1. Объявить вектор и вывести его
  vector<int> V1 = { 2, 1, 3, 4 };
  PrintVector(V1, "V1");

  // 1.2. Создать "кучу" (heap) из последовательности
  make_heap(V1.begin(), V1.end());
  PrintVector(V1, "make_heap(V1)");

  // 1.3. Добавить элемент в последовательность и вывести последовательность снова
  V1.push_back(23);
  PrintVector(V1, "V1+1");

  // 1.4. Добавить элемент в существующую кучу
  push_heap(V1.begin(), V1.end());
  PrintVector(V1, "V1.push_heap");

  // 1.5. Извлечь наибольший элемент из существующей кучи - алгоритм pop_heap
  pop_heap(V1.begin(), V1.end());
  V1.resize(V1.size() - 1);
  PrintVector(V1, "V1.pop_heap");

  // 2. Использование алгоритма со стандартным предикатом greater
  // 2.1. Создать вектор
  vector<int> V2 = { 5, 9, 7, 3 };
  PrintVector(V2, "V2");

  // 2.2. Создать кучу
  make_heap(V2.begin(), V2.end());
  PrintVector(V2, "make_heap(V2)");

  // 2.3. Добавить элемент в последовательность V2
  V2.push_back(4);
  PrintVector(V2, "V2+1");

  // 2.4. Добавить элемент в существующую кучу - предикат greater
  push_heap(V2.begin(), V2.end(), greater<int>());
  PrintVector(V2, "push_heap(V2)");

  // 2.5. Вытащить наибольший элемент из существующей кучи
  pop_heap(V2.begin(), V2.end(), greater<int>());
  V2.resize(V2.size() - 1);
  PrintVector(V2, "V2.pop_heap");
}

Результат

V1 => 2 1 3 4
make_heap(V1) => 4 2 3 1
V1+1 => 4 2 3 1 23
V1.push_heap => 23 4 3 1 2
V1.pop_heap => 4 2 3 1
V2 => 5 9 7 3
make_heap(V2) => 9 5 7 3
V2+1 => 9 5 7 3 4
push_heap(V2) => 4 9 7 3 5
V2.pop_heap => 5 9 7 3

  ⇑

4. Алгоритм sort_heap. Сортировать числа в «куче»

Алгоритм имеет две перегруженные реализации

template <class RandomAccessIterator>
void sort_heap(
  RandomAccessIterator first,
  RandomAccessIterator last);

template <class RandomAccessIterator, class Compare>
void sort_heap(
  RandomAccessIterator first,
  RandomAccessIterator last,
  Compare pred);

здесь

• first, last – итераторы произвольного доступа, указывающие соответственно на первый и последний элементы диапазона, который рассматривается как потенциальная «куча»;
• pred – бинарный предикат, возвращающий true, если первый элемент меньше второго.

Пример.

#include <iostream>
#include <algorithm>
#include <vector>
#include <functional>
#include <ostream>
using namespace std;

void print(const string& s, const vector<int>& v)
{
  cout << s << " => ";
  for (auto i = v.begin(); i != v.end(); i++)
  {
    cout << *i << " ";
  }
  cout << endl;
}

int main()
{
  // Алгоритм sort_heap - отсортировать числа в "куче" (heap)

  // 1. Создать вектор и вывести его
  vector<int> V1 = { 2, -1, 3, 8, 4, 0, 5, 3, 1 };
  print("V1", V1);

  // 2. Конвертировать последовательность V1 в "кучу"
  make_heap(V1.begin(), V1.end());

  // 3. Отсортировать числа в "куче"
  sort_heap(V1.begin(), V1.end());

  // 4. Вывести результат
  print("sort_heap(V1)", V1);
}

Результат

V1 => 2 -1 3 8 4 0 5 3 1
sort_heap(V1) => -1 0 1 2 3 3 4 5 8

  ⇑

---

Связанные темы

• Алгоритмы определения минимума и максимума. Алгоритмы min, min_element, max, max_element, lexicographical_compare
• Алгоритмы перестановок. Алгоритмы next_permutation, prev_permutation
• Немодифицирующие алгоритмы. Поиск. Алгоритмы find, find_if, find_first_of, find_end, adjanced_find, search, search_n
• Немодифицирующие алгоритмы. Алгоритмы count, count_if, equal, equal_range, mismatch
• Алгоритмы для работы с множествами. Алгоритмы includes, set_union, set_intersection, set_difference, set_symmetric_difference

  ⇑

---