he estudiado min-max-montones y montones, y tengo un par de preguntas:¿Es una matriz ordenada un min-heap? ¿Cuál es el valor mínimo de un montón máximo?
Una matriz ordenada de menor a mayor es un min-heap cuando se utiliza la implementación de montón basada en matrices. La propiedad de montón que el nodo padre es mayor que sus nodos secundarios (2i + 1 y 2i + 2, usando matrices basadas en cero) se cumple para todos los nodos que tienen hijos.
El valor mínimo de un montón máximo está en uno de los nodos de hoja, pero no sabe cuál. Como el nodo mínimo no puede, por definición, tener ningún nodo hijo, debe ser una hoja. La propiedad de montón, sin embargo, no especifica cómo se comparan los nodos hoja, solo con su padre.
es un arreglo ordenado de A-min montón?
Sí, si utiliza la típica convención de montón almacenada en matriz.
¿Dónde está el valor mínimo de un montón máximo?
En una de las hojas. Cuál exactamente no está definido.
Puede implementar el montón binario como una matriz para el índice que comparo con 2 * i + 1 y 2 * i + 2 (comienzo desde 0). en min amontonarán a [i] < un [2 * i + 1] y una [i] < un [2 * i + 2]
así
1. Una matriz ordenada es un montón mínimo.
2. No tiene un índice específico. Todo lo que sabemos que es sólo una hoja
le sugiero que lea este http://en.wikipedia.org/wiki/Binary_heap
donde es el valor mínimo de un máximo de almacenamiento dinámico?
Respuestas: Max Heap se puede representar utilizando una matriz simple con inicio de índice de 1 a n. El primer elemento es la raíz del montón máximo. Propiedad de montón: el nodo en el índice i ha dejado el hijo en 2i y el hijo derecho en 2i + 1 (si 2i y 2i + 1 son menores que el tamaño del montón, es decir, la longitud de la matriz).
Nodos de hojas del máximo montón se encuentran desde el índice i + 1 a n. Aquí i = n/2; n es la longitud de la matriz. Y uno de los nodos hoja tiene el valor mínimo.
De modo que podemos encontrar el valor mínimo de la pila máxima desde los valores de a [i + 1] a a [n]. La complejidad del tiempo para encontrar el valor mínimo es el orden de (n-i).
- una matriz ordenada es una min montón?
Si se ordena ascendente - sí, en general se trata de un montón min, más precisamente - una implementación matriz de un montón binario con las siguientes reglas:
Al mismo tiempo, no funciona a la inversa - una pila binaria basada en matrices no almacenará una lista ordenada
- , donde es el valor mínimo de un máximo de almacenamiento dinámico?
no está definido, y no es la pregunta que desea responder rápidamente cuando se almacenan las claves en un montón min. Si desea poder ver minimo y máximo de la pila en O (1) vez, puede usar clases como MinMaxPriorityQueue en Java.
¿La matriz ordenada es un montón mínimo?
matriz ordenada es o bien min-montón o max-montón pero viceversa no es cierto
min-montón o max-montón no están necesariamente matrices ordenadas.
¿Cuál es el valor mínimo de un montón máximo?
max-heap (o cola de prioridad) por definición proporciona el valor máximo de una colección en el tiempo O (1). si se requiere que alguien recupere el valor mínimo de un montón máximo, entonces usar el propio montón en primer lugar para este problema no es correcto. es como esperar que una pila proporcione acceso FIFO o esperando que la cola proporcione acceso LIFO.
Pero jfyi, el valor mínimo estará en una de las hojas del árbol formado por el montón. podría estar en cualquier subárbol. por lo que necesita otro algoritmo que demorará más de O (1) tiempo para localizarlo.
Como nota al pie:
Un montón con n elementos puede tener [1 a (n + 1)/2] hojas.
Si la altura del árbol formado por el montón es H entonces montón tendrá hasta 2^(h-1) deja
Arrays o bien se pueden ordenar en orden ascendente o en orden descendente. La afirmación "Una matriz ordenada es min-heap" es parcialmente correcta. La versión correcta de esta afirmación es "Una matriz ordenada en orden ascendente se puede tratar como minimago" y su declaración complementaria es "Una matriz ordenada en orden descendente se puede tratar como máximo dinámico".
"Un arreglo ordenado en orden ascendente se puede ser tratada como montón min-"
Pero recuerde que "no todos min-montones pueden tomar la forma de matriz ordenada en orden ascendente".
Y sobre el valor mínimo de máximo montón solo sabemos que esto está presente en las hojas y podemos buscar eso en O (n)