_Page_001.jpg)
La estructura heap es frecuentemente usada para implementar colas de prioridad. En este tipo de colas, el elemento a ser eliminado (borrados) es aquél que tiene mayor (o menor) prioridad. En cualquier momento, un elemento con una prioridad arbitraria puede ser insertado en la cola. Una estructura de datos que soporta estas dos operaciones es la cola de prioridad máxima (mínima).
Existen tres categorías de un heap: max heap, min heap y min-max heap.
Un max (min) tree es un árbol en el cual el valor de la llave de cada nodo no es menor (mayor) que la de los valores de las llaves de sus hijos (si tiene alguno). Un max heap es un árbol binario completo que es también un max tree. Por otra parte, un min heap es un árbol binario completo que es también un min tree.
De la definición se sabe que la llave del root de un min tree es la menor llave del árbol, mientras que la del root de un max tree es la mayor.
Si la llave (key) de cada nodo es mayor que o igual a las llaves de sus hijos, entonces la estructura heap es llamada max heap.
Si la llave (key) de cada nodo es menor que o igual a las llaves d esus hijos, entonces la estructura heap es llamada min heap.
En una estructura min-max heap, un nivel satisface la propiedad min heap, y el siguiente nivel inferior satisface la propiedad max heap, alternadamente. Un min-max heap es útil para colas de prioridad de doble fin.
Las operaciones básicas de un heap son:
Existen tres categorías de un heap: max heap, min heap y min-max heap.
Un max (min) tree es un árbol en el cual el valor de la llave de cada nodo no es menor (mayor) que la de los valores de las llaves de sus hijos (si tiene alguno). Un max heap es un árbol binario completo que es también un max tree. Por otra parte, un min heap es un árbol binario completo que es también un min tree.
De la definición se sabe que la llave del root de un min tree es la menor llave del árbol, mientras que la del root de un max tree es la mayor.
Si la llave (key) de cada nodo es mayor que o igual a las llaves de sus hijos, entonces la estructura heap es llamada max heap.
Si la llave (key) de cada nodo es menor que o igual a las llaves d esus hijos, entonces la estructura heap es llamada min heap.
En una estructura min-max heap, un nivel satisface la propiedad min heap, y el siguiente nivel inferior satisface la propiedad max heap, alternadamente. Un min-max heap es útil para colas de prioridad de doble fin.
Las operaciones básicas de un heap son:
- Creación de un heap vacío
- Inserción de un nuevo elemento en la estructura heap.
- Eliminación del elemento más grande del heap.
Su único requisito es que sólo es posible acceder a ellos a través de un puntero.
Ventajas:
- Soporta las operaciones insertar y suprimir en tiempo O(log N) en el caso peor.
- Soporta insertar en tiempo constante en promedio y primero en tiempo constante en el peor caso.
Un heap tiene las siguientes tres propiedades:
- Es completo, esto es, las hojas de un árbol están en a lo máximo dos niveles adyacentes, y las hojas en el último nivel están en la posición leftmost.
- Cada nivel en un heap es llenado en orden de izquierda a derecha.
- Está parcialmente ordenado, esto es, un valor asignado, llamado key del elemento almacenado en cada nodo (llamado parent), es menor que (mayor que) o igual a las llaves almacenadas en los hijos de los nodos izquierdo y derecho.
