Cola de prioridad (programación)

La versión actual de la página aún no ha sido revisada por colaboradores experimentados y puede diferir significativamente de la versión revisada el 25 de marzo de 2021; las comprobaciones requieren 2 ediciones .

Una  cola de prioridad es un tipo de datos abstracto en programación que admite dos operaciones obligatorias: agregar un elemento y extraer el máximo [1] (mínimo). Se supone que para cada elemento es posible calcular su prioridad  - un número real o, en el caso general, un elemento de un conjunto ordenado linealmente [2] .

Descripción

Los principales métodos implementados por la cola de prioridad son los siguientes [2] [3] [1] :

En este caso, un valor de clave más pequeño corresponde a una prioridad más alta.

En algunos casos, es más natural que la clave crezca junto con la prioridad. Entonces el segundo método puede llamarse extract_maximum()[1] .

Hay una serie de implementaciones en las que ambas operaciones básicas se realizan en el peor de los casos en un tiempo limitado (ver "O" grande y "o" pequeña ), donde  es el número de pares almacenados.

Ejemplos

Como ejemplo de una cola de prioridad, considere la lista de tareas de un trabajador. Cuando termina una tarea, pasa a la siguiente, la de mayor prioridad (la clave será el recíproco de la prioridad), es decir, realiza la operación de extraer el máximo. El jefe agrega tareas a la lista, indicando su prioridad, es decir, realiza la operación de agregar un elemento.

Extensiones de cola de prioridad

En la práctica, la interfaz de cola de prioridad a menudo se amplía con otras operaciones [4] [3] :

En las colas de prioridad indexadas (direccionadas [5] ), es posible acceder a los elementos por índice. Estas colas se pueden utilizar, por ejemplo, para fusionar varias secuencias ordenadas (fusión multidireccional) [1] .

También se puede considerar la cola de prioridad doble (DEPQ ) ,  en la que hay operaciones de acceso tanto al elemento mínimo como al máximo [6] .

Implementaciones

La cola de prioridad se puede implementar en función de varias estructuras de datos.

Las implementaciones más simples (y no muy eficientes) pueden usar una matriz desordenada u ordenada , una lista enlazada , adecuada para colas pequeñas. En este caso, los cálculos pueden ser tanto “perezosos” (la severidad de los cálculos se transfiere a la extracción del elemento), como tempranos (ansiosos), cuando la inserción del elemento es más difícil que su extracción. Es decir, una de las operaciones se puede realizar en el tiempo y la otra, en el peor de los casos , donde  está la longitud de la cola [1] .

Más eficientes son las implementaciones basadas en heap , donde ambas operaciones se pueden realizar en el peor de los casos en el tiempo [1] . Estos incluyen montón binario , montón binomial, montón de fibonacci, montón de emparejamiento[6] .

El tipo de datos abstractos (ATD) para la cola de prioridad se deriva del montón ADT cambiando el nombre de las funciones correspondientes. El valor mínimo (máximo) siempre está en la parte superior del montón [7] .

Ejemplo de Python

La biblioteca estándar de Python contiene un módulo heapq[8] que implementa una cola de prioridad [9] :

# importar dos funciones de cola con los nombres usados ​​en este artículo de heapq import heappush as insert , heappop as extract_maximum pq = [] # inicializar la lista insert ( pq , ( 4 , 0 , "p" )) # insertar el elemento "p" en la cola " con índice 0 y prioridad 4 insert ( pq , ( 2 , 1 , "e" )) insert ( pq , ( 3 , 2 , "a" )) insert ( pq , ( 1 , 3 , "h" )) # deascendenteordenenelementoscuatrolosimprime _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _

Este ejemplo generará la palabra "montón".

Notas

  1. ↑ 1 2 3 4 5 6 Sedgewick, Wayne, 2011 .
  2. ↑ 1 2 Aho, Hopcroft, Ullman, 2000 .
  3. ↑ 1 2 Kormen et al., 2005 .
  4. ↑ Robert Sedgewick. Algoritmos en C++, partes 1 a 4: fundamentos, estructura de datos, clasificación, búsqueda. - Tercera edicion. — Addison-Wesley Profesional. — 752 pág. - ISBN 978-0-7686-8533-6 .
  5. ↑ Mehlhorn, Sanders, 2008 .
  6. ↑ 1 2 Sahni, Mehta, 2018 .
  7. ↑ Rabhi, Lapalme, 1999 .
  8. ↑ 8.4. heapq: algoritmo de cola del montón . Consultado el 25 de noviembre de 2014. Archivado desde el original el 4 de diciembre de 2017.
  9. ↑ David Beazley, Brian K. Jones. 1.5. Implementación de una cola de prioridad // Libro de recetas de Python. - 3ra edición. - O'Reilly Media, Inc., 2013. - 706 págs. — ISBN 978-1-4493-4037-7 .

Literatura

  • Kormen, T., Leizerson, C., Rivest, R., Stein, K. Algoritmos: construcción y análisis = Introducción a los algoritmos / Ed. I. V. Krasikova. - 2ª ed. - M. : Williams , 2005. - 1296 p. — ISBN 5-8459-0857-4 .
  • Aho A. W., Hopcroft J. E., Ullman J. D. Estructuras de datos y algoritmos. - Williams, 2000. - 384 págs. — ISBN 9785845901224 . , 4.10. Colas de prioridad
  • Roberto Sedgewick; Kevin Wayne. 2.4 Colas de Prioridad // Algoritmos. - Cuarta edición. - Addison-Wesley Professional, 2011. - 992 p. — ISBN 978-0-13-276257-1 .
  • Gerth Stolting Brodal, Chris Okasaki. Colas de prioridad óptimas puramente funcionales  // Serie de informes BRICS. - Departamento de Ciencias de la Computación Universidad de Aarhus, 1996. - No. RS-96-37 . — ISSN 0909-0878 .
  • Fethi Rabhi y Lapalme, G. Algoritmos: un enfoque de programación funcional . - Addison-Wesley, 1999. - P.  92-93 , 106-107. — 235p. — ISBN 9780201596045 .
  • Sartaj Sahni y Dinesh P. Mehta. Parte II: Colas de prioridad // Manual de estructuras de datos y aplicaciones. — 2ª ed. - Chapman y Hall / CRC, 2018. - 1100 p. — ISBN 9781498701853 .
  • Mehlhorn, Kurt, Sanders, Peter. 6. Colas de prioridad // Algoritmos y estructuras de datos: la caja de herramientas básica. - Springer, 2008. - 300 págs. — ISBN 978-3-540-77978-0 .

Enlaces

  • Colas de prioridad para Ruby :
  • Implementación de la cola de prioridad de Haskell verificada por Coq :