Skip to content

Algorithm ​

Importe estructuras de datos, funciones directas y resultados de estudio de tyrus:algorithm. El módulo proporciona implementaciones nativas y de alto rendimiento de estructuras de datos clásicas, además de métricas deterministas de algoritmos. Todos los tipos de handle son genéricos excepto FenwickTree, SegmentTree, SparseTable, SegmentTreeLazy, BitSet, BloomFilter y Trie. Los handles nativos se liberan automáticamente cuando la variable sale del ámbito.

AlgoritmoDescripciónPágina
UnionFind<T>Conjunto disjunto (union-find) con compresión de camino y unión por rangoUnionFind
BinaryHeap<T>Cola de prioridad max-heap binariaBinaryHeap
BinomialHeap<T>Cola de prioridad max-heap binomial con meld O(log n)BinomialHeap
Counter<T>Contador de frecuencia con preservación de orden de inserciónCounter
Deque<T>Cola de doble extremoDeque
FenwickTreeÁrbol de Fenwick (binary indexed tree) para sumas de prefijoFenwickTree
SegmentTreeÁrbol de segmentos para consultas por intervalo y actualizaciones puntualesSegmentTree
SparseTableTabla RMQ inmutable para consultas de mínimo por intervaloSparseTable
SegmentTreeLazyÁrbol de segmentos para consultas y sumas por intervaloSegmentTreeLazy
BitSetConjunto de bits compacto con operaciones de conjuntoBitSet
BloomFilterPertenencia probabilística a conjuntos con tasa de falso positivo configurableBloomFilter
Graph<N, W>Grafo dirigido ponderado con creación automática de nodos y renderizado DOTGraph
bfs / bfsInfoRecorrido en anchura o su resultado de estudioBFS
dfs / dfsInfoRecorrido en profundidad iterativa o su resultado de estudioDFS
iddfs / iddfsInfoRecorrido con profundización iterativa o su resultado de estudioIDDFS
dijkstra / dijkstraInfoRuta más corta con pesos no negativos o su resultado de estudioDijkstra
aStar / aStarInfoRuta más corta con heurística o su resultado de estudioA*
bellmanFord / bellmanFordInfoRutas más cortas con pesos negativos o su resultado de estudioBellman-Ford
floydWarshall / floydWarshallInfoRutas más cortas densas entre todos los pares o su resultado de estudioFloyd-Warshall
spfa / spfaInfoRutas más cortas basadas en cola o su resultado de estudioSPFA
johnson / johnsonInfoRutas más cortas dispersas entre todos los pares o su resultado de estudioJohnson
kruskalBosque de expansión mínima con conjuntos disjuntoskruskal
primÁrbol de expansión mínima con cola de prioridadprim
boruvkaBosque de expansión mínima para grafos densosboruvka
steinerTreeÁrbol de conexión ponderado de terminalessteinerTree
edmondsKarpFlujo máximo con caminos aumentantes en anchuraedmondsKarp
dinicFlujo máximo con grafos de nivelesdinic
pushRelabelFlujo máximo con alturas de vérticespushRelabel
minCutCorte mínimo obtenido del flujo máximominCut
minCostMaxFlowFlujo máximo de coste mínimominCostMaxFlow
topologicalSortKahnOrdenación topológica por grados de entradatopologicalSortKahn
topologicalSortDfsOrdenación topológica por DFStopologicalSortDfs
tarjanSccComponentes fuertemente conexos con TarjantarjanScc
kosarajuSccComponentes fuertemente conexos con KosarajukosarajuScc
fleuryEulerianCamino Euleriano con FleuryfleuryEulerian
hierholzerEulerianCamino Euleriano con HierholzerhierholzerEulerian
findBridgesDetección de puentesfindBridges
findCutVerticesDetección de puntos de articulaciónfindCutVertices
biconnectedComponentsDescomposición en componentes biconexosbiconnectedComponents
edmondsBlossomEmparejamiento máximo en grafo generaledmondsBlossom
hungarianAsignación de coste mínimohungarian
mergeSort / mergeSortInfoOrdenación merge sort estable y su resultado de estudiomergeSort
quickSort / quickSortInfoQuick sort promedio o su resultado de estudioquickSort
heapSort / heapSortInfoHeap sort o su resultado de estudioheapSort
countingSort / countingSortInfoCounting sort o su resultado de estudiocountingSort
radixSort / radixSortInfoRadix sort o su resultado de estudioradixSort
bucketSort / bucketSortInfoBucket sort o su resultado de estudiobucketSort
timSort / timSortInfoOrdenación híbrida o su resultado de estudiotimSort
insertionSort / insertionSortInfoInsertion sort o su resultado de estudioinsertionSort
shellSort / shellSortInfoShell sort o su resultado de estudioshellSort
selectionSort / selectionSortInfoSelection sort o su resultado de estudioselectionSort
bubbleSort / bubbleSortInfoBubble sort inmediato o resultado de estudio con métricas semánticasBubble sort
shakerSort / shakerSortInfoBubble sort bidireccional o su resultado de estudioshakerSort
quickselectSelecciona el k-ésimo menor valor sin ordenar todo el arrayquickselect
binarySearchBúsqueda binaria en un array ascendente de enterosbinarySearch
interpolationSearchBúsqueda sensible a la distribución en un array de enteros uniformemente distribuidointerpolationSearch
exponentialSearchBúsqueda en un array ascendente expandiendo el intervalo exponencialmenteexponentialSearch
kmpSearchBúsqueda exacta de subcadenas con preprocesamiento de prefijoskmpSearch
zAlgorithmPreprocesamiento de coincidencias de prefijos de una cadenazAlgorithm
rabinKarpBúsqueda de subcadenas con rolling hashrabinKarp
boyerMooreBúsqueda de subcadenas con la regla del mal carácterboyerMoore
ahoCorasickBúsqueda de múltiples patrones devolviendo coincidenciasahoCorasick
levenshteinDistancia de edición entre dos cadenaslevenshtein
TrieÁrbol de prefijo para palabras de stringTrie
suffixArrayConstrucción de suffix array lexicográfico para stringssuffixArray
SuffixTreeSuffix tree construido con el algoritmo de Ukkonen, con extracción de suffix array lexicográficosuffixTreeUkkonen
LcaTablas de menor ancestro común sobre un árbol con consultas en O(log n)lcaBinaryLifting
HldDescomposición heavy-light con consultas de ruta en cadenas O(log n)heavyLightDecomposition
CentroidDescomposición centroid con profundidad O(log n) en el árbol centroidcentroidDecomposition
LinkedList<T>Lista simplemente enlazadaLinkedList
DoubleLinkedList<T>Lista doblemente enlazadaDoubleLinkedList
AvlTree<T>Árbol AVL autoequilibrado (conjunto ordenado)AvlTree
RedBlackTree<T>Árbol rojo-negro autoequilibrado (conjunto ordenado)RedBlackTree
SplayTree<T>Árbol de splay autoadaptativo (conjunto ordenado)SplayTree
Treap<T>Treap aleatorio (conjunto ordenado)Treap
SortedSet<T>Conjunto ordenado sobre un árbol binario de búsqueda balanceadoSortedSet
SkipList<T>Skip list aleatoria (conjunto ordenado)SkipList
SortedMap<K, V>Mapa ordenado de clave → valor sobre un árbol binario de búsqueda balanceadoSortedMap