Notas estruturas de dados

data-struct.md

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