Estructuras de Datos y Algoritmos (EDA)

Un curso sobre Tipos Abstractos de Datos

Una aplicación de las colas con prioridad

sin comentarios

Las colas con prioridad (y por tanto la estructura de datos montículo con la que se representan en memoria) se utilizan a menudo para mejorar la eficiencia de algoritmos en los que iterativamente se precisa conocer el mínimo (o máximo) de un conjunto de valores y eliminarlo del conjunto. Ejemplo:

monticulos_y_dijkstra

Si utilizamos una cola con prioridades (montículo), añadiéndole una operación de reducción de clave, el algoritmo anterior queda de la siguiente forma:

Dijkstra usando cola con prioridades

(Detalles: en la asignatura Algoritmia Básica, de la Especialidad en Computación)

———

Por supuesto, la utilidad del algoritmo anterior se obtiene si n es grande.

n 10 100 1000 10000 100000 1000000
n log n 30 600 10000 130000 1600000 19000000
n2 100 10000 1000000 100000000 10000000000 1000000000000

Written by Javier Campos

noviembre 29th, 2012 at 1:14 pm

Posted in Material