Meses: febrero 2011

En este artículo continúo la serie dedicada a los tipos de datos abstractos (TAD) en Haskell presentando el TAD de las colas de prioridad.

Una cola de prioridad (en inglés, priority queue) es una cola en la que cada elemento tiene asociada una prioridad y la operación de extracción siempre elige el elemento de menor prioridad. Un ejemplo de cola de prioridad es el formado por una lista de ciudades ordenadas por su distancia a un destino final.

El contenido del resto del artículo es el siguiente:

• la signatura del TAD de las colas de prioridad;
• las propiedades del TAD de las colas de prioridad;
• la implementación, en Haskell, de las colas de prioridad mediante listas y
• la comprobación con QuickCheck de sus propiedades.

Posteriormente, cuando se estudien los montículos, se presentará otra implementación de las colas de prioridad mediante montículos.
Read More “El tipo abstracto de datos de las colas de prioridad en Haskell”