From c6aac99a845c7787496611fd0bb7c4be55e916ed Mon Sep 17 00:00:00 2001 From: Desislava Shunina <115353472+desiish@users.noreply.github.com> Date: Tue, 3 Dec 2024 17:55:23 +0200 Subject: add pract09 readme --- Practicum/pract09/readme.md | 213 ++++++++++++++++++++++++++++++++++++++++++++ 1 file changed, 213 insertions(+) create mode 100644 Practicum/pract09/readme.md (limited to 'Practicum/pract09') diff --git a/Practicum/pract09/readme.md b/Practicum/pract09/readme.md new file mode 100644 index 0000000..ea04332 --- /dev/null +++ b/Practicum/pract09/readme.md @@ -0,0 +1,213 @@ +# Практикум №9 по Структури от данни, спец. ИС + +## `Binary Heap` +**Binary Heap**-a представлява дървовидна структура от данни, която изпълнява 2 условия: +1) пълно двоично дърво е (всички нива са запълнени освен последното); +2) всеки връх има стойност <= (респективно >=) на тази на родителя си (heap property); + +> [!IMPORTANT] +> От условията следва, че винаги най-големият (респективно най-малкият) елемент е на върха на пирамидата, НО данните вътре не са винаги сортирани. + +Обикновено се представя чрез масив, като е изпълнено следното: +- за всеки родител на индекс i лявото му дете е на индекс 2i + 1, а дясното - на 2i + 2; +- за всяко дете на индекс i родителят му се намира на индекс (i - 1) / 2; +- коренът е на индекс 0. + +Разграничаваме 2 вида heap: +- `minHeap` - най-малкият елемент е най-отгоре; +- `maxHeap` - най-големият елемент е най-отгоре; + +### Как от вектор можем да създадем heap? +STL поддържа методи, които ни позволяват да работим с вектор като с heap. Това са следните: +- **Превръщане на heap**: `std::make_heap(begin_it, end_it)` - O(N) +- **Добавяне на елемент**: + - Добавяме елемент в края на контейнера. + - Викаме `std::push_heap(begin, end)` - O(logN) +- **Извличане на най-големия елемент**: + - Викаме `std::pop_heap(begin, end)` - O(logN) + - Премахваме елемента в края. +- **Проверка дали е heap**: `std::is_heap(begin, end)` - O(N) + +Нека разгледаме и техните имплементации: +```c++ +#include +#include + +template +void heapify(RandomIt first, size_t rootIdx, size_t size, Compare comp) { + size_t largest = rootIdx; + size_t leftChild = 2 * rootIdx + 1; + size_t rightChild = 2 * rootIdx + 2; + + if (leftChild < size && comp(*(first + largest), *(first + leftChild))) + largest = leftChild; + + if (rightChild < size && comp(*(first + largest), *(first + rightChild))) + largest = rightChild; + + if (largest != rootIdx) { + std::swap(*(first + rootIdx), *(first + largest)); + heapify(first, largest, size, comp); + } +} + +template > +void make_heap(RandomIt first, RandomIt last, Compare comp = Compare()) { + size_t size = last - first; + + for (int i = size / 2; i >= 0; --i) + heapify(first, i, size, comp); +} + +template +void bubble_up(RandomIt first, size_t index, Compare comp) { + while (index > 0) { + size_t parentIndex = (index - 1) / 2; + + if (!comp(*(first + parentIndex), *(first + index))) + break; + + std::swap(*(first + parentIndex), *(first + index)); + index = parentIndex; + } +} + +template > +void push_heap(RandomIt first, RandomIt last, Compare comp = Compare()) { + size_t size = last - first; + + if (size > 1) + bubble_up(first, size - 1, comp); +} + +template > +void pop_heap(RandomIt first, RandomIt last, Compare comp = Compare()) { + size_t size = last - first; + + if (size > 1) { + std::swap(*first, *(last - 1)); + heapify(first, 0, size - 1, comp); + } +} + +template > +bool is_heap(RandomIt first, RandomIt last, Compare comp = Compare()) { + size_t size = last - first; + + for (size_t i = 0; i < size / 2; ++i) { + size_t leftChild = 2 * i + 1; + size_t rightChild = 2 * i + 2; + + if (leftChild < size && comp(*(first + i), *(first + leftChild))) + return false; + + if (rightChild < size && comp(*(first + i), *(first + rightChild))) + return false; + } + + return true; +} +``` + +Както се вижда, по default методите използват `std::less<>` за сравнение на обектите, така че default-ния heap е `maxHeap`. + +> [!NOTE] +> Ако искаме да създадем `minHeap`, то като comparator трябва да подадем `std::greater<>`. + +Структурата от данни, която е създадена на базата на `Binary Heap`-a, е т.нар. `Priority Queue` или приоритетна опашка на български. + +## `std::priority_queue` + +`std::priority_queue` представлява обвиващ клас за контейнер (std::vector по default), изграден на основата на heap-a. По default е изграден като maxHeap, т.е. +ни гарантира, че винаги най-големия елемент ще е първи. Поддържа следните операции: +- **Добавяне на елемент**: `pq.push(value)` - O(logN) +- **Премахване на елемента с най-висок приоритет**: `pq.pop()` - O(logN) +- **Достъп до елемента с най-висок приоритет**: `pq.top()` - O(1) +- **Проверка на размера**: `pq.size()` - O(1) +- **Проверка за празнота**: `pq.empty()` - O(1) + +Нека разгледаме какви параметри приема в шаблона си: +```c++ +template< + class T, + class Container = std::vector, + class Compare = std::less +> class priority_queue; +``` + + +Ето и примерна имплементация: +```c++ +#include +#include +#include + +template, class Comp = std::less> +class priority_queue +{ + Container _c; + Comp _comp; + +public: + void push(const T& value) + { + _c.push_back(value); + std::push_heap(_c.begin(), _c.end(), _comp); + } + + void push(T&& value) + { + _c.push_back(std::move(value)); + std::push_heap(_c.begin(), _c.end(), _comp); + } + + void pop() + { + std::pop_heap(_c.begin(), _c.end(), _comp); + _c.pop_back(); + } + + bool empty() const + { + return _c.empty(); + } + + const T& top() const + { + if (empty()) + throw std::runtime_error("Empty container"); + + return _c.front(); + } + + size_t size() const + { + return _c.size(); + } +}; +``` + +И тук, ако искаме да създадем minHeap, трябва да подадем `std::greater<>` като custom comparator. + +### Пример с min-heap + +```c++ +#include +#include +#include + +int main() +{ + std::vector v = {3, 1, 4, 1, 5, 9}; + std::priority_queue, std::greater> pq(v.begin(), v.end()); + + while (!pq.empty()) + { + std::cout << pq.top() << ' '; + pq.pop(); + } +} +``` + +--- +[**Линк към задачите**](https://leetcode.com/problem-list/aglkjy9v/) -- cgit v1.3.1-26-gb76a