Monticulo Binario
Páginas: 3 (746 palabras)
Publicado: 3 de diciembre de 2015
Montículo
(Heap)
Definición
Es una estructura de datos del tipo árbol con
perteneciente a un conjunto ordenado.
información
Montículo máximo: Tienen la característica se que cada nodo
padre tieneun valor mayor que el de cualquiera de sus nodos
hijos.
Montículo mínimo: El valor del nodo padre es siempre menor
al de sus hijos.
5
19
10
12
7
9
Un árbol cumple la condición de montículo sisatisface dicha
condición y además es un árbol binario completo.
MONTÍCULO DE PRIORIDAD
En un montículo de prioridad, el mayor elemento (o el menor,
dependiendo de la relación de orden escogida),esta siempre en
el nodo de la raíz. Por esta razón, los montículos son útiles para
implementar colas de prioridad.
La eficiencia de las operaciones en los montículos es crucial en
diversos algoritmos derecorrido.
Montículos binarios
•
Completo, con la posible excepción del nivel inferior.
•
El nivel inferior se llama de izquierda a derecha.
•
Permite su implementación sobre un vector.Ventajas
•
Constantes menores
•
La raíz en la primera posición del vector (posición 0)
•
Dado un nodo situado en la posición i:
o
Su hijo izquierdo esta en la posición 2i+1
o
Su hijo derecho allado, en la posición 2i+2
o
Su padre en la posición (i-1)/2
PROPIEDAD DE ORDENACIÓN
Tipos de montículos:
MONTÍCULO DE MÍNIMOS
•
Todo nodo tiene una clave menor o igual que la de sus hijos.
•
Elmenor elemento se encuentra en la raíz.
MONTÍCULO DE MÁXIMOS
•
Todo nodo tiene una clave mayor o igual que la de sus hijos.
•
El mayor elemento esta en la raíz.
OPERACIONES DEL MONTICULO
INSERTAR•
Situar al elemento a insertar en la ultima posición disponible
del vector
•
Comparar el elemento insertado con su padre
Padre en i-1/2 siendo i la posición del nodo insertado
Si la llave es menor:•
Se intercambia con su padre
•
Se repite el proceso hasta que el padre sea menor o haya
alcanzado la raíz
•
Este proceso se denomina criba o filtrado ascendente
Caso mejor: el elemento es...
(Heap)
Definición
Es una estructura de datos del tipo árbol con
perteneciente a un conjunto ordenado.
información
Montículo máximo: Tienen la característica se que cada nodo
padre tieneun valor mayor que el de cualquiera de sus nodos
hijos.
Montículo mínimo: El valor del nodo padre es siempre menor
al de sus hijos.
5
19
10
12
7
9
Un árbol cumple la condición de montículo sisatisface dicha
condición y además es un árbol binario completo.
MONTÍCULO DE PRIORIDAD
En un montículo de prioridad, el mayor elemento (o el menor,
dependiendo de la relación de orden escogida),esta siempre en
el nodo de la raíz. Por esta razón, los montículos son útiles para
implementar colas de prioridad.
La eficiencia de las operaciones en los montículos es crucial en
diversos algoritmos derecorrido.
Montículos binarios
•
Completo, con la posible excepción del nivel inferior.
•
El nivel inferior se llama de izquierda a derecha.
•
Permite su implementación sobre un vector.Ventajas
•
Constantes menores
•
La raíz en la primera posición del vector (posición 0)
•
Dado un nodo situado en la posición i:
o
Su hijo izquierdo esta en la posición 2i+1
o
Su hijo derecho allado, en la posición 2i+2
o
Su padre en la posición (i-1)/2
PROPIEDAD DE ORDENACIÓN
Tipos de montículos:
MONTÍCULO DE MÍNIMOS
•
Todo nodo tiene una clave menor o igual que la de sus hijos.
•
Elmenor elemento se encuentra en la raíz.
MONTÍCULO DE MÁXIMOS
•
Todo nodo tiene una clave mayor o igual que la de sus hijos.
•
El mayor elemento esta en la raíz.
OPERACIONES DEL MONTICULO
INSERTAR•
Situar al elemento a insertar en la ultima posición disponible
del vector
•
Comparar el elemento insertado con su padre
Padre en i-1/2 siendo i la posición del nodo insertado
Si la llave es menor:•
Se intercambia con su padre
•
Se repite el proceso hasta que el padre sea menor o haya
alcanzado la raíz
•
Este proceso se denomina criba o filtrado ascendente
Caso mejor: el elemento es...
Leer documento completo
Regístrate para leer el documento completo.