Abstraktni podatkovni tipi.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "id": "6fcd0d8c-4c8f-4d4e-ae57-b7b86aab0d62",
   "metadata": {},
   "source": [
    "# Abstraktni podatkovni tipi\n",
    "\n",
    "Abstraktni podatkovni tip (APT, *abstract data type*) poleg množice možnih vrednosti definira tudi vse operacije, ki so dovoljene na elementih tega podatkovnega tipa, ne definira pa konkretne predstavitve podatkov\n",
    "\n",
    "Podatkovna struktura (PS, *data structure*) je način organizacije in hrambe podatkov, ki omogoča njihovo učinkovito uporabo, kot so npr. dostop do podatkov, obdelava in spreminjanje.\n",
    "\n",
    "Abstraktni podatkovni tip torej definira **funkcionalnost**, ne pa konkretne **implementacije** in s tem povezane računske zahtevnosti posameznih operacij. Kot bomo videli že na prvem primeru polja, ločnica ni vedno najbolj jasna, ker se enaka imena lahko uporabljajo v obeh pomenih."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 1,
   "id": "6e4f7419-7a80-45b0-99a7-90ce900cdccb",
   "metadata": {},
   "outputs": [],
   "source": [
    "#include <iostream>\n",
    "#include <vector>\n",
    "#include <stack>\n",
    "#include <list>\n",
    "#include <random>\n",
    "#include <algorithm>\n",
    "#include <stdlib.h>\n",
    "using namespace std;"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "d6bf3429-de27-4b74-ae08-2f1821a7420e",
   "metadata": {
    "jp-MarkdownHeadingCollapsed": true
   },
   "source": [
    "## Polje (*array*)\n",
    "\n",
    "Polje lahko interpretiramo na dva načina: kot abstraktni podatkovni tip (APT) ali kot podatkovno strukturo (PS).\n",
    "\n",
    "Polje (ADT) hrani urejen nabor elementov, do katerih lahko dostopamo s celoštevilskim indeksi. Omogoča naslednjo funkcionalnost:\n",
    "\n",
    "- `init(c)`: Inicializira polje velikosti `c`.\n",
    "- `set(i,x)`: Shrani element x na indeks i.\n",
    "- `get(i)`: Vrni element na indeksu i.\n",
    "\n",
    "Polje oz. tabela (DS) je hkrati tudi ena najbolj osnovnih podatkovnih struktur, ki hrani podatke enakega tipa/velikosti zaporedno enega za drugim v strnjenem kosu pomnilnika.\n",
    "\n",
    "Primeri: (Pascal: `array [1..12] of integer`), (C, C++: `int t[12]`), (Java: `int[] t = new int[12]`)."
   ]
  },
  {
   "cell_type": "markdown",
   "id": "537ef204-13c0-457e-a436-4d97d616bbb2",
   "metadata": {},
   "source": [
    "## Sklad (*stack*)\n",
    "\n",
    "Sklad je abstraktni podatkovni tip, ki hrani elemente organizirane tako, da lahko dodamo nov element, dostopamo pa lahko samo do tistega, ki je bil dodan nazadnje. Obnaša se torej podobno kot kup knjig, na katerega lahko zlagamo nove knjige, s kupa pa lahko vzamemo samo knjigo, ki je trenutno na vrhu. Če želimo kakšno knjigo, ki se nahaja globlje, jih bomo morali z vrha vzeti več. Sklad je poznan tudi kot LIFO (last in, first out) struktura.\n",
    "\n",
    "- `push(x)`: Dodaj element na vrh sklada.\n",
    "- `pop()`: Odstrani in vrne element, ki se trenutno nahaja na vrhu sklada.\n",
    "\n",
    "Pogosto uporabljena operacije je še `top/peek()`, ki vrne vrednost vrhnjega elementa, ne da bi ga odstranila, `size()`, ...\n",
    "\n",
    "Sklad je precej enostaven za implementacijo, saj lahko uporabimo kar povezan seznam, s katerim dosežemo konstantno časovno zahtevnost operacij. Kljub svoji enostavnosti, nam pogosto pride prav. Vse rekurzivne funkcije (pravzaprav kar vse funkcije) se namreč izvajajo s pomočjo sklada.\n",
    "\n",
    "Primeri: (C++: `stack`), (Java: `Stack`)"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "438c2883-1d4d-4d86-a204-36dc0be15af7",
   "metadata": {},
   "source": [
    "## Seznam (*list*)\n",
    "\n",
    "Seznam je abstraktni podatkovni tip, ki hrani končno zaporedje elementov. Smiseln nabor operacij, ki jih mora omogočati, je:\n",
    "\n",
    "- `add(x)`: Dodaj element x v seznam. Kam je dodan, je lahko stvar implementacije, ali pa je definirano že v APT.\n",
    "- `remove(x)`: Odstrani element x iz seznama.\n",
    "- `size()`: Število elementov v seznamu.\n",
    "- `traverse`: Način iteracije čez vse elemente seznama. Lahko v obliki dostopa do prvega elementa in nato vsakega naslednjika.\n",
    "\n",
    "Lahko bi definirali še marsikatero drugo operacijo: `empty()`, `contains(x)`, `get(i)`, `insert(i,x)`, ...\n",
    "\n",
    "Primeri: (C++: `list`), (Java: `List`), (Python: `list`)."
   ]
  },
  {
   "cell_type": "markdown",
   "id": "45baa616-3590-4694-b247-8ad8a08ea046",
   "metadata": {
    "jp-MarkdownHeadingCollapsed": true
   },
   "source": [
    "### Povezani seznam (*linked list*)\n",
    "\n",
    "Povezan seznam je podatkovna struktura, ki nam omogoča učinkovito vstavljanje in brisanje (preko reference na element, za katerega vstavljamo oz. ki ga brišemo). Spoznali ste ga že pri Programiranju 2. Vsako vozlišče hrani vrednost elementa in kazalec na naslednje vozlišče. Poleg tega potrebujemo še kazalec na začetek povezanega seznama. Je pa v povezanem seznamu otežen dostop preko indeksa, torej do $i$-tega elementa, in sicer zahteva $O(n)$ korakov, da se prebijemo do njega od začetka seznama.\n",
    "\n",
    "Primeri: (C++: `list`), (Java: `LinkedList`)."
   ]
  },
  {
   "cell_type": "markdown",
   "id": "a9492d00-0b52-48a4-87de-1327b30e6d5c",
   "metadata": {},
   "source": [
    "### Dinamično polje (*dynamic/resizeable array*)\n",
    "\n",
    "Dinamično polje je podatkovna struktura, ki presega omejitve navadnega polja in omogoča dodajanje novih elementov. Kot taka je primerna za implementacijo seznama. \n",
    "\n",
    "Implementacije seznama se lahko lotimo s tabelo, kot ste navajeni iz C-ja. Vsakič, ko dodamo nek element, preverimo kapaciteto naše tabele. Če smo jo presegli, alociramo novo, za 1 večjo tabelo, skopiramo vse elemente in dodamo novega na konec. To je zelo prostorsko učinkovito, časovno pa precej potratno, saj potrebujemo za izgradnjo seznama z $n$ elementi kar $O(n^2)$ časa. \n",
    "\n",
    "Kadar govorimo o povprečni časovni zahtevnosti v nekem zaporedju operacij, temu rečemo **amortizirana zahtevnost**. V tem primeru je amortizirana časovna zahtevnost $O(n)$, ker za dodajanje $O(n)$ elementov porabimo skupaj $O(n^2)$ časa, kar znese $O(n)$ operacij na posamezen dodan element. Neamortizirana časovna zahtevnost dodajanja posameznega elementa pa je linearna, torej $O(n)$, ker se nam lahko zgodi, da moramo skopirati celoten seznam.\n",
    "\n",
    "Alternativa je podvojevanje velikosti seznama. Vsakič, ko dosežemo kapaciteto, alociramo novo, dvakrat večjo tabelo. Tako bomo za izgradnjo seznama dolžine $n$, potrebovali $1 + 2 + 4 + 8 + \\dots < 4n = O(n)$ operacij (oz. $2n$, če je $n$ ravno potenca števila 2). Prostorsko je nekoliko manj učinkovito, vendar še vedno reda $O(n)$. Enake računske zahtevnosti dosežemo tudi s kakšnim drugim faktorjem, ki ni nujno 2. Moramo pa velikost množiti z nekim faktorjem, ne pa ga prištevati. Spodnja implementacija prikazuje osnovno idejo.\n",
    "\n",
    "Primeri: (C++: `vector`), (Java: `ArrayList`), (Python: `list`)."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "id": "9b60b720-33b5-4a70-8d08-4fc3ffa00a99",
   "metadata": {},
   "outputs": [],
   "source": [
    "class DynamicArray {\n",
    "private:\n",
    "    int *t, size, capacity;\n",
    "public:\n",
    "    DynamicArray() { t = (int*)malloc(sizeof(int));  size = 0; capacity = 1; }\n",
    "    ~DynamicArray() { free(t); }\n",
    "    int operator[](int i) { return t[i]; }\n",
    "    void add(int x) {\n",
    "        if (size == capacity) {\n",
    "            capacity *= 2;\n",
    "            t = (int*)realloc(t, capacity*sizeof(int));\n",
    "        }\n",
    "        t[size++] = x;\n",
    "    }\n",
    "};"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 3,
   "id": "bf3f9306-3077-42a4-b36e-6e923afcd821",
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "50000\n"
     ]
    }
   ],
   "source": [
    "DynamicArray a;\n",
    "int n=100000;\n",
    "for (int i=0;i<n;i++) a.add(i);\n",
    "cout << a[n/2] << endl;"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "e459f429-6904-4cbe-9d77-380edc4aacbe",
   "metadata": {},
   "source": [
    "## Vrsta (*queue*)\n",
    "\n",
    "Vrsta je abstraktni podatkovni tip, ki hrani elemente organizirane tako, da lahko dodamo nov element na konec vrste, dostopamo pa lahko do tistega, ki se nahaja na začetku vrste oz. je v njej najdlje. Nič drugače, kot vrste sicer, le da tu res ni možnosti vrivanja. V primerjavi s skladom je to FIFO (first in, first out) struktura.\n",
    "\n",
    "- `push/enqueue(x)`: Doda element na konec vrste.\n",
    "- `pop/dequeue()`: Odstrani in vrne element z začetka vrste.\n",
    "\n",
    "Kot pri skladu, sta tudi tu pogosta še `front/peek()` in `size()`. Različica vrste je tudi **dvostrana vrsta** oz. vrsta z dvema koncema (*double-ended queue*), kjer lahko elemente dodajamo in odstranjujemo z obeh strani (začetka in konca).\n",
    "\n",
    "Vrsto lahko enostavno implementiramo s povezanim seznamom. Poleg kazalca na začetek seznama potrebujemo še kazalec na konec, da lahko učinkovito dodajamo elemente. Tako imajo vse operacijo konstantno časovno zahtevnost, prostorska zahtevnost pa je linearna, kar je tudi najbolje, kar lahko dosežemo.\n",
    "\n",
    "Primeri: (C++: `queue, deque`), (Java: `Queue, Deque`), (Python: `deque`)"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "1e629eb1-72da-4949-9471-231a8e613f0d",
   "metadata": {},
   "source": [
    "Druga možnost za implementacijo je uporaba dinamičnega polja, ki podvoji svojo kapaciteto, ko je polno. Nove elemente dodajamo na konec tabele. Pri odstranjevanju z začetka pa popravimo indeks, kjer se vsebina vrste začne v tabeli. Težava take rešitve je prostorska zahtevnost, ki ni odvisna od števila elementov v vrsti, ampak od skupnega števila do sedaj dodanih elementov. Rešitev lahko malenkost izboljšamo z uporabo krožnega polja. Sedaj je prostorska zahtevnost odvisna od maksimalne velikosti vrste. Da dosežemo prostorsko zahtevnost, ki je linearno odvisna od velikosti vrste (števila elementov v njej), moramo vključiti še krčenje tabele in sicer, ko velikost pade pod četrtino kapacitete. Razmislite, kaj bi se lahko zgodilo, če bi to naredili pri polovici."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 4,
   "id": "5f7323ae-d9bd-4400-bf49-34e2a2cb682b",
   "metadata": {},
   "outputs": [],
   "source": [
    "class ArrayQueue {\n",
    "private:\n",
    "    vector<int> t;\n",
    "    int head, tail;\n",
    "public:\n",
    "    int size, capacity;\n",
    "    ArrayQueue() { head=0, tail=0, size=0, capacity=1; t=vector<int>(capacity); }\n",
    "\n",
    "    int front() { return t[head]; }\n",
    "\n",
    "    void push(int x) {\n",
    "        if (size+1==capacity) {  // grow\n",
    "            vector<int> t2(2*capacity);\n",
    "            for (int i=head,j=0; i!=tail; i=(i+1)%capacity,j++) t2[j]=t[i];\n",
    "            t=t2; head=0; tail=size; capacity*=2;\n",
    "        }\n",
    "        t[tail] = x;\n",
    "        tail = (tail+1)%capacity;\n",
    "        size++;\n",
    "    }\n",
    "\n",
    "    int pop() {\n",
    "        int x = t[head];\n",
    "        head = (head+1)%capacity;\n",
    "        size--;\n",
    "        if (size<=capacity/4) {  // shrink\n",
    "            vector<int> t2(capacity/2);\n",
    "            for (int i=head,j=0; i!=tail; i=(i+1)%capacity,j++) t2[j]=t[i];\n",
    "            t=t2; head=0; tail=size; capacity/=2;\n",
    "        }\n",
    "        return x;\n",
    "    }\n",
    "};"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 5,
   "id": "22b62668-ef24-4886-8408-f94b5bc8814a",
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "80 20 64\n"
     ]
    }
   ],
   "source": [
    "ArrayQueue q;\n",
    "for (int i=0;i<100;i++) q.push(i);\n",
    "for (int i=0;i<80;i++) q.pop();\n",
    "cout << q.front() << \" \" << q.size << \" \" << q.capacity << endl;"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "1ba98d1b-0be3-4d7a-9941-d7f0fc3aacbf",
   "metadata": {},
   "source": [
    "Še ena zanimiva možnost je, da si pomagamo z dvema skladoma, s katerima lahko simuliramo vrsto. Elemente dodajamo na prvi sklad, pobiramo pa z drugega sklada. Če je drugi sklad kdaj prazen, preložimo celotno vsebino s prvega sklada na drugega. Pri tem se obrne vrstni red elementov in tisti z dna prvega sklada, ki je bil dodan prvi, se znajde na vrhu drugega sklada. Tudi ta rešitev ima amortizirano časovno zahtevnost vseh operacij zgolj $O(1)$, čeprav ima posamezna operacija odstranjevanja elementa časovno zahtevnost $O(n)$ v nekaterih primerih."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 6,
   "id": "409be1dd-9d32-4921-84d7-9a4cf3799c44",
   "metadata": {},
   "outputs": [],
   "source": [
    "class Queue2Stacks {\n",
    "private:\n",
    "    stack<int> in,out;\n",
    "public:\n",
    "    void push(int x) { in.push(x); }\n",
    "\n",
    "    int pop() {\n",
    "        if (out.empty()) {\n",
    "            while (!in.empty()) {\n",
    "                int x=in.top(); in.pop();\n",
    "                out.push(x);\n",
    "            }\n",
    "        }\n",
    "        int x=out.top(); out.pop();\n",
    "        return x;\n",
    "    }\n",
    "};"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 7,
   "id": "72a2a52b-d3c3-4ca5-9c0d-6c914a6e272f",
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "1\n",
      "2\n",
      "3\n"
     ]
    }
   ],
   "source": [
    "Queue2Stacks q2;\n",
    "q2.push(1); q2.push(2);\n",
    "cout << q2.pop() << endl;\n",
    "q2.push(3);\n",
    "cout << q2.pop() << endl;\n",
    "cout << q2.pop() << endl;"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "5b2e12d7-c439-4639-a22e-12eef97b8389",
   "metadata": {},
   "source": [
    "## Vrsta s prednostjo (*priority queue*)\n",
    "\n",
    "Vrsta s prednostjo ali prioritetna vrsta je podobna navadni vrsti, vendar ima vsak element prirejeno tudi *prioriteto*. Ko odstranjujemo elemente iz vrste, prejmemo najprej tistega z največjo (ali najmanjšo) prioriteto in ne prvega, ki je bil vstavljen. Enako kot v bolnišnici niso pacienti obravnavani po času prihoda, ampak glede na resnost zdravstvenega stanja.\n",
    "\n",
    "- `insert/push(x, p)`: Dodaj element `x` s prioriteto `p` v vrsto.\n",
    "- `pull/pop()`: Odstrani in vrni element z najvišjo prioriteto, ki se nahaja v vrsti.\n",
    "\n",
    "Tudi tu so pogoste operacije še `front/peek()`, `size()`, ...\n",
    "\n",
    "Pogosto so prioritete definirane implicitno preko operatorjev za primerjavo in zato nimamo eksplicitno podane prioritete ob vstavljanju elementa. Lahko pa vedno iz prioritet in elementov naredimo pare, ki jih dodajamo v vrsto.\n",
    "\n",
    "Implementacije se lahko lotimo na zelo enostaven način in elemente hranimo kar v seznamu. Pri iskanju elementa z najvišjo prioriteto preiščemo vse elemente v vrsti oz. seznamu in izberemo primernega. To ima seveda očitno pomanjkljivost, da `pop` ni konstantna operacija, ampak ima linearno časovno zahtevnost. \n",
    "\n",
    "Lahko bi elemente v vrsti s prednostjo hranili urejene. Če bi uporabili polje za hrambo urejenega seznama, imamo težavo pri vrivanju novega elementa, ker moramo vse zamakniti. Če bi uporabili povezan seznam, pa imamo težavo pri iskanju mesta za vrivanje, ker ne moremo delati bisekcije po indeksih.\n",
    "\n",
    "V nadaljevanju si bomo ogledali nekaj načinov, kako smo lahko pri tem bolj učinkoviti.\n",
    "\n",
    "Primeri: (C++: `priority_queue`), (Java: `PriorityQueue`), (Python: `heapq`)"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "ab1ee72a-31c6-4e33-b044-cbf68306b07b",
   "metadata": {},
   "source": [
    "### Kopica (*heap*)\n",
    "\n",
    "Najbolj tipična učinkovita implementacija prioritetne vrste je s kopico. Obstaja več vrst kopic, mi pa se bomo omejili na najbolj osnovno **dvojiško kopico**, za katero velja:\n",
    "\n",
    "- struktura: Dvojiška kopica je poravnano (*complete*) dvojiško drevo.\n",
    "- vsebina: Vsako vozlišče mora biti večje ali enako od svojih otrok (max-heap), v primeru obratne ureditve (min-heap) pa manjše ali enako. V nadaljevanju se bomo ukvarjali s slednjo.\n",
    "\n",
    "![Dvojiška kopica (wikipedija)](https://upload.wikimedia.org/wikipedia/commons/6/69/Min-heap.png)\n",
    "\n",
    "Drevesom se bomo bolj posvetili nekoliko kasneje, vendar si oglejmo par lastnosti dvojiške kopice:\n",
    "\n",
    "- Najmanjši element se nahaja v korenu drevesu.\n",
    "- Višina drevesa je logaritemsko odvisna od števila vozlišč, torej $O(\\log n)$.\n",
    "\n",
    "Dvojiško kopico lahko zaradi svoje lepe strukturne lastnosti predstavimo kar s tabelo, v katero po vrsti po nivojih zložimo vse vrednosti. Zgornji primer ustreza tabeli `{1, 2, 3, 17, 19, 36, 7, 25, 100}`. Zaradi prikladnosti bomo indeksiranje v tabeli začeli z 1 in ne 0, kot imamo sicer navado. Hitro se lahko prepričamo, da ima vozlišče na indeksu $i$ svoja otroka na indeksih $2i$ in $2i+1$. In obratno, vozlišče na indeksu $i$ ima svojega starša na indeksu $\\lfloor i/2 \\rfloor$.\n",
    "\n",
    "Razmislimo o dodajanju novega elementa. Da ohranimo strukturo, ga bomo vstavili na naslednje prosto mesto oz. ga dodali na konec tabele. S tem smo pokvarili urejenost, ki pa jo lahko popravimo. Nova vrednost je morda tako majhna, da paše nekam višje v drevesu (bližje korenu), zato jo bomo *dvignili*. Če je vozlišče manjše od starša, ga bomo zamenjali s staršem. In to ponavljali, dokler vozlišče ne pristane v korenu ali se ustavi na kakšnem primernem mestu.\n",
    "\n",
    "Dostop do najmanjšega elementa je trivialen. Brisanje najmanjšega pa malo manj. Zamenjali ga bomo z zadnjim elementom, nato pa popravili urejenost kopice. V tem primeru je nov element v korenu morda prevelik in ga je treba *potopiti* globlje. Zamenjali ga bomo z enim od njegovih otrok, in sicer z manjšim, ter to ponavljali.\n",
    "\n",
    "Prostorska zahtevnost je linearna, časovna zahtevnost obeh operacij pa sorazmerna z višino kopice, torej $O(\\log n)$."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 8,
   "id": "e5d107c4-0110-4ca3-b136-8b9bbacb790d",
   "metadata": {},
   "outputs": [],
   "source": [
    "class BinaryHeap {\n",
    "private:\n",
    "    vector<int> t={-1};\n",
    "public:\n",
    "    void push(int x) {\n",
    "        t.push_back(x);\n",
    "        int i=t.size()-1;\n",
    "        while (i>1 && t[i]<t[i/2]) {  // lift\n",
    "            swap(t[i],t[i/2]);\n",
    "            i/=2;\n",
    "        }\n",
    "    }\n",
    "\n",
    "    int pull() {\n",
    "        int x=t[1], i=1;\n",
    "        t[1]=t.back(); t.pop_back();\n",
    "        while (1) {  // sink\n",
    "            int j=i;\n",
    "            if (2*i<t.size() && t[2*i]<t[j]) j=2*i;\n",
    "            if (2*i+1<t.size() && t[2*i+1]<t[j]) j=2*i+1;\n",
    "            if (i==j) break;\n",
    "            swap(t[i],t[j]);\n",
    "            i=j;\n",
    "        }\n",
    "        return x;\n",
    "    }\n",
    "};"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "f8bbb2a9-6f2a-4c75-9c03-9d866e0bd34b",
   "metadata": {},
   "source": [
    "Vrsto s prednostjo lahko uporabimo tudi za urejanje elementov. Če uporabimo kopico, dobimo seveda **urejanje s kopico** (*heapsort*), ki ima časovno zahtevnost $O(n \\log n)$."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 9,
   "id": "8de9e6ac-e9f6-4d82-b0fd-297dcca34342",
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "1\n"
     ]
    }
   ],
   "source": [
    "BinaryHeap h;\n",
    "int n=100'000;\n",
    "default_random_engine rnd(123);\n",
    "for (int i=0;i<n;i++) h.push(rnd()%n);\n",
    "vector<int> s;\n",
    "for (int i=0;i<n;i++) s.push_back(h.pull());\n",
    "cout << is_sorted(s.begin(), s.end()) << endl;"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "b6421796-e382-4805-ab83-9f046f49142f",
   "metadata": {},
   "source": [
    "Kopico lahko zgradimo kot v prejšnjem primeru z zaporednim vstavljanjem elementov v vedno večjo kopico, kar ima časovno zahtevnost $O(n \\log n)$. Nekoliko presenetljivo pa je, da lahko kopico zgradimo zgolj v $O(n)$ časa s Floydovim algoritmom. Najprej elemente poljubno razvrstimo v kopico, nato pa jo popravljamo po nivojih od listov proti korenu, da postopoma nastajajo vedno večje pravilno urejene kopice. \n",
    "\n",
    "Naj bo $h$ višina kopice, kjer ima koren višino $h$, listi pa višino $0$. Ob popravljanju podkopice s korenom na višini $x$, moramo koren potopiti za največ $x$ korakov. Korenov, ki jih je treba potopiti globoko, je malo. Veliko pa je takih, ki jih ni treba potopiti prav daleč. Na višini $x$ se nahaja $2^{h-x}$ elementov, ki jih potopimo kvečjemu za $x$ nivojev: $\\sum_{x=0}^h x 2^{h-x} = \\sum_{x=0}^h x 2^{h}/2^x = n \\sum_{x=0}^h x/2^x < n \\sum_{x=0}^\\infty x/2^x = 2n = O(n)$ (da neskončna vrsta $x/2^x$ res konvergira k 2, se lahko prepričate s pomočjo odvoda geometrijske vrste)."
   ]
  },
  {
   "cell_type": "markdown",
   "id": "8cd8964b-9a66-4f56-96a3-8fec02cae949",
   "metadata": {},
   "source": [
    "### Seznam skupin\n",
    "\n",
    "Oglejmo si še nekoliko bolj domač pristop k združevanju prednosti seznama in polja, ki sicer ne bo vodil do kakšnega posebej znanega ali boljšega algoritma, bo pa koristna vaja in ilustracija pristopa, ki pride prav tudi kje drugje. Vzdrževati želimo urejen seznam elementov, kjer bo najmanjši element na začetku. V seznamu imamo težavo z iskanjem, na polju pa z vstavljanjem in brisanjem. Razdelimo celoten seznam z $n$ elementi na manjše skupine velikosti $k$: elemente vsake skupine bomo hranili v dinamičnem polju, celotne skupine pa bodo povezane v povezan seznam. Razmislimo o časovni zahtevnosti posamezne operacije.\n",
    "\n",
    "- iskanje: $O(n/k + \\log k)$ - najti moramo pravo skupino izmed $n/k$ skupin, nato pa lahko znotraj nje uporabimo bisekcijo z $\\log k$ operacijami.\n",
    "- vstavljanje/brisanje: $O(n/k + \\log k + k) = O(n/k + k)$ - ko najdemo mesto vstavljanja, moramo še vstaviti element in zamakniti vse ostale element v skupini.\n",
    "- brisanje najmanjšega: $O(k)$ - izbrišemo in zamaknemo elemente v prvi skupini (s kazalcem na najmanjšega lahko tudi $O(1)$).\n",
    "\n",
    "Najdražja operacija je vstavljanje elementa. Če želimo, da bo čim bolj učinkovita, morata biti člena $n/k$ in $k$ čim bolj enaka, sicer bo en od njiju dominiral. Iz enačbe $n/k = k$ hitro pridemo do zaključka, da bo najboljša izbira $k=O(\\sqrt n)$. Zato je pristop razbijanja na skupine znan tudi pod imenom **korenska dekompozicija** (*square root decomposition*).\n",
    "\n",
    "V prejšnji analizi smo se ukvarjali samo z eno operacijo, vendar lahko v zaporedju vstavljanj pride vsakič do vstavljanja v isto skupino in tako velikosti skupin ne bodo več uravnotežene. To lahko rešimo z razbijanjem prevelikih skupin ali združevanjem premajhnih. Še enostavnejša rešitev pa je, da vsakih $\\sqrt{n}$ operacij povsem na novo zgradimo uravnoteženo podatkovno strukturo skupin. Tako bo amortizirana časovna zahtevnost posamezne operacije še vedno $O(\\sqrt{n})$."
   ]
  },
  {
   "cell_type": "markdown",
   "id": "72761a78-8457-4c12-82a1-8f09404c2161",
   "metadata": {},
   "source": [
    "### Preskočni seznam (*skip list*)\n",
    "\n",
    "Zanimiva podatkovna struktura je preskočni seznam, ki je povezan seznam z dodatnimi (preskočnimi) povezavami, ki predstavljajo bližnjice in omogočajo hitrejše skakanje po seznamu. Običajno se uporablja za hranjenje *urejenega seznama* elementov oz. v našem primeru celih števil, kar izgleda priročno za implementacijo vrste s prednostjo.\n",
    "\n",
    "![Preskočni seznam (wikipedia)](https://upload.wikimedia.org/wikipedia/commons/8/86/Skip_list.svg)\n",
    "\n",
    "Zgornja slika prikazuje strukturo preskočnega seznama. Vsako vozlišče ima svojo \"višino\", ki je izbrana **naključno**. Vsak nov nivo pa je dodan z verjetnostjo $p$, ki je običanjo kar $1/2$. Nivoji so med seboj povezani v več povezanih seznamov. Tako se lahko pri iskanju elementa najprej premikamo po najvišjem nivoju, kjer delamo največje skoke. Nato se spustimo en nivo nižje in najdaljujemo tam, itd.\n",
    "\n",
    "Verjetnost, da ima element višino $h \\geq 1$ je $p^{h-1}$. Na prvem nivoju je vseh $n$ elementov, na drugem jih pričakujemo samo še $n/2$, na tretjem $n/4$ itd. Smiselno je torej imeti $O(\\log n)$ nivojev. Pričakovana prostorska zahtevnost je linearna $O(n)$, ker velja $n+n/2+n/4+... < 2n$. Recimo, da imamo naključno zgrajen preskočni seznam z $n$ elementi in želimo vanj vstaviti nov element oz. ga poiskati. Kakšna je pričakovana časovna zahtevnost te operacije? Razmislimo o pričakovanem številu skokov na posameznem nivoju. Če se od elementa premikamo v obratni smeri iskanja, se bomo premaknili nazaj do prvega večjega elementa. Vsak element na tem nivoju je večji z verjetnostjo $p$, pričakovano število korakov, da naletimo na večjega, pa je $1/p$ oz. v našem primeru kar 2. Pričakovana časovna zahtevnost vstavljanja ali iskanja posameznega elementa je torej $O(\\log n)$."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 10,
   "id": "ef779288-bdba-4fda-89d4-93499a1128fd",
   "metadata": {},
   "outputs": [],
   "source": [
    "class SkipNode {\n",
    "public:\n",
    "    int value, height;\n",
    "    vector<SkipNode*> next;\n",
    "    SkipNode(int _value, int _height) : value(_value), height(_height) { \n",
    "        next.resize(height);\n",
    "    }\n",
    "};"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 11,
   "id": "09e243b8-ed2d-4ab9-9164-0793a00cbf22",
   "metadata": {},
   "outputs": [],
   "source": [
    "class SkipList {\n",
    "private:\n",
    "    int max_height;\n",
    "    SkipNode *head;\n",
    "    default_random_engine rnd;\n",
    "public:\n",
    "    SkipList() : max_height(20) { \n",
    "        head = new SkipNode(-1, max_height);\n",
    "        rnd = default_random_engine(123);\n",
    "    }\n",
    "    ~SkipList() {  delete head; }\n",
    "\n",
    "    bool contains(int x) {\n",
    "        SkipNode *node = head;\n",
    "        for (int h=max_height-1;h>=0;h--) {\n",
    "            while (node->next[h] != NULL && node->next[h]->value < x) node = node->next[h];\n",
    "        }\n",
    "        return node->next[0] != NULL && node->next[0]->value == x;\n",
    "    }\n",
    "\n",
    "    void insert(int x) {\n",
    "        int height = 1;\n",
    "        while (height<max_height && rnd()%2==0) height++;\n",
    "        SkipNode *new_node = new SkipNode(x, height);\n",
    "        SkipNode *node = head;\n",
    "        for (int h=max_height-1;h>=0;h--) {\n",
    "            while (node->next[h] != NULL && node->next[h]->value < x) node = node->next[h];\n",
    "            if (h<height) {\n",
    "                new_node->next[h] = node->next[h];\n",
    "                node->next[h] = new_node;\n",
    "            }\n",
    "        }\n",
    "    }\n",
    "};"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "e1d64c48-b32b-424c-8b0d-1572f3c4f945",
   "metadata": {},
   "source": [
    "Testirajmo pravilnost in učinkovitost implementacije na primeru vstavljanja $n$ naključnih celih števil z intervala $[0,n-1]$. Na koncu pa preštejmo, koliko različnih števil imamo v seznamu. Zanimiva vaja iz verjetnosti je izračunati, da je pričakovano število približno 63% oz. natančneje $(1-1/e)$."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 12,
   "id": "de9e586e-5195-4df6-afca-36c0fe7f27eb",
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "razlicnih: 63307\n"
     ]
    }
   ],
   "source": [
    "SkipList sl;\n",
    "int n=100'000, st=0;\n",
    "default_random_engine rnd(123);\n",
    "for (int i=0;i<n;i++) sl.insert(rnd()%n);\n",
    "for (int i=0;i<n;i++) st+=sl.contains(i);\n",
    "cout << \"razlicnih: \" << st << endl;"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "ab141cd0-5a75-4777-8677-eb5e0b4344f5",
   "metadata": {},
   "source": [
    "## Množica (*set*)\n",
    "\n",
    "Množica je abstraktni podatkovni tip, ki kot že ime pove, hrani množico elementov. Bistveno je, da *ne vsebuje ponovitev enakih elementov*. Vsak element je torej prisoten v množici, ali pa ga ni. Ne predpisuje nobenega vrstnega reda elementov.\n",
    "\n",
    "- `insert/add(x)`: Dodaj element v množico, če v njej še ne obstaja.\n",
    "- `remove(x)`: Odstrani element iz množice.\n",
    "- `contains(x)`: Ugotovi, ali je element prisoten v množici, ali ne.\n",
    "\n",
    "Pogosto omogoča tudi način iteracije čez vse elemente množice in definira funkcije `size()`, `union()`, `intersection()`, ...\n",
    "\n",
    "Množico lahko implementiramo s seznamom, vendar to ne bo najbolj učinkovito. Na primer, pri dodajanju elementa moramo najprej ugotoviti, ali ta element že obstaja in v ta namen preveriti cel seznam, kar je operacija z linearno časovno zahtevnostjo. Ena možnost je, da uporabimo preskočni seznam, ki hrani elemente urejene in omogoča bolj učinkovito izvedbo omenjenih operacij, ki imajo logaritemsko časovno zahtevnost. Druga možnost je uporaba iskalnih dreves, kar si bomo ogledali kasneje, tretja pa uporaba razpršenih tabel.\n",
    "\n",
    "Množica je konceptualno sicer drugačna od slovarja, vendar pri implementaciji naletimo na podobne ovire. Zato si bomo v nadaljevanju pri slovarjih ogledali še pristop z uporabo *razpršenih tabel*, ki pride v poštev tudi za implementacijo množic.\n",
    "\n",
    "Različica množice je **vreča** (*multiset*, *bag*), ki lahko hrani tudi več ponovitev enakih elementov. Cilj te podatkovne strukture pa je še vedno učinkovito preverjanje vsebovanosti elementov v njej ter dodajanje in odstranjevanje.\n",
    "\n",
    "Primeri: (C++: `set`), (Java: `Set`), (Python: `set`)"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "cdf8af55-fdb9-4367-9be3-91edccee4899",
   "metadata": {},
   "source": [
    "## Slovar (*map, dictionary, associative array*)\n",
    "\n",
    "Slovar je abstraktni podatkovni tip, ki hrani pare (ključ, vrednost) oz. angleško (*key, value*). Pri tem pa se vsak ključ lahko pojavi največ enkrat (tu vidimo podobnost z množico). Vsakemu ključu je torej prirejena neka vrednost. V slovarju bi lahko npr. za vsakega študenta hranili njegove podatke. Ključi bi bile vpisne številke, vrednosti pa ime, priimek in morda še kakšni dodatni podatki. Obratno ne bi šlo, ker ima lahko več študentov enako kombinacijo imena in priimka in ga zato ne moremo uporabiti kot ključ v slovarju.\n",
    "\n",
    "- `insert(k,v)`: Dodaj par s ključem `k` in vrednostjo `v`, ali ga posodobi, če ključ že obstaja. Rečemo tudi, da pod ključ `k` shranimo vrednost `v`.\n",
    "- `remove(k)`: Odstrani par s ključem `k`.\n",
    "- `get/lookup(k)`: Vrni vrednosti, ki je shranjena poleg ključa `k`.\n",
    "\n",
    "Pogosto omogoča tudi način iteracije čez vse ključe in definira funkcije `size()`, `contains(k)`, ...\n",
    "\n",
    "Tudi tu bi lahko za implementacijo uporabili kar seznam parov, vendar naletimo na enake težave z učinkovitostjo kot pri množici. Pravzaprav lahko slovar uporabljamo kot množico, če uporabljamo ključe kot elemente množice, vrednosti pa ignoriramo.\n",
    "\n",
    "Primeri: (C++: `map`), (Java: `Map`), (Python: `dict`)"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "0a2099e7-97ad-4b72-b951-802ff4b2fea9",
   "metadata": {},
   "source": [
    "### Zgoščena/razpršena tabela\n",
    "\n",
    "Če bi želeli učinkovito implementirati slovar za primer, kjer so ključi 8-mestne vpisne številke študentov, bi si lahko vnaprej pripravili polje velikosti $10^8$ z indeksi od $0$ do $10^8-1$, ki ustrezajo vsem možnim vpisnim številkam. Seveda bo precej polj v taki tabeli praznih. S tem lahko implementiramo vso potrebno funkcionalnost slovarja v $O(1)$.\n",
    "\n",
    "Predlagana rešitev naleti na dve očitni oviri, če jo želimo uporabiti tudi v kakšnem drugem primeru:\n",
    "\n",
    "- Kaj če nimamo dovolj prostora za tabelo take velikost?\n",
    "- Kako naj ta pristop uporabimo v primeru ključev, ki niso cela števila, ampak npr. nizi?\n",
    "\n",
    "Primeri: (C++: `unordered_map`), (Java: `HashMap`), (Python: `dict`)\n",
    "\n",
    "Zgoščena (ali razpršena) tabela ponuja rešitev, ki temelji na **zgoščevalni/razpršilni funkciji** (*hash function*). Recimo, da si lahko privoščimo tabelo velikosti $H$. Zgoščevalna funkcija bo preslikala ključ v indeks te tabele. Za cela števila je npr. primerna zgoščevalna funkcija kar $h(x) = x \\mod H$. Če imamo opravka z nizi, moramo biti nekoliko bolj kreativni, npr. $h(s) = \\sum_i a^i s_i \\mod H$ za nek parameter $a$. Zgoščevalna funkcija mora preslikati enake elemente (ključe) v enake vrednosti. Lahko pa se tudi zgodi, da preslika različne elemente v enako vrednost.\n",
    "\n",
    "Preslikavi različnih elementov v enako vrednost rečemo **trk** (*collision*). Želimo si, da bi zgoščevalna funkcija čim bolj enakomerno porazdelila elemente med zgoščene vrednosti, da ne bi prihajalo do trkov. Beseda \"zgoščevalna\" izhaja iz tega, da velik nabor vrednosti (npr. imen in priimkov) zgostimo v manjši nabor indeksov. Beseda \"razpršilna\" pa iz tega, da naj bi funkcija elemente enakomerno razpršila oz. porazdelila po domeni indeksov.\n",
    "\n",
    "Do trkov bo na žalost prišlo, zato potrebujemo način za njihovo obvladovanje. Najbolj klasičen pristop je, da vrednosti pri vseh ključih, ki se preslikajo v isti indeks, hranimo v seznamu. Običajno kar povezanem seznamu, ki omogoča brisanje in dodajanje v konstantnem času. Temu rečemo **veriženje** (*chaining*) in je prikazano na spodnji sliki. Alternativen pristop, ki mu rečemo odprto naslavljanje (*open addressing*) ali zaprto zgoščevanje (*closed hashing*), uporablja zaporedje zgoščevalnih funkcij. Funkcije preizkuša po vrsti, dokler ne najde take, ki je vrnila zgoščeno vrednost, ki ustreza nekemu prostemu indeksu.\n",
    "\n",
    "![Zgoščena tabela z veriženjem (wikipedija)](https://upload.wikimedia.org/wikipedia/commons/d/d0/Hash_table_5_0_1_1_1_1_1_LL.svg)\n",
    "\n",
    "Želimo si čim manj trkov, saj moramo v primeru veriženja preiskati seznam vseh tistih, ki imajo enako zgoščeno vrednost in so shranjeni pod istim indeksom. Verjetnost trkov je odvisna od velikost tabele, števila elementov v njej in kvalitete zgoščevalne funkcije. Običajno merimo zasedenost tabele (*load factor*) kot razmerje med številom vnesenih elementov in kapaciteto tabele, $\\alpha = n / H$ . Ko ta faktor preseže 1, bo tudi ob idealni zgoščevalni funkciji, ki vsakemu elementu priredi svoj indeks, prihajalo do trkov. Ko zasedenost tabele doseže neko mejo, lahko izvedemo **ponovno zgoščevanje** (*rehashing*), kjer alociramo npr. dvakrat večjo tabelo, izračunamo nove zgoščene vrednosti vseh elementov in jih razporedimo po novi tabeli v upanju, da smo zmanjšali število trkov.\n",
    "\n",
    "V najslabšem primeru bomo imeli veliko nesrečo in se bodo vedno vsi ključi preslikali v isti indeks. V tem primeru so časovne zahtevnost vseh operacij $O(n)$, kar ni nič bolje od uporabe navadnega seznama. Bolj zanimiva je pričakovana časovna zahtevnost. Osredotočili se bomo na iskanje elementa, ki je glavna operacija. Predpostavili bomo, da lahko izračunamo zgoščeno vrednost v konstantnem času $O(1)$. Pozor, ta predpostavka ni res že v primeru dolgih nizov. Poleg tega bomo za analizo predpostavili, da zgoščevalna funkcija vrača naključne vrednosti med $1$ in $H$, ki so vse enako verjetne.\n",
    "\n",
    "- Najprej si oglejmo primer iskanja elementa, ki ne obstaja. V tem primeru so vsi indeksi oz. pripadajoči seznami enako verjetni. Pričakovana časovna zahtevnost je enaka pričakovani dolžini seznama, ki je ob naših predpostavkah enaka $\\alpha$. Torej $O(1+\\alpha)$ (tudi če je $\\alpha=0$, moramo izračunati zgoščeno vrednost, zato +1).\n",
    "- V primeru iskanja elementa, ki obstaja, niso vsi seznami enako verjetni. Bolj verjetno je, da bomo morali iskati v daljših seznamih, kot v krajših. Tudi v tem primeru se ob zgornjih predpostvkah izkaže, da je pričakovana časovna zahtevnost $O(1+\\alpha)$. Recimo, da je iskanje vsakega od obstoječih elementov enako verjetno. Pričakovana časovna zahtevnost bo enaka povprečni dolžini seznama, v katerega je bil ta element vstavljen. Če je bil dodan kot $i$-ti po vrsti, je bila takrat povprečna dolžina seznama $\\frac{i-1}{H}$. S tem lahko izračunamo pričakovano število operacij $\\frac{1}{n}\\sum_{i=1}^n (1 + \\frac{i-1}{H}) = O(1 + \\alpha)$.\n",
    "\n",
    "Če torej poskrbimo, da bo $\\alpha$, ki je delež zasedenosti tabele, neka konstantna vrednost, bodo imele tudi vse operacije pričakovano časovno zahtevnost, ki je konstantna, $O(1)$! Prav to dosežemo s ponovnim zgoščanjem.\n",
    "\n",
    "Predstavili smo najbolj klasično tehniko zgoščenih tabel. Seveda obstajajo še številne druge tehnike razreševanja trkov in upravljanja z velikostjo tabele, ki si jih lahko ogledate sami."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 13,
   "id": "8521817f-8e49-4721-a8d7-6f1dcbcb2ded",
   "metadata": {},
   "outputs": [],
   "source": [
    "class HashTable {\n",
    "public:\n",
    "    vector<list<pair<int,int>>> t;\n",
    "    int size, capacity;\n",
    "    int hash(int x) { return x % capacity; }\n",
    "    HashTable() { size=0; capacity=1; t.resize(capacity); }\n",
    "\n",
    "    void rehash() {\n",
    "        capacity *= 2;\n",
    "        vector<list<pair<int,int>>> t2(capacity);\n",
    "        for (int h=0; h<t.size(); h++) {\n",
    "            for (auto [key, value] : t[h]) {\n",
    "                int h2 = hash(key);\n",
    "                t2[h2].push_back({key, value});\n",
    "            }\n",
    "        }\n",
    "        t = t2;\n",
    "    }\n",
    "\n",
    "    void insert(int k, int v) {\n",
    "        if (size == capacity) { rehash(); }\n",
    "        int h = hash(k);\n",
    "        for (auto& [key, value] : t[h]) {\n",
    "            if (key == k) { value = v; return; }\n",
    "        }\n",
    "        size++;\n",
    "        t[h].push_back({k,v});\n",
    "    }\n",
    "\n",
    "    int get(int k) {\n",
    "        int h = hash(k);\n",
    "        for (auto [key, value] : t[h]) {\n",
    "            if (key == k) return value;\n",
    "        }\n",
    "        return -1;\n",
    "    }\n",
    "};"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "dd6b01b2-72c8-4a52-bb1b-0e83ab23c782",
   "metadata": {},
   "source": [
    "Vstavimo sedaj $n$ naključno izbranih števil v slovar, za vrednost pa bomo vedno uporabili kar 1. Vidimo, da je zopet približno 63% zasedenih vrednosti. Oglejmo si še povprečno in največjo dolžino seznama za veriženje v naši zgoščeni tabeli."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 14,
   "id": "fd2ebf74-c667-4ab9-9e76-2cfc7679ec80",
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "63307 65536\n",
      "0.965988 2\n"
     ]
    }
   ],
   "source": [
    "HashTable ht;\n",
    "int n=100'000, st=0;\n",
    "default_random_engine rnd(123);\n",
    "for (int i=0;i<n;i++) ht.insert(rnd()%n, 1);\n",
    "cout << ht.size << \" \" << ht.capacity << endl;\n",
    "int m=0, a=0;\n",
    "for (int h=0;h<ht.capacity;h++) {\n",
    "    int len=ht.t[h].size();\n",
    "    m = max(m, len);\n",
    "    a += len;\n",
    "}\n",
    "cout << (double)a/ht.capacity << \" \" << m << endl;"
   ]
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "C++17",
   "language": "C++17",
   "name": "xcpp17"
  },
  "language_info": {
   "codemirror_mode": "text/x-c++src",
   "file_extension": ".cpp",
   "mimetype": "text/x-c++src",
   "name": "c++",
   "version": "17"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 5
}