Очередь с приоритетами на С++ с использованием динамической кучи (heap) минимумов (максимумов) и шаблонов (template)
Содержание
1. Введение в структуру данных - куча
1.2. Описание структуры данных — куча
1.3. Базовая реализация кучи минимумов с помощью вектора
2. Работа кучи с разными типами данных
2.1. Применение шаблонов С++ для настройки кучи на работу с разными типами данных
2.2. Определение оператора сравнения в пользовательском типе данных для работы с кучей
4. Использование для реализации кучи указателей
1. Введение в структуру данных - куча
1.1. Возможности кучи
Данная структура данных позволяет динамически производить следующие операции над набором данных, состоящим из n элементов:
1) метод insert() добавляет новые элементы за время О (log n);
2) метод top() возвращает минимальное (максимальное) значение за время О (1);
3) метод pop() удаляет минимальное (максимальное) значение за время О (log n).
Данная структура данных может использоваться для т. н. «пирамидальной» сортировки. Добавление в структуру набора данных занимает О (n log n) и последовательное извлечение наименьших (наибольших) элементов - О (n log n), итого - О (2 n log n) или О (n log n).
1.2. Описание структуры данных - куча
В основе структуры лежит массив. Структура представляет собой бинарное дерево, где у каждого элемента есть два потомка. Отсюда вставка и удаление элементов за время О (log n) — максимальная глубина дерева. Родитель и потомки «жестко» связаны между собой по формуле (см. далее), в которой используются индексы массива, а значения элементов массива перемещаются (обмениваются) между ячейками массива в результате сравнения значений элементов (< или >) и продвижения на вершину (в начало массива) наименьшего (наибольшего) элемента.
В С++ массив индексируется, начиная с 0 — элемент с данным индексом является вершиной кучи (корнем дерева), в котором всегда будет находится минимум (максимум) — это является инвариантом. Также куча гарантирует, что потомки не больше (не меньше) родителя.
Приведем псевдографику для изображения кучи, где цифры означают индекс элемента в массиве:
0
| \
1 2
|\ |\
3 4 5 6
и т. д.Формула для определения потомков, где i – индекс элемента массива — родителя:
1) 
, - левый потомок (например, у корня — элемента с индексом 0 левый потомок — 1, у элемента с индексом 1 левый потомок — 3);
2) 
, - правый потомок (например, у корня — элемента с индексом 0 правый потомок - 2, у элемента с индексом 1 правый потомок — 4).
Формула для определения родителя, где i – индекс элемента массива — потомка, / - целочисленное деление — остаток отбрасывается:
1) 
, - для левого потомка (например, у элемента с индексом 1 родитель — 0, у элемента с индексом 3 родитель — 1);
2) 
, - для правого потомка (например, у элемента с индексом 2 родитель — 0, у элемента с индексом 4 родитель — 1).
Эти формулы можно несколько упростить, «объявив» вершиной кучи элемент с индексом 1, элемент с индексом 0 просто не будем использовать.
Формула для определения потомков, где i – индекс элемента массива — родителя:
1) 
, - левый потомок (например, у корня — элемента с индексом 1 левый потомок — 2, у элемента с индексом 2 левый потомок — 4);
2) 
, - правый потомок (например, у корня — элемента с индексом 1 правый потомок - 3, у элемента с индексом 3 правый потомок — 7).
Формула для определения родителя, где i – индекс элемента массива — потомка, / - целочисленное деление — остаток отбрасывается:
1) 
, - для левого потомка (например, у элемента с индексом 2 родитель — 1, у элемента с индексом 4 родитель — 2);
2) 
, - для правого потомка (например, у элемента с индексом 3 родитель — 1, у элемента с индексом 7 родитель — 3).
Таким образом, формула для определения родителя у обоих потомков будет одинаковой за счет целочисленного округления, что облегчит нам кодирование.
Приведем псевдографику для изображения кучи, где цифры означают индекс элемента в массиве:
1
| \
2 3
|\ |\
4 5 6 7
и т. д.1.3. Базовая реализация кучи минимумов с помощью вектора
Вектор является динамической структурой данных, позволяющей добавлять элементы, динамически расширяя (увеличивая) свою емкость (размер). Вектор управляет памятью, при необходимости увеличения первоначальной емкости самостоятельно выделяет память большего размера (как правило, в 2 раза больше) и переносит туда свои элементы.
Использование вектора для реализации кучи позволяет сделать кучу динамической, передав вектору задачу управления памятью.
Приведем минимальный код, необходимый для реализации кучи минимумов на С++:
Листинг № 1
#include <iostream>
#include <vector>
using namespace std;
using namespace std::literals;
struct heap {
void insert(int v) {
d.push_back(v); // вставляем новое значение в конец
// вычисляем индекс вставленного элемента
int i = d.size() - 1;
// ищем место для нового элемента в структуре
// элемент «всплывает» пока он меньше очередного родителя
// индекс элемента i не может быть меньше 1 (вершина кучи)
while(i > 0) {
auto p = i >> 1; // вычисляем индекс родителя i / 2
// индекс родителя p не может быть меньше 1 (вершина)
// если родитель больше потомка, то
if(p > 0 && d[i] < d[p]) {
swap(d[p], d[i]); // меняем значения местами
i = p; // присваиваем индекс родителя
} else break;
}
}
int top() { return d[1]; } // возвращаем значение вершины
void pop() {
int i = 1, sz = d.size();
// меняем местами вершину и последний элемент
swap(d[i], d[sz — 1]);
d.resize(--sz); // удаляем бывший минимум
// ищем «правильное» место в структуре для элемента,
// находящегося на вершине кучи,
// элемент «топится» пока он больше очередного потомка
// повторяем пока индекс элемента i меньше размера массива
while(i < sz) {
// вычисляем индекс левого потомка 2 * i
auto c = i << 1;
// индекс правого потомка (1 + с)
// должен быть меньше размера массива
// если значение правого потомка меньше левого,
// то перемещаем индекс на правого потомка
if((1 + c) < sz && d[1 + c] < d[c]) ++c;
// индекс элемента должен быть меньше размера массива
// если потомок меньше родителя, то
if(c < sz && d[c] < d[i]) {
// меняем местами потомка и родителя
swap(d[c], d[i]);
i = c; // присваиваем индекс потомка
} else break;
}
}
vector<int> d{0}; // пропускаем элемент с индексом 0
};
int main() {
vector<int> input {10, 5, 2, 6, 3, 7, 1, 9, 8, 0, 4};
heap h;
for(auto i : input) h.insert(i); // вставляем элементы в кучу
for(int i = 0; i < input.size(); ++i) {
cout << h.top() << " "s; // выводим минимум
h.pop(); // удаляем минимум
}
cout << endl;
return 0;
}
ВЫВОД:
0 1 2 3 4 5 6 7 8 9 10Комментарии к коду
У потомка один родитель, в то время как у родителя два потомка. Поэтому в методе pop(), когда мы «топим» элемент, опускаем его сверху вниз, то есть движемся от родителя к потомкам, перед обменом «родитель - потомок» необходимо из двух потомков выбрать наименьшего, что бы гарантированно обеспечить инвариант: в куче минимумов потомки всегда больше родителя.
Например, перед обменом родитель равен 5, левый потомок 3, правый - 1. Если мы обменяем местами родителя с левым потомком, то получим: родитель 3, левый потомок 5, правый -1. Инвариант не будет обеспечен: в куче минимумов родитель 3 будет больше правого потомка 1.
Мы реализовали 3 метода: insert(), top(), pop().
Существует еще 2 полезных метода:
1) heapify() строит кучу на основе переданного массива. Мы заменили его последовательной вставкой элементов в кучу:
for(auto i : input) h.insert(i);2) sort() сортирует элементы кучи. Мы заменили его последовательным извлечением и удалением минимума:
for(int i = 0; i < input.size(); ++i) {
cout << h.top() << " "s; // выводим минимум
h.pop(); // удаляем минимум
} Вместо вывода минимумы можно направить в вектор-приемник, в котором будет сформирован отсортированный массив.
2. Работа кучи с разными типами данных
2.1. Применение шаблонов С++ для настройки кучи на работу с разными типами данных
Чтобы не писать кучу под каждый тип данных преобразуем базовый код кучи из листинга 1 в шаблон.
Листинг № 2
// добавляем объявление шаблона в начало определения кучи
template<typename T>
struct heap {
...
// заменяем тип вставляемых данных int на T
void insert(T v) {
...
// заменяем тип возвращаемых данных int на T
T top() { return d[1]; }
...
// заменяем тип данных вектора int на T
vector<T> d{0};
}
int main() {
vector<string> input {"abc"s, "aa"s, "z"s};
// объявляем кучу строк
heap<string> h;
// включаем в объявление auto& i амперсанд & - знак ссылки,
// чтобы не копировать очередную переменную в i, а ссылаться
// на нее
for(auto& i : input) h.insert(i);
...
}
ВЫВОД:
aa abc z2.2. Определения оператора сравнения в пользовательском типе данных для работы с кучей
Чтобы куча работала, она должна правильно расставлять элементы данных, сравнивая их между собой (< или >). Для стандартных типов такие операции уже определены.
Пользовательский тип данных может потребоваться для хранения т. н. «полезной» нагрузки. Чтобы куча минимумов работала с пользовательским типом данных, необходимо определить операцию сравнения «меньше».
Определим тип без полезной нагрузки, являющийся оберткой вокруг типа int.
Листинг № 3
struct h_block {
int v;
bool operator<(h_block o) { return v < o.v; }
};
...
// Данный тип можно использовать с кучей, например, так:
int main() {
vector<int> input {10, 5, 2, 6, 3, 7, 1, 9, 8, 0, 4};
heap<h_block> h;
for(auto i : input) {
h_block b;
b.v = i;
h.insert(b);
}
...
}
ВЫВОД:
0 1 2 3 4 5 6 7 8 9 102.3. Превращение кучи минимумов в кучу максимумов без изменения кода кучи, используя оператор сравнения в пользовательском типе данных
Если в теле оператора сравнения типа h_block поменять знак сравнения < на >, то мы получим кучу максимумов.
bool operator<(h_block o) { return v > o.v; }
ВЫВОД:
10 9 8 7 6 5 4 3 2 1 0Таким образом, пользовательский тип без полезной нагрузки, являющийся оберткой вокруг другого типа, позволяет превращать кучу минимумов в кучу максимумов без изменения кода кучи.
Превратим тип h_block в шаблон, чтобы работать с разными типами встроенных данных.
Листинг № 4
// добавляем объявление шаблона в начало определения типа
template<typename T>
struct h_block {
T v;
// куча максимумов >
bool operator<(h_block o) { return v > o.v; }
};
...
int main() {
vector<string> input {"abc"s, "aa"s, "z"s};
heap<h_block<string>> h;
for(auto& i : input) {
h_block<string> b;
b.v = i;
h.insert(b);
}
...
}
ВЫВОД:
z abc aa3. Использование оператора сравнения в пользовательском типе данных для решения более сложных задач c помощью кучи
Пример 1. Использование кучи для выдачи наиболее коротких (длинных) текстов.
Листинг № 5
// добавляем специализацию шаблона для string
// поскольку для типа int вызов v.size() не определен
template<>
struct h_block<string> {
string v;
// сначала короткие строки, затем длинные
bool operator<(h_block o) { return v.size() < o.v.size(); }
};
...
ВЫВОД:
z aa abcПример 2. Использование кучи для выдачи текстов, содержащих больше (меньше) символов ‘a’.
Листинг № 6
// изменяем специализацию шаблона для string
template<>
struct h_block<string> {
string v;
int n = 0; // количество символов ‘a’ в тексте
// определяем метод сеттер для однократного вычисления n
// в момент установки значения строки
void set(string s) {
for(int i = 0; i < s.size(); ++i) if(s[i] == 'a') ++n;
v = move(s);
}
// сначала строки, содержащие больше символов ‘a’,
// затем меньше символов ‘a’
bool operator<(h_block o) { return n > o.n; }
};
...
int main() {
vector<string> input {"abc"s, "aa"s, "zaaa"s};
heap<h_block<string>> h;
for(auto& i : input) {
h_block<string> b;
// используем метод сеттер вместо непосредственного
// присваивания значения b.v = i
b.set(i);
h.insert(b);
}
...
}
ВЫВОД:
zaaa aa abcКомментарии к коду
В данном примере пользовательский тип несет полезную нагрузку в виде члена n - количество символов ‘a’ в тексте. Мы используем метод сеттер вместо непосредственного присваивания значения для однократного вычисления n в момент установки значения текста.
Методы сеттеры используют для установки значений закрытых членов класса, когда присваивания значения напрямую b.v = i недопустимо. Использование struct, у которой все члены по умолчанию открыты, вместо class, у которого все члены по умолчанию закрыты, для решения алгоритмических задач вполне оправданно, чего нельзя сказать о промышленном коде.
Вычисление n можно было бы реализовать, объявив параметризованный конструктор для структуры:
h_block(string s) { ... };Однако, если мы определим свой конструктор, то компилятор больше не создаст неявные («implicit») методы и в некоторых случаях придется реализовывать еще 4 метода:
h_block() = default; // конструктор по умолчанию
h_block(const h_block& obj) { ... }; // конструктор копирования
// оператор присваивания
h_block& operator=(const h_block& obj) { ... };
// начиная с C++11
h_block(h_block&& obj) { ... }; // конструктор перемещения
// оператор перемещения
h_block& operator=(h_block&& obj) { ... };4. Использование для реализации кучи указателей
В базовой реализации мы храним в куче непосредственно объекты. У данного подхода есть недостатки. Один из них состоит в том, что если вектор, который мы используем для реализации кучи исчерпает свою емкость, то он будет вынужден выделить новую память (как правило, в 2 раза больше имеющейся) и ему придется перенести в нее все имеющиеся объекты. В качестве примера можно привести манипуляции с текстами в куче.
Если мы будем хранить в куче только указатели, то они имеют фиксированный размер 4 байта в 32-х разрядных системах и 8 — в 64-х разрядных. При исчерпании вектором емкости и выделении новой памяти копироваться будут только указатели, а не сами тексты. То есть при количестве элементов n объем копирования составит 4 n или 8 n байт. В то время как объем каждого текста может измеряться килобайтами.
Содержание объектов не имеет значения для кучи, если класс объекта предоставляет оператор сравнения.
Листинг № 7 (полный код)
template<typename T>
struct h_block {
T v;
bool operator<(h_block o) { return v > o.v; }
};
template<>
struct h_block<string> {
string v;
int n = 0;
void set(string s) {
for(int i = 0; i < s.size(); ++i) if(s[i] == 'a') ++n;
v = move(s);
}
bool operator<(h_block o) { return n > o.n; }
};
template<typename T>
struct heap {
// заменяем тип параметра T на T* - указатель на T
void insert(T* v) {
d.push_back(v);
int i = d.size() - 1;
while(i > 0) {
auto p = i >> 1;
// для сравнения объектов разыменовываем указатели
if(p > 0 && *d[i] < *d[p]) {
swap(d[p], d[i]);
i = p;
} else break;
}
}
// заменяем тип возвращаемого значения T на T* указатель на T
T* top() { return d[1]; }
void pop() {
int i = 1, sz = d.size();
swap(d[i], d[sz - 1]);
delete d[sz - 1]; // освобождаем память
d.resize(--sz);
while(i < sz) {
auto c = i << 1;
// для сравнения объектов разыменовываем указатели
if((1 + c) < sz && *d[1 + c] < *d[c]) ++c;
// для сравнения объектов разыменовываем указатели
if(c < sz && *d[c] < *d[i]) {
swap(d[c], d[i]);
i = c;
} else break;
}
}
// заменяем тип значения T на T* - указатель на T
vector<T*> d{1};
};
int main() {
vector<string> input {"abc"s, "aa"s, "zaaa"s};
heap<h_block<string>> h;
for(auto& i : input) {
auto b = new h_block<string>(); // выделяем память
b->set(i); // устанавливаем значение через указатель
h.insert(b);
}
for(int i = 0; i < input.size(); ++i) {
// обращаемся к значению через указатель
cout << h.top()->v << " "s; h.pop();
}
cout << endl;
return 0;
}
ВЫВОД:
zaaa aa abc