¿Es una matriz que está en un orden ordenado un montón mínimo?

Si y no.

Un montón mínimo tiene una estructura de árbol binario y una matriz tiene una estructura de acceso aleatorio, por lo que, en ese sentido, no, son dos estructuras muy diferentes.

Pero si interpreta que la matriz tiene una estructura de árbol binario implícito, puede interpretarse como un montón dinámico válido.

• ¿Cuál es el significado de la simulación de recursividad?
• ¿Por qué son importantes los números primos para la seguridad informática?
• ¿Cuál es la diferencia entre quicksort y mergesort?
• ¿Cómo puedo encontrar la ruta más larga de un gráfico bidireccional utilizando el algoritmo BFS?
• ¿Cuál es la forma más eficiente de implementar la unión en varias tablas (> 5 tablas) usando SQL / ANSI SQL?

Un montón mínimo tiene tres propiedades:

1. Cada nodo tiene como máximo dos hijos
2. Cada padre está clasificado menos que sus hijos
3. El árbol binario está completo.

Una matriz a menudo se interpreta como un árbol binario donde los elementos secundarios de un índice dado [matemáticas] i [/ matemáticas] se encuentran en los índices [matemáticas] 2i + 1 [/ matemáticas] y [matemáticas] 2i + 2 [/ matemáticas] . Si la matriz tiene un tamaño inferior a [matemática] 2i + 1 [/ matemática] o [matemática] 2i + 2 [/ matemática], entonces esos hijos de [matemática] i [/ matemática] se consideran nulos .

Cuando una matriz se interpreta de esta manera, con esta implementación de un montón binario, se puede demostrar que cada padre tendrá un valor menor o igual que sus dos hijos. Por lo tanto, es un montón mínimo válido.

tl; dr:

Aquí hay una prueba de por qué es un montón mínimo válido (específicamente una matriz de enteros):

Enunciado: Una matriz de enteros ordenados en orden creciente es un montón mínimo válido.

debemos probar 3 cosas: cada nodo tiene como máximo dos hijos, el árbol (interpretado) está completo y el valor de cada nodo es menor que el valor de cada uno de sus hijos.

1. Cada nodo tiene como máximo dos hijos
1. deje que el árbol binario se interprete de manera tal que los hijos del índice [matemática] i [/ matemática] estén en índices [matemática] 2i + 1 [/ matemática] para todos [matemática] 2i + 1 <n [/ matemática] y [matemática ] 2i + 2 [/ matemática] para todos [matemática] 2i + 2 <n [/ matemática]
2. (a) define exactamente dos posibles hijos para cada nodo, por lo tanto (1) es verdadero
2. El árbol definido por (1.a) está completo
1. dejemos que x se defina como una potencia de 2 tal que [math] \ frac {n} {2} \ le x \ lt n [/ math]
2. que y se defina como una potencia de 2 tal que [matemática] n \ le y \ lt 2n [/ matemática]
3. los nodos en los índices [matemáticas] [0, x-1] [/ matemáticas] son ​​todos nodos internos porque el nodo en el índice [matemáticas] x-1 [/ matemáticas] tiene al menos 1 hijo **
4. los nodos en los índices [matemática] [x, n-1] [/ matemática] son ​​todos nodos hoja porque el nodo en el índice [matemática] x [/ matemática] no tiene hijos **
5. el nodo en el índice [matemáticas] x-1 [/ matemáticas] es el nodo más a la derecha en el nivel $ h $, donde el nivel [matemáticas] h [/ matemáticas] contiene nodos en los índices [matemáticas] [2 ^ h-1, 2 ^ {h + 1} -2] [/ matemáticas] **
6. declaraciones (ae) prueba declaración (2)
3. Cada valor de nodos es menor que el valor de cada uno de sus hijos
1. para un nodo en el índice [math] i [/ math], sus hijos (si existen) están en los índices [math] 2i + 1 [/ math] y [math] 2i + 2 [/ math]
2. el valor en cualquier índice [matemática] i [/ matemática] es menor que el valor en el índice [matemática] i + 1 [/ matemática] (inferido por la definición de una matriz ordenada por valor creciente)
3. por (a) y (b), la declaración (3) es verdadera
4. Por la prueba de enunciado (1–3), el enunciado original es verdadero

EDITAR:

1. definición actualizada de min-montón para incluir la integridad.
2. prueba actualizada para compensar la integridad del árbol binario.

**: los detalles para la validez de esta declaración se omiten por simplicidad