# Strutture Dati
:::danger
da completare
:::
## Vettori
**Se il vettore di lunghezza n non è ordinato**
- search, max, min, succesor -> $\mathcal{O}(n)$
- insert, delete -> $\mathcal{O}(n)$

**Se il vettore è ordinato**
- minimo e massimo -> $\mathcal{O}(1)$
- search, succesor -> $\mathcal{O}(\log(n))$
- insert,delete -> $\mathcal{O}(n)$

**inserire in un vettore pieno**
- rifiutati in $\mathcal{O}(1)$ (se teniamo conteggio)
- riallocazione in $\mathcal{O}(n)$

## linked list
**code**

struct El {
	int data;
	struct El *prox;
} Elemento;

**se la lista non è ordinata**
- search,min,max, succesor -> $\mathcal{O}(n)$
- insert -> $\mathcal{O}(1)$
- delete (without reference) -> $\mathcal{O}(n)$
- delete (with reference) -> $\mathcal{O}(1)$

**se la lista è ordinata**
- uno tra max e min è $\mathcal{O}(1)$, l'altro $\mathcal{O}(n)$
- se ho reference ad entrambi $\mathcal{O}(1)$
- search , successor -> $\mathcal{O}(n)$
- insert, delete -> $\mathcal{O}(n)$

## Stack
**code**

//todo

**funzioni**
- Push(S,e) -> aggiunge e in cima alla pila $\mathcal{O}(1)$
- Pop(S) -> return la cima della pila e la elimina dalla pila $\mathcal{O}(1)$
- Empty(S) -> controlla se il succ della testa è NULL $\mathcal{O}(1)$

## Queues
**code**

//todo

**funzioni**
- Enqueue(Q,e) -> aggiunge e alla fine della coda
- Dequeue(Q) -> restituisce il primo della coda, lo elimina della coda
- Empty(Q) -> return true se la coda è vuota

**realizzazione con vettore**
- vettore lungo l con indice iniziale in 0
- uso due indici *tail * & *head*
- indici incrementati mod l
- Enqueue(Q,e) : se n < l inserisco in A[tail] , n++, tail++. $\mathcal{O}(1)$
- Dequeue(Q): se n>0 restituisci A[head], n--, head++. $\mathcal{O}(1)$
- Empty(S): return true se n==0 . $\mathcal{O}(1)$
- Reallocare costa $\Theta(n)$

**realizzazione con lista**
- usiamo un puntatore tail, oltre a quello head
- Enqueue(Q,e) : inserisci l'elemento in coda alla lista, aggiorna tail. $\mathcal{O}(1)$
- Dequeue(Q): return l'elemento puntato da head, aggiorno head. $\mathcal{O}(1)$
- Empty(Q) : return true if head=tail. $\mathcal{O}(1)$

## Dizionari
contiene elementi accessibili direttamente con la loro **chiave**.
Per ottimizzare lo spazio calcolo una funzione della chiave h(k) -> funzione di **hash**

**Indirizzamento chiuso (open hashing)**
- ogni riga della tabella, chiamata *bucket*, contiene la testa di una lista.
- nell'eventualità di una collisione l'elemento viene aggiunto alla lista in $\mathcal{O}(1)$
- per fare search calcolo la chiave k e cerco nell'intero bucket h(k)

**Indirizzamento aperto (closed hashing)**
- in caso di collisione si seleziona un altro bucket in modo deterministico
- se non si trovano bucket
- rifiuta in $\Theta(n)$
- si rialloca e si hasha di nuovo tutto in $\Theta(n)$
- nella ricerca si deve implementare la stessa regola deterministica
- per la cancellazione si usa una *tombstone*, che non corrisponde a nessuna chiave

## Alberi binari di ricerca (BST)
per essere BST deve valere per ogni nodo x che
- se y è nel sottoalbero sinistro x -> y.key < x.key
- se y è nel sottoalbero destro x -> y.key > x.key

è importante progettare funzioni che preservino queste proprietà

## Heap

- Struttura ad albero con la chiave del nodo padre sempre maggiore - +nel caso di max-heap+ - di quella dei figli
- Le funzioni su un max-heap sono: Max, Inserisci, Cancella-Max, Costruisci-max-heap, Max-heapify

#### Costruisci-Max-Heap
la funzione costruisce un heap a partire da un array A e un'indice n

Costruisci-Max-Heap(A){
A.heapsize <- A.length
for i <- floor(A.length/2) downto 1
    Max-Heapify(A,i)



Max-Heapify(A,n)
1 l   LEFT(n)
2 r   RIGHT(n)
3 if l  A:heapsize and A[l] > A[n]
4 posmax   l
5 else posmax   n
6 if r  A:heapsize and A[r] > A[posmax]
7 posmax   r
8 if posmax 6= n
9 Swap(A[n];A[posmax])
10 Max-Heapify(A; posmax)