Please enable JavaScript.
Coggle requires JavaScript to display documents.
Data Structures - Coggle Diagram
Data Structures
Estruturas de dados lineares
static array
Coleção de dados de tamanho fixo
dynamic array
vector
Coleção de dados que pode sofrer redimensionamento
Operações de busca e de ordenação são geralmente feitas em estruturas de dados desse tipo
Ordenação
Bubble/Selection/Insert Sort(O(n²))
Merge/Heap/Quick Sort (O(n log n))
Counting/Radix/Bucket Sort (O(n))
Busca
Linear Search (O(n))
Binary Search (O(log n))
Hashing (O(1))
bitset
array de booleanos que suporta algumas operações interessantes como set, reset, test, etc
Bitmask
Uma bitmask é um conjunto de valores booleanos, dessa forma, podemos representar essa estrutura como um
inteiro/string de bits
Linked List
Usa ponteiros para criar uma coleção de elementos
Stack
Realiza inserções/remoções no topo da estrutura em O(1)
Last In First Out (LIFO)
Queue/Deque
Insere ao final e remove no começo
First In First Out (FIFO)
Estruturas de dados que nós implementamos
Grafos
Uma grafo pode ser representado por par ordenado que possui um conjunto de vértices (V) e um conjunto de arestas (E):
G = (V, E)
Matriz de Adjacências
Lista de Adjacências
Lista de Arestas
Grafos Implícitos
Alguns grafos não precisam ser guardados em uma estrutura de grafo, por exemplo um grid map
Union-Find Disjoint Sets
Representa uma coleção de conjuntos disjuntos
Com essa estrutura conseguimos checar rapidamente se os elementos estão ligados de alguma forma ou não
Segment Tree
É uma estrutura utilizada para responder dinamicamente perguntas sobre um maior/menor elemento dentro de um certo alcance
Pode ser implementada na forma de um array assim como uma heap
Geralmente se os elementos forem estáticos utilizar segment tree se torna desnecessário
Usar uma DP seria mais eficiente
Binary Indexed Tree (Fenwick Tree)
Estrutura de dados usada para implementar uma tabela de frequências cumulativas dinâmica
Pode também ser utilizada para resolver problemas de soma em um determinado alcance (Range sum query - RSQ)
Facilmente implementável com um vector para garantir flexibilidade
Estruturas de dados não lineares
Balanced Binary Search Tree (BST)
Uma BST pode realizar operações de busca e inserção em O(log n), porém não pode haver uma degeneração
Implementações de uma BST como AVL e RB garantem que a árvore esteja balanceada
O map/set de C++ utiliza essas implementações garantindo que as operações aconteçam sem uma degeneração
Heap/Priority Queue
Possui uma organização de árvore assim como a BST, porém precisa ser uma árvore completa. Ou seja, a inserção ocorre de cima para baixo da esquerda para a direita
Uma heap pode ser representada em um formato de lista ignorando o primeiro elemento
Uma heap não garante uma busca eficiente, mas garante que o topo é sempre o maior/menor elemento