Fibonacci Heap es una colección de árboles con propiedades min-heap o max-heap. En Fibonacci Heap, los árboles pueden tener cualquier forma, incluso todos los árboles pueden ser Nodes únicos (esto es diferente a Binomial Heap donde cada árbol tiene que ser un árbol binomial). En este artículo, discutiremos la operación de inserción y unión en … Continue reading «Montón de Fibonacci: inserción y unión»
Es muy recomendable comprender completamente Proto Van Emde Boas Tree . Van Emde Boas Tree admite operaciones de búsqueda, sucesor, predecesor, inserción y eliminación en tiempo O (lglgN), que es más rápido que cualquiera de las estructuras de datos relacionadas, como cola de prioridad, árbol de búsqueda binaria, etc. Van Emde Boas Tree funciona con … Continue reading «Árbol de boas de Van Emde | Conjunto 1 | Fundamentos y Construcción»
Dada una array arr[] de tamaño n y q consultas y un entero k . Cada consulta consta de un rango de índice [l, r] y la tarea es contar el número de pares de índices i y j tales que l ≤ i ≤ j ≤ r (indexación basada en 1) y el xor … Continue reading «Consultas de rango para encontrar el número de subarreglos con un xor dado»
¿Cómo implementar el esquema de almacenamiento en caché LRU? ¿Qué estructuras de datos se deben utilizar? Se nos da el número total de páginas posibles que se pueden referir. También se nos da un tamaño de caché (o memoria) (la cantidad de marcos de página que el caché puede contener a la vez). El esquema … Continue reading «Implementación de caché LRU – Part 2»
Nos dan una array de números enteros y un rango, necesitamos encontrar si el subarreglo que cae en este rango tiene valores en forma de montaña o no. Se dice que todos los valores del subarreglo tienen la forma de una montaña si todos los valores aumentan o disminuyen o primero aumentan y luego disminuyen. Más … Continue reading «Encuentra si un subarreglo tiene forma de montaña o no»
Dada una array binaria. La tarea es encontrar el par de filas en la array binaria que tiene la máxima diferencia de bits. Ejemplos: Input: mat[][] = {{1, 1, 1, 1}, {1, 1, 0, 1}, {0, 0, 0, 0}}; Output : (1, 3) Bit difference between row numbers 1 and 3 is maximum with value … Continue reading «Encuentre un par de filas en una array binaria que tenga la máxima diferencia de bits»
Comprueba si un gráfico dado contiene un ciclo o no. Ejemplo: Input: Output: Graph contains Cycle. Input: Output: Graph does not contain Cycle. Prerrequisitos: conjunto disjunto (o unión-búsqueda) , unión por rango y compresión de ruta Ya hemos discutido unión-búsqueda para detectar ciclos . Aquí discutimos la búsqueda por compresión de ruta, donde se modifica … Continue reading «Algoritmo de búsqueda de unión | (Unión por rango y búsqueda por compresión de ruta optimizada)»
Prerequisite : Segment Tree Persistency in Data Structure Segment Tree es en sí mismo una gran estructura de datos que entra en juego en muchos casos. En este post introduciremos el concepto de Persistencia en esta estructura de datos. Persistencia, simplemente significa retener los cambios. Pero, obviamente, retener los cambios provoca un consumo adicional de … Continue reading «Árbol de segmentos persistentes | Serie 1 (Introducción)»
Dada una array de palabras, encuentre todos los prefijos únicos más cortos para representar cada palabra en la array dada. Supongamos que ninguna palabra es prefijo de otra. Ejemplos: Input: arr[] = {«zebra», «dog», «duck», «dove»} Output: dog, dov, du, z Explanation: dog => dog dove => dov duck => du zebra => z Input: arr[] … Continue reading «Encuentre el prefijo único más corto para cada palabra en una lista dada | Conjunto 1 (Usando Trie)»
La descomposición Heavy Light (HLD) es una de las técnicas más utilizadas en la programación competitiva . Problema de ejemplo: comprendamos la descomposición pesada-ligera (HLD) con la ayuda del siguiente ejemplo. Supongamos que tenemos un árbol desequilibrado (no necesariamente un árbol binario) de n Nodes , y tenemos que realizar operaciones en el árbol para … Continue reading «Descomposición ligera pesada | Serie 1 (Introducción)»