Please enable JavaScript.
Coggle requires JavaScript to display documents.
Capítulo 2: Data Structures and Libraries - Coggle Diagram
Capítulo 2: Data Structures and Libraries
2.1 Overview and Motivation
Importância das estruturas de dados → eficiência em inserções, buscas, deleções, queries.
Usar bibliotecas prontas (STL, Java API).
Foco em força x fraquezas das estruturas + complexidade de espaço/tempo.
2.2 Linear DS with Built-in Libraries
Static Array
Vector / ArrayList (dinamicamente redimensionáveis)
Sorting & Searching
O(n²): Bubble, Selection, Insertion.
O(n log n): Merge, Quick, HeapSort.
Especiais: Radix, Bucket.
Array of Booleans → bitset
Bitmask (inteiros representando conjuntos)
Operações: set, clear, toggle, shift.
Linked List (list)
Stack (LIFO)
Queue (FIFO)
Deque (double-ended queue)
2.3 Non-Linear DS with Built-in Libraries
BST (map/set, TreeMap/TreeSet)
Operações O(log n).
Baseados em Red-Black Trees.
Heap / Priority Queue
Árvore binária completa.
Operações Insert, ExtractMax/Min.
Usado em Dijkstra, Prim, A*, etc.
Hash Table (unordered_map / HashMap)
Úteis, mas uso cuidadoso.
Evitar em competições salvo quando necessário.
2.4 Data Structures with Our Own Libraries
Graph Representations
Adjacency Matrix (O(V²))
Boa para grafos densos/pequenos.
Adjacency List (O(V+E))
Mais eficiente em grafos esparsos.
Edge List
Lista de arestas.
Implicit Graphs (ex.: tabuleiro de xadrez, grid).
Union-Find Disjoint Sets (UFDS)
Representa conjuntos disjuntos.
Operações: findSet, unionSet, isSameSet.
Heurísticas: Path compression + Union by rank.
Complexidade: quase O(1).
Segment Tree
Suporte a Range Queries (RMQ).
Estrutura hierárquica (O(n log n) build, O(log n) query/update).
Permite queries como mínimo, máximo, soma, etc.
Pode ser estendido para RMQ dinâmico.
Fenwick Tree (Binary Indexed Tree)
Alternativa mais simples que Segment Tree.
Operações RSQ (Range Sum Query) em O(log n).
Update em O(log n).
Baseada em manipulação de bits (LSOne).