C++,Visual C++,Теорія

C++. STL. Алгоритми роботи з даними, що представлені за принципом “купи” (heap).

Алгоритми роботи з даними, що представлені за принципом “купи” (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

  ⇑

Споріднені теми

  ⇑