Rever

8.3.2 numeração de binary tree

Binary search

Find index in a sorted list.

Priority queue

Uma lista onde cada item possui associado um sequencial de prioridade
Remover apenas o mínimo
Adicionar qualquer valor (sorted on insertion)

class PQ {
  add(k, v);
  peekMin();
  popMin();
  size();
}

Impls

List (sorted or unsorted)
Heap

Heap

An ordered, complete binary tree.

Altura h = log n since line size = 2^line

Insertion Insert at tree tail, bublle up.

Removal (min key) Remove root, bubble down.

Array-based tree Facilita a localização dos elementos (se comparado a uma linked list).

Complexidade O(1) ou O(logn).

Esquerda: pos_filho = 2 * pos_pai + 1

Direita: pos_filho = 2 * pos_pai + 2

Bottom-up construction ???

Sorting with a PQ Adicionar itens em uma PQ automaticamente os classifica.

Adaptable PQ guardando a posição de cada item na estrutura, permitindo atualização O(log n).

MAPS

Unsorted table map

type UnsortedTableMap = { k; v }[];

Iterate on O(n).

Hashmap

Hash code + compression fn
Polinomial hash codes, cyclic shift hash codes
Division/ MAD compression fns

Map types, Collision

Seperate chaining (nested containers)
Linear probing (walk for empty slots)
Load factors vs. efficiency (python has 2/3 factor)

Sorted maps

A map in a sorted table
Allows sorted key iteration at log n -- n
Slow insertion/update, since it is a table
Slower than hashmap for random access

Skip lists

Store the map in linked list for faster updates, use the following structure to make searches O(log n) on average (RNG)
Create tiered references (towers) of the base linked list with subsequently 1/2 items removed
Search iteration through "top" list mimics binary search

Sets

class Set {
    add(e)
    discard(e)
    contains(e): boolean
    contains(set: Set): boolean
}

Sets podem ser comparados a Maps sem valor (os dados são sempre chaves).

Tree traversal

Preorder

Pai, filho de esq a dir

function preOrder(node, visitFn) {
    visitFn(node)
    node.children().forEach(c => preOrder(c, visitFn))
}

Postorder

Filho de esq a dir, pai

function postOrder(node, visitFn) {
    node.children().forEach(c => postOrder(c, visitFn))
    visitFn(node)
}

Breadth-first

Avanço ordenado por nível

function breadthFirst(node, visitFn) {
    const queue = new Queue([node])
    while(queue.length) {
        const currentNode = queue.dequeue()
        visitFn(currentNode)
        queue.enqueue(...currentNode.children())
    }
}

BSTs

Binário (2 filhos)
Items à direita sempre são maiores

wkrueger/data-struct.md