Skip to content

Algorithm ​

Importe estruturas de dados, funções diretas e resultados de estudo de tyrus:algorithm. O módulo fornece implementações nativas e de alto desempenho de estruturas de dados clássicas, além de métricas determinísticas de algoritmos. Todos os tipos de handle são genéricos exceto FenwickTree, SegmentTree, SparseTable, SegmentTreeLazy, BitSet, BloomFilter e Trie. Handles nativos são liberados automaticamente quando a variável sai de escopo.

AlgoritmoDescriçãoPágina
UnionFind<T>Conjunto disjunto (union-find) com compressão de caminho e união por rankUnionFind
BinaryHeap<T>Fila de prioridade max-heap bináriaBinaryHeap
BinomialHeap<T>Fila de prioridade max-heap binomial com meld O(log n)BinomialHeap
Counter<T>Contador de frequência com preservação de ordem de inserçãoCounter
Deque<T>Fila de duas pontasDeque
FenwickTreeÁrvore de Fenwick (binary indexed tree) para somas de prefixoFenwickTree
SegmentTreeÁrvore de segmentos para consultas por intervalo e atualizações pontuaisSegmentTree
SparseTableTabela RMQ imutável para consultas de mínimo por intervaloSparseTable
SegmentTreeLazyÁrvore de segmentos para consultas e adições por intervaloSegmentTreeLazy
BitSetConjunto de bits compacto com operações de conjuntoBitSet
BloomFilterPertinência probabilística em conjuntos com taxa de falso positivo configurávelBloomFilter
Graph<N, W>Grafo direcionado com pesos, criação automática de nós e renderização DOTGraph
bfs / bfsInfoTravessia em largura ou seu resultado de estudoBFS
dfs / dfsInfoTravessia em profundidade iterativa ou seu resultado de estudoDFS
iddfs / iddfsInfoTravessia com aprofundamento iterativo ou seu resultado de estudoIDDFS
dijkstra / dijkstraInfoMenor caminho com pesos não negativos ou seu resultado de estudoDijkstra
aStar / aStarInfoMenor caminho com heurística ou seu resultado de estudoA*
bellmanFord / bellmanFordInfoMenores caminhos com pesos negativos ou seu resultado de estudoBellman-Ford
floydWarshall / floydWarshallInfoMenores caminhos entre todos os pares densos ou seu resultado de estudoFloyd-Warshall
spfa / spfaInfoMenores caminhos baseados em fila ou seu resultado de estudoSPFA
johnson / johnsonInfoMenores caminhos entre todos os pares esparsos ou seu resultado de estudoJohnson
kruskalFloresta geradora mínima com conjuntos disjuntoskruskal
primÁrvore geradora mínima com fila de prioridadeprim
boruvkaFloresta geradora mínima para grafos densosboruvka
steinerTreeÁrvore de conexão ponderada de terminaissteinerTree
edmondsKarpFluxo máximo com caminhos aumentantes em larguraedmondsKarp
dinicFluxo máximo com grafos de níveisdinic
pushRelabelFluxo máximo com alturas de vérticespushRelabel
minCutCorte mínimo obtido do fluxo máximominCut
minCostMaxFlowFluxo máximo de custo mínimominCostMaxFlow
topologicalSortKahnOrdenação topológica por graus de entradatopologicalSortKahn
topologicalSortDfsOrdenação topológica por DFStopologicalSortDfs
tarjanSccComponentes fortemente conexos com TarjantarjanScc
kosarajuSccComponentes fortemente conexos com KosarajukosarajuScc
fleuryEulerianCaminho Euleriano com FleuryfleuryEulerian
hierholzerEulerianCaminho Euleriano com HierholzerhierholzerEulerian
findBridgesDetecção de pontesfindBridges
findCutVerticesDetecção de pontos de articulaçãofindCutVertices
biconnectedComponentsDecomposição em componentes biconexosbiconnectedComponents
edmondsBlossomEmparelhamento máximo em grafo geraledmondsBlossom
hungarianAtribuição de custo mínimohungarian
mergeSort / mergeSortInfoOrdenação merge sort estável e seu resultado de estudomergeSort
quickSort / quickSortInfoQuick sort médio ou seu resultado de estudoquickSort
heapSort / heapSortInfoHeap sort ou seu resultado de estudoheapSort
countingSort / countingSortInfoCounting sort ou seu resultado de estudocountingSort
radixSort / radixSortInfoRadix sort ou seu resultado de estudoradixSort
bucketSort / bucketSortInfoBucket sort ou seu resultado de estudobucketSort
timSort / timSortInfoOrdenação híbrida ou seu resultado de estudotimSort
insertionSort / insertionSortInfoInsertion sort ou seu resultado de estudoinsertionSort
shellSort / shellSortInfoShell sort ou seu resultado de estudoshellSort
selectionSort / selectionSortInfoSelection sort ou seu resultado de estudoselectionSort
bubbleSort / bubbleSortInfoBubble sort imediato ou resultado de estudo com métricas semânticasBubble sort
shakerSort / shakerSortInfoBubble sort bidirecional ou seu resultado de estudoshakerSort
quickselectSeleciona o k-ésimo menor valor sem ordenar o array inteiroquickselect
binarySearchBusca binária em um array crescente de inteirosbinarySearch
interpolationSearchBusca sensível à distribuição em um array de inteiros uniformemente distribuídointerpolationSearch
exponentialSearchBusca em um array crescente expandindo o intervalo exponencialmenteexponentialSearch
kmpSearchBusca exata de substring com pré-processamento de prefixoskmpSearch
zAlgorithmPré-processamento de correspondência de prefixos de uma stringzAlgorithm
rabinKarpBusca de substring com rolling hashrabinKarp
boyerMooreBusca de substring com a regra do mau caractereboyerMoore
ahoCorasickBusca de múltiplos padrões retornando as correspondênciasahoCorasick
levenshteinDistância de edição entre duas stringslevenshtein
TrieÁrvore de prefixo para palavras de stringTrie
suffixArrayConstrução de suffix array lexicográfico para stringssuffixArray
SuffixTreeSuffix tree construída com o algoritmo de Ukkonen, com extração de suffix array lexicográficosuffixTreeUkkonen
LcaTabelas de menor ancestral comum sobre uma árvore com consultas em O(log n)lcaBinaryLifting
HldDecomposição heavy-light com consultas de caminho em cadeias O(log n)heavyLightDecomposition
CentroidDecomposição centroid com profundidade O(log n) na árvore centroidcentroidDecomposition
LinkedList<T>Lista simplesmente encadeadaLinkedList
DoubleLinkedList<T>Lista duplamente encadeadaDoubleLinkedList
AvlTree<T>Árvore AVL autobalanceada (conjunto ordenado)AvlTree
RedBlackTree<T>Árvore rubro-negra autobalanceada (conjunto ordenado)RedBlackTree
SplayTree<T>Árvore de splay autoadjustável (conjunto ordenado)SplayTree
Treap<T>Treap aleatório (conjunto ordenado)Treap
SortedSet<T>Conjunto ordenado sobre uma árvore binária de busca balanceadaSortedSet
SkipList<T>Skip list aleatória (conjunto ordenado)SkipList
SortedMap<K, V>Mapa ordenado de chave → valor sobre uma árvore binária de busca balanceadaSortedMap