Куча. Операция вставки и удаления элемента. - EcsFlash/DataTypes GitHub Wiki
Куча — это специализированная структура данных, которая представляет собой бинарное дерево, удовлетворяющее свойству кучи. Существует два основных типа куч:
- Min-Heap (Минимальная куча): В каждом узле значение не больше, чем значения его потомков. Это означает, что наименьший элемент всегда находится в корне дерева.
- Max-Heap (Максимальная куча): В каждом узле значение не меньше, чем значения его потомков. Это означает, что наибольший элемент всегда находится в корне дерева.
Мы будем рассматривать max-heap, так как везде в очередях с приоритетом в корне лежал элемент с максимальным значением приоритета. Логику доступа к элементами кучи я накалякал на фотокарточке:
- Добавление элемента: Новый элемент добавляется в конец кучи, чтобы сохранить полноту дерева.
- Балансировка новоиспеченного элемента: Новый элемент сравнивается с его родителем. Если неравенство нарушено, элемент меняется местами с родителем. Этот процесс продолжается до тех пор, пока в всё не встанет на сои места.
- Удаление корневого элемента: Корневой элемент удаляется, так как он является минимальным (или максимальным) элементом.
- Меняем местами корень с последним элементом
- Просеивание: Новый корень сравнивается с потомками. Если неравенство нарушено, меняем элементы местами и продолжаем до тех пор пока все не встанет на свои места.
#include <iostream>
#include <vector>
#include <stdexcept>
using namespace std;
class MaxHeap {
private:
vector<int> heap;
void toUp(int index) {
while (index > 0) {
int parentIndex = (index - 1) / 2;
if (heap[index] > heap[parentIndex]) {
swap(heap[index], heap[parentIndex]);
index = parentIndex;
}
else {
break;
}
}
}
void toDown(int index) {
while (true) {
int left = 2 * index + 1;
int right = 2 * index + 2;
int toSwap = index;
if (left < heap.size() && heap[left] > heap[toSwap]) {
toSwap = left;
}
if (right < heap.size() && heap[right] > heap[toSwap]) {
toSwap = right;
}
if (toSwap != index) {
swap(heap[index], heap[toSwap]);
index = toSwap;
}
else {
break;
}
}
}
public:
void insert(int value) {
heap.push_back(value);
toUp(heap.size() - 1);
}
int extractMax() {
if (heap.empty()) {
throw "no mama";
}
int maxValue = heap[0];
heap[0] = heap.back();
heap.pop_back();
toDown(0);
return maxValue;
}
int peekMax() const {
if (heap.empty()) {
throw "no mama";
}
return heap[0];
}
bool isEmpty() const {
return heap.empty();
}
};