Hola, buen día.
Una pregunta. En el arreglo donde se representa una cola de prioridad, ¿siempre pasa que no quedan huecos entre los elementos?
Hola Juan, Heap es la estructura que vimos que sirve para implementar una cola de prioridad acotada, representa un árbol binario en el que el elemento de cada nodo es menor o igual que los elementos de los subárboles (Propiedad de Orden) y es un árbol completamente lleno, excepto el nivel más bajo que se llena de izquierda a derecha (Propiedad de Estructura).
A su vez, dada la propiedad de estructura del Heap, este árbol binario se puede almacenar en un arreglo con tope, y en ese caso los elementos están todos contiguos (no hay huecos) ya que conforman un árbol completo salvo el último nivel y los niveles se encuentran todos uno a continuación del otro.
Por ejemplo para los elementos {1, 2, 4, 5, 3} tendríamos el siguiente árbol:
1
3 2
4 5 3
y el siguiente arreglo:
| |1|3|2|4|5|3| | | | | | | |
tope=6 (aunque esto puede variar según como se utilice tope)
Tener en cuenta que para poder encontrar de forma fácil lo hijos y el padre de cada nodo usamos los las posiciones 1 al tope del arreglo, no usamos las posición 0. De esta forma los hijos del nodo en la posición i están en la posición 2*i y 2*i+1, si estos son menores que tope; y el padre de i está en la posición i div 2, si es mayor que 0.
saludos, libertad
Genial, muchas gracias. Esto de que el árbol queda lleno salvo su último nivel, ¿también pasa luego de haber eliminado elementos?
Hola.
Si. Las propiedades de estructura y orden se mantienen invariantes al ejecutar operaciones que modifican la estructura.
Saludos, Carlos
Ahh. Muchas gracias
Saludos
Saludos