Add Sem09

8 files changed, 372 insertions, 1 deletions

diff --git a/README.md b/README.md
index dc9ce6f..f0bd7dc 100644
--- a/README.md
+++ b/README.md
@@ -23,4 +23,7 @@
 Задачи за дървета. Балансирани дървета. Ротации и AVL дървета.
 
 ## Тема 8
-Имплементация на ротации. Индексация в двоично наредено дърво за логаритмично време. Heaps и абстрактна структура от данни приоритетна опашка.
\ No newline at end of file
+Имплементация на ротации. Индексация в двоично наредено дърво за логаритмично време. Heaps и абстрактна структура от данни приоритетна опашка.
+
+## Тема 9
+Имплементация на приоритетна опашка. Запознаване с асд dictionary и въвеждане на структурата от данни хеш таблица. Въвждане на различни методи за имплементация на хеш таблица.
\ No newline at end of file
diff --git a/Seminar09/README.md b/Seminar09/README.md
new file mode 100644
index 0000000..7d1f753
--- /dev/null
+++ b/Seminar09/README.md
@@ -0,0 +1,155 @@
+# Девети семинар по структури от данни - 04.12.2024
+
+## Имплементация на приоритетна опашка
+
+## Heap sort
+
+# Абстрактен тип данни dictionary. Хеш таблици. Реализация на феш таблици.
+*A common problem in computer science is the representation of a mapping between two sets.*
+
+## Абстрактен тип данни множество (set) и речник (dictionary/map/associative array)
+
+За абстрактен тип данни множество поддържаме:
+* insert(key)
+* contains(key)
+* erase(key)
+
+В абстрактния тип данни "речник" всеки елемент е обвързан с ключ.
+* insert(key, value)
+* contains(key) / find(key)
+* erase(key)
+
+Една възможна имплементация на речник би била двоично наредено (балансирано) дърво. Наредбата ще се поражда от ключовете (искаме те да са сравними). Във възлите на дървото ще пазим ключ и стойност - намирайки ключа в логаритмично време имаме и стойността му.
+
+Тази имплементация влече логаритмично време по големината на колекцията за всички операции. Хеш таблиците са структура от данни, която подобрява това време, и премахва нуждата да имаме сравними ключове.
+
+## Хеш функции
+Нека U е съвкупност от всички възможни ключове с които работим. Ако ключовете ни са числа U ще бъде множеството от възможните стойности на числата. Възможно е да имаме и ключове, които не са числа (примерно низове). 
+
+Хеш функция наричаме функция от типа: h: U -> {0, ..., n}. Ако си представим, че пазим ключовете в масив с големина `n`, то хеш функцията ще даде индекс на всеки ключ.
+
+Съществуват много феш функции. Примерно:
+```cpp
+int hashDummy(int key) {
+    return 0;
+}
+```
+е валидна, но неизползваема хеш функция. 
+
+Какво наричаме добра (или използваема) хеш функция?
+* Функцията трябва да използва всички данни от ключа.
+* Функцията трябва равномерно да разпределя елементите.
+* Функцията трябва да е бърза за изчисляване.
+* Желателно е за подобни ключове функцията да връща различни резултати.
+
+Добрата хеш функция се "държи добре" върху определен вход, но няма универсална хеш функция. 
+
+Също така, никой не ни гарантира, че броят на възможните ключове е по - малък от `n` (т.е. е съвсем възможно |U| > n). Това означава, че е възможно да съществуват два елемента за които `x != y && h(x) == h(y)`. По - просто казано - възможно е да има два елемента, които имат еднакъв индекс.
+
+Това наричаме **колизия**.
+
+## Използване на хеш функции в хеш таблиците.
+Структурата от данни хеш таблица трябва да поддържа вмъкване, търсене и премахване по подаден ключ (и стойност във вмъкването). Ако разполагаме с добра хеш функция за съвкупността от ключове, с които нашата таблица работи, можем да приложим следната стратегия:
+
+Създаване: 
+1. Създай масив с големина n който пази стойности.
+
+Вмъкване:
+1. Намери индекса на ключа използвайки хеш функцията
+2. Добави стойността на намерения индекс.
+
+Търсене:
+1. Намери стойността на ключа използвайки хеш функцията
+2. Промери дали има елемент на този индекс.
+
+Премахване:
+1. Намери стойността на ключа използвайки хеш функцията
+2. Ако има елемент на този индекс то премахни.
+
+Тази стратегия е **твърде оптимистична!** Ако хеш функцията ни няма колизии всичко ще е наред. Ако има колизии тази стратегия е обречена на провал - какво правим когато искаме да вмъкнем елемент, чийто ключ има същия хеш индекс като вече съществяващ такъв?
+
+В следващите няколко секции ще се занимаем с две неща:
+1. Техники за справяне с колизии.
+2. Техники за оптимална реализация на хеш таблица.
+
+![hashmap](media/hashmap.png)
+
+## Справяне с колизии - Separate chaining
+При представената неуспешна стратегия, създавайки хеш таблицата, заделяхме масив с n елемента, който пази стойности. Нека елементите на този масив не са стойности **а контейнери, които пазят такива.** Такива контейнери наричаме buckets или кофи.
+
+Сега, ако имаме колизия, просто добавяме елемента най - отзад на свързания списък. При търсенето също има промени - вече обхождаме свързания списък за да намерим дали наистина ключа съществува, или просто кофата е напълнена с ключове, съдържащи други стойности.
+
+Аналогично е при премахването - отново трябва да обходим свързания списък.
+
+![separate-chaining](media/separate_chaining.png)
+
+За момента не сме казали нищо за сложността на която и да е операция. Тази имплементация ни води до O(n) worst case complexity. Това би се случило, примерно, ако добавим n елемента с ключове, образуващи колизия. И се опитаме да добавим, премахнем или потърсим ключ, също образуващ колизия. 
+
+Такова поведение **е слабо вероятно** използвайки добра хеш функция, но ако използваме функция от типа на `hashDummy` е очаквано.
+
+## Използване на други структури за да подобрим O(n) worst case
+Лошата горна граница за търсенето ни идва от факта, че използваме свързани списъци. Вече имаме дървета, които ни позволяват O(log(n)) търсене, защо вместо свързани списъци не използваме тях примерно?
+
+Това е интересна тема за разсъждение - от една страна лошото търсене не се дължи толкова на свързания списък колкото на факта, че елементите не са разпределени добре. 
+
+Дървото ще забърза нещата, но така не поддържаме ли просто едно бавно дърво (или няколко такива)?
+
+Такива техники все пак се използват. [Тук](https://openjdk.org/jeps/180) можем да прочетем:
+
+```
+The principal idea is that once the number of items in a hash bucket grows beyond a certain threshold, that bucket will switch from using a linked list of entries to a balanced tree. In the case of high hash collisions, this will improve worst-case performance from O(n) to O(log n).
+```
+
+
+## Недостатъци на Separate chaining 
+Освен O(n) сложността в най - лошия случай това решение добавя ниво на забавяне към търсенето, понеже свързаните списъци нямат cache locality. Следващата стратегия се стреми да подобри този проблем.
+
+## Open adressing
+В предишната стратегия елементите се държаха извън хеш таблицата (в свързани списъци). В отвореното адресиране **всички** елементи се държат в хеш таблицата.
+
+Все пак това ни връща на първоначалната стратегия. Този път няма да променяме паметта, в която държим елементите, а ще променяме начините по които ги търсим, добавяме или изтриваме.
+
+Един работещ начин за подобна промяна е следния:
+
+## Linear probing
+
+### Добавяне
+Разглеждаме елементите и техните хеш кодове: {A, 2}, {B, 3}, {C, 7}, {D, 2}.
+
+Добавянето на първите три в някакъв смисъл е лесно. Имаме следния сценарий:
+
+![](media/insert-first.png)
+
+Какво правим обаче когато имаме колизия (както е в случая с D). Ами започваме линейно да търсим първата свободна клетка. Там добавяме D.
+
+![](media/insert-second.png)
+
+## Търсене
+Сега, да предположим, че търсим D. Генерираме неговия хеш код, но на негово място стои А. Логично е, познавайки стратегията си, да не се отказваме и да продължим да търсим. Търсим до момента в който не срещнем първата празна клетка.
+
+## Изтриване
+Тук нещата стават малко по - сложни. Да кажем, че изтрием B. След това търсим D. Но сега между A и D **има празна клетка**. Това погрешно ще ни каже, че елементът не е в колекцията.
+
+**Решение:** добавяме два флага на клетката: empty и deleted. Ако клетката е била изтрита **не спираме да търсим**. Спираме при първата **празна клетка**. 
+
+**Няма проблем да добавяме елементи в изтрита клетка.**
+
+##  Недостатъци на linear probing стратегията
+Този метод работи, но какво правим когато всички клетки се запълнят? При n + 1 - вото добавяне тази стратегия спира да работи. Момента в който запълним всички клетки можем да преоразмерим масива (resize).
+
+## Преоразмеряване на хеш таблици
+При стратегията Separate chaining нямахме проблема с преоразмеряването. Обикновено обаче такова присъства. В случай на 10 кофи и 10000 елемента операциите започват да стават по - бавни.
+
+```
+LoadFactor = #elements / #buckets
+```
+
+Обикновено хеш таблиците имат два начални параметъра - първоначална големина на масива (initial capacity) и load factor. Втория ни помага да разберем кога да направим resize. Обикновено се използват стойности като 0.7 или 0.75.
+
+## Някои хеш функции
+* Метод на деленето (division method): h(k) = k mod n.
+* Метод на умножението (multiplication method): h(k) = floor( n * (kA mod 1) )
+Където А е някакво число между 0 и 1. mod 1 изважда единствено дробната част от умножението.
+
+* Готови хеширащи функции:
+Добрите хеширащи функции често са сложни. Съществуват готови хеширащи функции, които можем да използваме като черни кутии (MD5, SHA, ...)
\ No newline at end of file
diff --git a/Seminar09/media/hashmap.png b/Seminar09/media/hashmap.png
new file mode 100644
index 0000000..c6c7961
--- /dev/null
+++ b/Seminar09/media/hashmap.png
diff --git a/Seminar09/media/insert-first.png b/Seminar09/media/insert-first.png
new file mode 100644
index 0000000..f0b3afc
--- /dev/null
+++ b/Seminar09/media/insert-first.png
diff --git a/Seminar09/media/insert-second.png b/Seminar09/media/insert-second.png
new file mode 100644
index 0000000..e7c97d5
--- /dev/null
+++ b/Seminar09/media/insert-second.png
diff --git a/Seminar09/media/separate_chaining.png b/Seminar09/media/separate_chaining.png
new file mode 100644
index 0000000..dfd77f0
--- /dev/null
+++ b/Seminar09/media/separate_chaining.png
diff --git a/Seminar09/src/priority-queue/heapsort.cpp b/Seminar09/src/priority-queue/heapsort.cpp
new file mode 100644
index 0000000..28e499a
--- /dev/null
+++ b/Seminar09/src/priority-queue/heapsort.cpp
@@ -0,0 +1,80 @@
+#include <iostream>
+#include <vector>
+
+void heapify(std::vector<int>& _data, size_t index, size_t array_size)
+{
+    int current_index = index;
+
+    while(true)
+    {
+        size_t left_index = 2 * current_index + 1;
+        size_t right_index = 2 * current_index + 2;
+
+        bool go_left = left_index < array_size && _data[current_index] < _data[left_index];
+        bool go_right = right_index < array_size && _data[current_index] < _data[right_index];
+
+        if(!go_left && !go_right)
+        {
+            break;
+        }
+
+        if(go_left && go_right)
+        {
+            if(_data[left_index] < _data[right_index])
+            {
+                std::swap(_data[current_index], _data[right_index]);
+                current_index = right_index;
+            }
+            else
+            {
+                std::swap(_data[current_index], _data[left_index]);
+                current_index = left_index;
+            }
+        }
+        else if(go_left)
+        {
+            std::swap(_data[current_index], _data[left_index]);
+            current_index = left_index;
+        }
+        else 
+        {
+            std::swap(_data[current_index], _data[right_index]);
+            current_index = right_index;
+        }
+    }
+}
+
+void build_heap(std::vector<int>& data)
+{
+    for(int i = data.size() / 2 - 1; i >= 0; i--)
+        heapify(data, i, data.size());
+}
+
+void heap_sort(std::vector<int>& data)
+{
+    build_heap(data);
+
+    int current_min = data.size() - 1;
+
+    for (size_t i = 0; i < data.size() - 1; i++)
+    {
+        std::swap(data[0], data[current_min--]);
+        heapify(data, 0, current_min);
+    }
+}
+
+int main()
+{
+    std::vector<int> v;
+    for (size_t i = 0; i < 100; i++)
+    {
+        v.push_back(rand() % 100);
+    }
+    
+    heap_sort(v);
+
+    for(int x : v)
+    {
+        std::cout << x << " ";
+    }
+}
\ No newline at end of file
diff --git a/Seminar09/src/priority-queue/priority-queue.hpp b/Seminar09/src/priority-queue/priority-queue.hpp
new file mode 100644
index 0000000..4e54d63
--- /dev/null
+++ b/Seminar09/src/priority-queue/priority-queue.hpp
@@ -0,0 +1,133 @@
+#pragma once
+#include <vector>
+#include <stdexcept>
+
+class priority_queue
+{
+private:
+    static size_t left_child(size_t index);
+    static size_t right_child(size_t index);
+    static int parent(int index);
+
+    void heapify(size_t index);
+public:
+    priority_queue() = default;
+
+    // build_heap
+    priority_queue(const std::vector<int>& data);
+
+    void push(int element);
+    int peek() const;
+    void pop();
+
+    bool empty() const;
+    size_t size() const;
+
+private:
+    std::vector<int> _data;
+};
+
+size_t priority_queue::left_child(size_t index)
+{
+    return 2 * index + 1;
+}
+
+size_t priority_queue::right_child(size_t index)
+{
+    return 2 * index + 2;
+}
+
+int priority_queue::parent(int index)
+{
+    return (index - 1) / 2;
+}
+
+void priority_queue::heapify(size_t index)
+{
+    size_t current_index = index;
+
+    while(true)
+    {
+        size_t left_index = left_child(current_index);
+        size_t right_index = right_child(current_index);
+
+        bool go_left  = left_index < _data.size()  && _data[current_index] < _data[left_index];
+        bool go_right = right_index < _data.size() && _data[current_index] < _data[right_index];
+
+        if(!go_left && !go_right)
+        {
+            break;
+        }
+        
+        if(go_left && go_right)
+        {
+            if(_data[left_index] > _data[right_index])
+            {
+                std::swap(_data[current_index], _data[left_index]);
+                current_index = left_index;
+            }
+            else
+            {
+                std::swap(_data[current_index], _data[right_index]);
+                current_index = right_index;
+            }
+        }
+        else if(go_left)
+        {
+            std::swap(_data[current_index], _data[left_index]);
+            current_index = left_index;
+        }
+        else // go_right
+        {
+            std::swap(_data[current_index], _data[right_index]);
+            current_index = right_index;
+        }
+    }
+}
+
+priority_queue::priority_queue(const std::vector<int>& data) :
+    _data(data)
+{
+    // build_heap
+    for (int i = _data.size() / 2 - 1; i >= 0; i--)
+        heapify(i);    
+}
+
+void priority_queue::push(int element)
+{
+    _data.push_back(element);
+    int index = _data.size() - 1;
+    int parent_index = parent(index);
+
+    while(index > 0 && _data[index] > _data[parent_index])
+    {
+        std::swap(_data[index], _data[parent_index]);
+        index = parent_index;
+        parent_index = parent(index);
+    }
+}
+
+int priority_queue::peek() const
+{
+    return _data[0];
+}
+
+void priority_queue::pop() 
+{
+    if(empty())
+        throw std::runtime_error("Pop on empty queue");
+    
+   _data[0] = _data.back();
+   _data.pop_back();
+   heapify(0); 
+}
+
+size_t priority_queue::size() const
+{
+    return _data.size();
+}
+
+bool priority_queue::empty() const
+{
+    return size() == 0;
+}
\ No newline at end of file