Categoría: Data Structures-Heap

Encuentre valores mínimos y máximos entre todos los Nodes hoja máximos de todos los posibles Binary Max Heap

Posted on by Rudeus Greyrat

Dado un entero positivo N , la tarea es encontrar los elementos más grandes y más pequeños, a partir de los Nodes de hoja máximos de cada montón máximo binario posible formado al tomar los primeros N números naturales como el valor de los Nodes del montón máximo binario. Ejemplos: Entrada: N = 2 Salida: … Continue reading «Encuentre valores mínimos y máximos entre todos los Nodes hoja máximos de todos los posibles Binary Max Heap»

Estructuras de datos | Montón | Pregunta 3

Posted on by Rudeus Greyrat

Un montón máximo de 3 arios es como un montón máximo binario, pero en lugar de 2 hijos, los Nodes tienen 3 hijos. Un montón de 3 arios se puede representar mediante una array de la siguiente manera: la raíz se almacena en la primera ubicación, a[0], los Nodes en el siguiente nivel, de izquierda … Continue reading «Estructuras de datos | Montón | Pregunta 3»

Cola de prioridad usando Binary Heap

Posted on by Rudeus Greyrat

Priority Queue es una extensión de la cola con las siguientes propiedades:   Cada elemento tiene una prioridad asociada. Un elemento con prioridad alta se elimina de la cola antes que un elemento con prioridad baja. Si dos elementos tienen la misma prioridad, se sirven según su orden en la cola. Un montón binario es un … Continue reading «Cola de prioridad usando Binary Heap»

Estructuras de datos | Montón | Pregunta 7

Posted on by Rudeus Greyrat

Tenemos un montón binario en n elementos y deseamos insertar n elementos más (no necesariamente uno tras otro) en este montón. El tiempo total requerido para esto es (A) (logn) (B) (n) (C) (nlogn) (D) (n^2) (A) A (B) B (C) C (D) D Respuesta : (B) Explicación: Podemos reducir el problema a Build Heap … Continue reading «Estructuras de datos | Montón | Pregunta 7»

Estructuras de datos | Montón | Pregunta 4

Posted on by Rudeus Greyrat

Suponga que los elementos 7, 2, 10 y 4 se insertan, en ese orden, en el montón 3-ario máximo válido que se encuentra en la pregunta anterior: ¿Cuál de las siguientes es la secuencia de elementos en la array que representa el montón resultante? (A) 10, 7, 9, 8, 3, 1, 5, 2, 6, 4 … Continue reading «Estructuras de datos | Montón | Pregunta 4»

Estructuras de datos | Montón | Pregunta 5

Posted on by Rudeus Greyrat

Considere un montón máximo binario implementado usando una array. ¿Cuál de las siguientes arrays representa un montón máximo binario? (GATE CS 2009) (A) 25,12,16,13,10,8,14 (B) 25,12,16,13,10,8,14 (C) 25,14,16,13,10, 8,12 (D) 25,14,12,13,10,8,16 Respuesta: (C) Explicación: un árbol es un montón máximo si los datos en cada Node del árbol son mayores o iguales que los de … Continue reading «Estructuras de datos | Montón | Pregunta 5»

Heapq con predicado personalizado en Python

Posted on by Rudeus Greyrat

Requisito previo: módulo heapq El módulo heapq tiene varias funciones que toman la lista como un parámetro y la organizan en un orden de montón mínimo. El problema con estas funciones es que esperan una lista o una lista de tuplas como parámetro. No admiten comparaciones entre otros iterables u objetos. Por ejemplo, considere un … Continue reading «Heapq con predicado personalizado en Python»

Estructuras de datos | Montón | Pregunta 8

Posted on by Rudeus Greyrat

En un montón mínimo con n elementos con el elemento más pequeño en la raíz, el séptimo elemento más pequeño se puede encontrar en el tiempo a) (n log n) b) (n) c) (log n) d) (1) La pregunta no estaba clara en el examen GATE original. Para mayor claridad, suponga que no hay duplicados … Continue reading «Estructuras de datos | Montón | Pregunta 8»

Implementación de caché de uso menos frecuente (LFU)

Posted on by Rudeus Greyrat

El uso menos frecuente (LFU) es un algoritmo de almacenamiento en caché en el que el bloque de caché utilizado con menos frecuencia se elimina cada vez que se desborda la memoria caché. En LFU verificamos la página anterior, así como la frecuencia de esa página y si la frecuencia de la página es mayor … Continue reading «Implementación de caché de uso menos frecuente (LFU)»

Estructuras de datos | Montón | Pregunta 6

Posted on by Rudeus Greyrat

¿Cuál es el contenido de la array después de dos operaciones de eliminación en la respuesta correcta a la pregunta anterior? (A) 14,13,12,10,8 (B) 14,12,13,8,10 (C) 14,13,8,12,10 (D) 14,13,12,8,10 Respuesta: (D) Explicación: para los árboles Heap, la eliminación de un Node incluye las siguientes dos operaciones. 1) Reemplace la raíz con el último elemento en … Continue reading «Estructuras de datos | Montón | Pregunta 6»