Cola de prioridad

Los heap's son una estructura de datos [Sed92] que se usa para soportar operaciones con colas de prioridad guardando los registros en un arreglo de tal manera que cada llave esta garantizada por ser mayor que las llaves que están en otras dos posiciones específicas. Este ordenamiento es muy fácil ver si dibujamos el arreglo en un árbol de dos dimensiones con líneas abajo de cada llave a las dos llaves correspondientes. Obsérvese la figura . La representación del heap o cola de prioridad como arreglo puede verse en la siguiente tabla .

Figura: Representación completa de la cola de prioridad como árbol

Tabla B.1: Representación de una cola de prioridad como un arreglo

k	1	2	3	4	5	6	7	8	9	10	11	12
a[k]	X	T	O	G	S	M	N	A	E	R	A	I

Esta representación es útil porque es muy fácil tomar el nodo padre y sus hijos. Los padres de un nodo en una posición están en posición y al contrario. Los dos hijos del nodo en la posición están en la posición y . Una cola de prioridad es un árbol binario completo, representado como un arreglo, en el cual cada nodo satisface la condición de la cola de prioridad. En particular, la llave más grande esta siempre en la primera posición del arreglo. La ventaja de utilizar esta estructura de datos, es que todas las operaciones con esta cola de prioridad pueden ser terminadas en tiempo logarítmico.