Modulo 5. Colas con prioridad PDF

Preview

Summary

Download Modulo 5. Colas con prioridad PDF

Description

Colas con prioridad Elena García Barriocanal Miguel Ángel Sicilia Urbán P06/75001/00579 Módulo 5

© FUOC • P06/75001/00579 • Módulo 5

Colas con prioridad

Índice

Introducción ............................................................................................

5

Objetivos ...................................................................................................

6

1. El concepto de cola con prioridad .................................................

7

2. Funcionamiento de las colas con prioridad ...............................

8

3. Implementación de las colas con prioridad ............................... 10 3.1. Implementación lineal ................................................................... 10 3.2. Implementación mediante pilón ................................................... 10 3.2.1. ¿Qué es un pilón? ................................................................ 11 3.2.2. Inserción de un elemento ................................................... 13 3.2.3. Supresión de un elemento .................................................. 14 4. Las colas prioritarias en las bibliotecas JDK .............................. 16 5. Ordenación por pilón: el algoritmo heapsort ............................ 17 6. Ejemplo de uso: algoritmo de Huffman ...................................... 25 Resumen .................................................................................................... 28 Ejercicios de autoevaluación ............................................................... 29 Solucionario ............................................................................................. 31 Glosario ..................................................................................................... 33 Bibliografía .............................................................................................. 33 Anexo ......................................................................................................... 35

© FUOC • P06/75001/00579 • Módulo 5

5

Colas con prioridad

Introducción

Una vez introducidos los tipos de datos correspondientes a las secuencias y a los árboles y, por lo tanto, una vez conocidos los datos de tipo cola, se puede pensar en una generalización, que es reflejo de muchas situaciones del mundo real. Las colas estudiadas en el módulo “Contenedores secuenciales” responden a una estructura FIFO, es decir, el primer elemento en salir es el primero que ha entrado.

FIFO es la sigla de first in, first out.

Ahora bien, esto no permite modelizar determinadas situaciones. Por ejemplo, si se pretende diseñar una estructura de datos para un planificador de tareas de un sistema operativo, es posible que las tareas no se tengan que asignar obligatoriamente a la CPU según el orden de llegada, sino respondiendo a un grado de prioridad que depende de cómo sean de críticas o importantes. En este módulo se describe un tipo abstracto de datos que permite modelizar estas situaciones y que se conoce con el nombre de cola con prioridad. Las colas con prioridad se pueden implementar de diferentes maneras, pero hay una que hace especialmente eficientes las operaciones de inserción y supresión de elementos en la cola. Para llevar a cabo esta implementación se utilizará un pilón para almacenar lo que se denomina árbol casicompleto y parcialmente ordenado. Esta implementación se estudiará con detalle en este módulo. El módulo también incluye una breve descripción de las principales clases Java para la utilización de colas con prioridad, y de la eficiencia que tienen las operaciones de las colas. También es importante destacar una de las principales utilidades de las colas con prioridad: el algoritmo de ordenación por pilón o heapsort. El algoritmo heapsort utiliza una cola con prioridad como estructura intermedia para conseguir una buena eficiencia a la hora de ordenar un vector: O(n log n), siendo n la medida del vector. Esto mejora los algoritmos de ordenación más conocidos. En este módulo, se estudiará una implementación de algoritmo que hace un especial buen uso de una cola de prioridad para optimizar al máximo la eficiencia espacial.

CPU es la sigla de central process unit.

© FUOC • P06/75001/00579 • Módulo 5

6

Objetivos

En los materiales didácticos del módulo encontramos los elementos indispensables para alcanzar los siguientes objetivos: 1. Comprender el concepto de cola con prioridad. 2. Saber utilizar el tipo abstracto de datos cola con prioridad. 3. Comprender y saber utilizar las diferentes implementaciones de las colas con prioridad. 4. Saber elegir la mejor implementación de una cola con prioridad según la situación. 5. Conocer las clases de Java para la utilización de colas con prioridad. 6. Comprender el concepto de árbol cuasicompleto y parcialmente ordenado y sus operaciones. 7. Comprender y saber aplicar el método de ordenación por pilón o algoritmo heapsort.

Colas con prioridad

© FUOC • P06/75001/00579 • Módulo 5

7

Colas con prioridad

1. El concepto de cola con prioridad

Las colas como tipo abstracto de datos tienen como característica esencial el uso del orden de inserción de los elementos para determinar su orden de ex-

El funcionamento del tipo de datos Cola se puede encontrar en el módulo “Contenedores secuenciales” de esta asignatura.

tracción. Así, el primer elemento que entra será el primer elemento que sale. Dicho de otro modo, el criterio de salida es el orden de inserción. Éste es un orden que aceptamos con naturalidad en muchas situaciones de nuestra vida –en las colas de los teatros, de los medios de transporte...– en las que decimos que todos los elementos (los individuos) de la cola tienen la misma prioridad; es decir, no hay privilegios dependientes del individuo respecto a la salida de la cola (de hecho, un intento de transgredir este orden suele desencadenar conflictos). No obstante, también en muchas otras situaciones asumimos que ciertos individuos tienen una “prioridad mayor”. Por ejemplo, en las colas, se suele dejar pasar a las embarazadas y se suele permitir que los pasajeros de primera clase de los aviones embarquen los primeros. Incluso, a veces, al ver a dos individuos somos capaces de discernir enseguida cuál de los dos se debería poner “delante” en la cola. Por ejemplo, en los servicios de urgencia, los médicos saben determinar el orden de prioridad de los pacientes según la gravedad aparente de la enfermedad o de la herida, al menos de manera aproximada. Esto quiere decir que el criterio de prioridad se puede considerar una relación de orden. De los ejemplos anteriores, se deduce que las colas con prioridad son un tipo abstracto de datos, cuya característica fundamental es que el orden de salida de los elementos de la lista no es el mismo que el orden de entrada, sino que están sujetos a una relación diferente. Si bien habitualmente se considera que una cola con prioridad es un tipo de cola (y, por lo tanto, una especialización), es importante destacar que el concepto de cola con prioridad se puede considerar también una generalización conceptual de cola (sin prioridad). Esto es así porque el orden de llegada a la cola se puede ver como un criterio de prioridad concreto de entre los muchos posibles. De hecho, se suele adoptar como el criterio de prioridad “por defecto” en muchas de las situaciones de la vida cotidiana.

Colas con prioridad y colas sin prioridad Si tenemos una implementación de una cola con prioridad en la que se asigna como prioridad el momento de inserción del elemento, y si tenemos como criterio de prioridad que la hora de llegada es la más prioritaria, la cola con prioridad actuará igual que una cola sin prioridad. Pensad, además, que si usamos de la misma manera el momento de inserción pero invirtiendo el criterio (es decir, el momento más prioritario es el más reciente) tendremos el comportamiento de una pila.

© FUOC • P06/75001/00579 • Módulo 5

8

Colas con prioridad

2. Funcionamiento de las colas con prioridad

Una cola con prioridad es una especialización de una secuencia en la que el orden de salida de los elementos se determina previamente de acuerdo con unos criterios establecidos por el programador. Por lo tanto, los elementos que contenga la cola han de mantener una relación de orden.

Para describir el funcionamento del TAD cola con prioridad se supondrá que los elementos que contiene cualquier cola (de tipo elem) mantienen una relación de orden total. Es decir, que dados dos elementos cualesquiera a y b se puede establecer que a es menor que b, o que b es menor que a o que los dos son iguales. Además, se considerará que si a es menor que b, entonces a tiene más prioridad que b y, por lo tanto, saldrá “antes” que b una vez almacenado en la cola. La interfaz del TAD cola con prioridad (que denotaremos ColaConPrioridad) está formada por las operaciones de creación de la cola, inserción de un elemento en la cola, eliminación del primer elemento en la cola y consulta del valor del primer elemento de la cola. Estas operaciones tienen la especificación que a continuación describimos. Hay que destacar que el TAD cola con prioridad está implementado en la biblioteca de TAD de la asignatura como una clase que implementa la interfaz Cola y, por lo tanto, conserva la misma interfaz pero redefine sus métodos de acuerdo con un comportamiento más complejo en el que se respeta la prioridad de los elementos.

a

Colección ColaConPrioridad implementa Cola ColaConPrioridad; Crea una cola con prioridad. @pre Cierto. @post Cola vacía. void encolar(E: Elem); Añade un elemento a la cola con prioridad. @pre Cierto. @post Cola con prioridad con el nuevo elemento añadido al lugar que le corresponde según su prioridad. Elem desencolar(); Devuelve el elemento más prioritario de la cola y lo elimina de ésta. @pre La cola con prioridad sobre la que se realiza la operación no ha de estar vacía. @post El elemento más prioritario de la cola y la cola con prioridad sin el elemento que tenía más prioridad antes de ejecutar la operación.

En la biblioteca de TAD propia de la asignatura, se incluyen otros constructores en los que se puede pasar como parámetro la medida máxima de la cola, el comparador que permite deducir el orden por prioridad o los dos.

© FUOC • P06/75001/00579 • Módulo 5

9

Colas con prioridad

Elem primero(); Devuelve el elemento más prioritario de la cola. @pre La cola con prioridad sobre la que se realiza la consulta no ha de estar vacía. @post Devuelve el elemento con más prioridad de los almacenados, sin eliminarlo de la cola. int numElems(); Devuelve el número de elementos en la cola. @pre Ninguno (‘cierto’) @post Devuelve el número de elementos que hay en la cola con prioridad. boolean estaLleno(); Devuelve si la cola está llena o no (‘cierto’ si está llena). @pre Ninguno(‘cierto’) @post Devuelve ‘cierto’ si la cola con prioridad está llena. boolean estaVacio(); Devuelve si la cola está vacía o no (‘cierto’ si está vacía). @pre Ninguno(‘cierto’) @post Devuelve ‘cierto’ si la cola con prioridad está vacía. A continuación se muestra un ejemplo fácil para comprender mejor la especificación del TAD ColaConPrioridad, suponiendo que se implementa con una clase Java: uoc.ei.ejemplos.modulo5.UsoColaPrioridad ... ColaConPrioridad cP = new ColaConPrioridad(); Integer i; cP.encolar(new Integer(5)); cP. encolar (3); // A causa del autoboxing de Java5 // cP.encolar(N) cP. encolar (4); // tiene el mismo efecto // cP.encolar new (Integer(N)) cP. encolar (1); cP. encolar (2); // El contenido de la cola es: 1, 2, 3, 4, 5 if (!cP.estaVacio()) { i = cP.desencolar (); System.out.println(e); // Muestra 1 } // El contenido de la cola es: 2, 3, 4, 5 i = cP.primero(); System.out.println(e); // Muestra 2 while (!cP.estaVacio()) System.out.print(cP.desencolar ()+", ");// Muestra 2, 3, 4, 5 ...

© FUOC • P06/75001/00579 • Módulo 5

10

Colas con prioridad

3. Implementación de las colas con prioridad

3.1. Implementación lineal La implementación inmediata que sugieren las operaciones de la interfaz del TAD ColaConPrioridad se basaría en una estructura de datos lineal, ya que, de hecho, hay una relación de tipo lineal entre los elementos almacenados en la cola. Esta relación lineal no es otra que la que define la relación de orden del atributo o atributos que determinan la prioridad de los elementos de la cola. La implementación hecha con una estructura lineal se puede llevar a cabo de cualquiera de las maneras que ya conocemos, sea de manera enlazada o no, circular o lineal, o implementada utilizando memoria estática o dinámica. A causa de la necesidad de mantener los elementos en

Véase las implementaciones lineales de las colas del módulo “Contenedores secuenciales” de esta asignatura.

Figura 1

la cola con prioridad según un determinado orden, cualquiera de las implementaciones mencionadas requiere un tiempo de ejecución de orden lineal respecto del número de elementos que contiene la cola en alguna de sus operaciones: • Si utilizamos una lista ordenada, las operaciones de consulta y eliminación son de orden constante, si bien la inserción pasa a ser de orden lineal, ya que habría que recorrer la cola para saber en qué punto

Figura 2

concreto hay que insertar el elemento (figura 1). • Si una lista se mantiene ordenada sólo según el momento de inserción, la operación de inserción queda en tiempo constante. Pero tanto la consulta como la eliminación de un elemento son de orden lineal, ya que en los dos casos hay que hacer una busca lineal (figura 2).

3.2. Implementación en pilón Las situaciones que hemos visto hasta ahora se pueden mejorar si se utiliza una implementación en pilón de la cola de prioridad. El pilón, tal como se explica más adelante, reflejará un árbol parcialmente ordenado cuasicompleto que contendrá los datos de la cola. Con esta implementación, se garantizará que tanto la inserción como la eliminación se ejecutan con coste logarítmico y mantienen la consulta en tiempo constante.

El concepto de árbol parcialmente ordenado se explica en este mismo subapartado. En el subapartado 3.2.1 se detalla la implementación de árboles en pilón.

© FUOC • P06/75001/00579 • Módulo 5

11

Colas con prioridad

Se define como árbol parcialmente ordenado aquel en el que cualquier nodo es menor que sus hijos, con independencia de su aridad.

Por lo tanto, según esta definición, la raíz de

Figura 3

un árbol parcialmente ordenado contiene el elemento más pequeño de todo el árbol. Observad que no se garantiza nada respecto del orden de los nodos hermanos, de aquí el término parcialmente ordenado: en un orden total, dados dos elementos y sus posiciones, siempre se sabe si uno es más pequeño o igual que el otro. En cambio, en un orden parcial, esto no pasa. En la figura 3, se muestran dos árboles. El primero es un árbol binario parcialmente ordenado y, el segundo, un árbol de aridad 3 parcialmente ordenado. Para la implementación de las colas de prioridad en un pilón, en este módulo utilizaremos un árbol binario parcialmente ordenado, y dejaremos como actividad la implementación de la cola utilizando árboles de mayor aridad. Por otro lado, y como la implementación de la cola se hará en pilón, también se pedirá que el árbol sea cuasicompleto, a fin de que el vector en el que se almacenen los datos de la cola de prioridad se aproveche al máximo y se asegure una buena eficiencia espacial. Teniendo en cuenta la representación de la cola mediante este tipo de árboles implementados con un vector, las operaciones de encolar y desencolar elementos devienen inserción y supresión de elementos en el pilón.

3.2.1. Qué es un pilón?

Un pilón es el nombre que recibe la implementación de un árbol que utiliza un vector.

Este tipo de implementación se basa en el almacenamiento de la información del nodo en una posición de un vector a la que se puede tener acceso directo. Para hacer esto, es necesario saber qué posición del vector corresponde a cada nodo en función de la posición que éste ocupe en el árbol. En el pilón, los nodos se organizan según la estrategia siguiente: el nodo raíz se sitúa en la primera posición; el hijo izquierdo de la raíz, en la segunda; el hijo derecho de la raíz, en la tercera; el hijo izquierdo del hijo izquierdo de la raíz, en la cuarta, etc. (figura 4). Aquellos nodos que no existan han de tener su posición garantizada (para el caso de futuras inserciones), pero deben indicar de alguna manera cuándo están libres.

Observad en el ejemplo que un nodo de tercer nivel (25) puede ser más pequeño que otro de segundo que no sea su padre (29).

© FUOC • P06/75001/00579 • Módulo 5

12

Para saber en qué posición del vector hay que situar un

Colas con prioridad

Figura 4

determinado nodo del árbol se utiliza una cadena que identifica la posición de cada nodo. Esta cadena incluye la posición de sus nodos antecesores en el árbol: • La raíz se identifica con la cadena vacía. • La cadena que identifica al hijo izquierdo de un nodo es igual a la cadena que identifica a su nodo padre concatenada por la derecha con el carácter 1. •

La cadena que identifica al hijo derecho de un nodo es igual a la cadena que identifica a su nodo padre concatenada por la derecha con el carácter 2.

En el ejemplo anterior, las cadenas que identifican a cada nodo son: • A → cadena vacía • B → cadena • C → cadena • D → cadena • E → cadena A partir de la cadena S = s1s2…sk, Ψ(S) es la posición en el vector del nodo: k

Ψ( S) = 2 k + ∑ ( si − 1) ⋅ 2 k− i i =1

Figura 5

En la figura 5, se muestra otro ejemplo de cómo se representa un árbol en un pilón. El elemento indicado por la cadena S = 212 se encontrará en la posición 13 del vector: Ψ(212) = 23 + (2 − 1) · 22 + (1 − 1) · 21 + (2 − 1) · 20 = 8 + 4 + 1 = 13 A partir de lo que se ha expuesto, se deducen las posiciones de los hijos y del padre de un nodo del árbol determinado: • Posición del hijo izquierdo (s’) de un nodo s: Ψ (S’) = 2 · Ψ (S) • Posición del hijo derecho (s’’) de un nodo s: Ψ (S’’) = 2 · Ψ (S) + 1 • Posición del padre (s) de un nodo s’: Ψ (S’) = Ψ (S’) div 2 Respecto de la eficiencia temporal, la utilidad de la implementación en pilón surge en árboles en los que se harán operaciones individuales y concretas, que serán O(1) o O(log n). En cuanto a la eficiencia espacial, un árbol con pocos nodos y muchos niveles es muy ineficiente. Por eso, haremos que los pilones sean normalmente árboles completos o cuasicompletos.

© FUOC • P06/75001/00579 • Módulo 5

13

Un árbol es completo si todos sus niveles contienen el máximo número de nodos posible. Un árbol se considera cuasicompleto si todos los niveles menos el último están llenos y, en el último nivel, los nodos se encuentran consecutivamente comenzando por el que hay más a la izquierda, y dejan las posibles hojas vacías a la derecha.

3.2.2. Inserción de un elemento

Para encolar un elemento en la cola de prioridad, se ha de realizar una inserción en el árbol binario parcialmente ordenado y cuasicompleto. El elemento que hay que inserir se introduce en la primera posición libre que se encuentre al hacer un recorrido por niveles. Como el árbol es cuasicompleto, esta posición será siempre una hoja (la siguiente de la última empezando por la izquierda, o la primera de un nuevo nivel). Esta inserción puede dejar el árbol parcialmente desordenado –aunque quede cuasicompleto–, y habría que reestructurarlo. Para ello, se intercambia el elemento inserido con su padre hasta que se sati...