cola de prioridad de Python

Funciones y métodos de Python




Cola de prioridad de Python: una guía

Una cola de prioridad de Python almacena datos en un orden particular. Hay dos formas de implementar una cola de prioridad en Python: usando la clase de cola y usando el módulo heapq.

Es posible que desee ordenar los datos en función de los valores de cada elemento de la lista. Por ejemplo, es posible que desee que el valor más alto aparezca primero en la lista y que el valor más bajo aparezca al final de la lista.

Ahí es donde entran las colas de prioridad. Una cola de prioridad es una estructura de datos que almacena datos basados ​​en el valor de sus claves en orden ascendente. Esto le permite acceder fácilmente al valor más pequeño y más grande de la cola.

Este tutorial explicará por qué no debe usar una lista para crear colas de prioridad. Le mostraremos dos enfoques más eficientes que puede utilizar para crear una cola de prioridad de Python.




¿Qué es una cola de prioridad de Python?

Las colas de prioridad son una versión modificada de una cola que almacena datos en orden de qué elemento tiene la mayor prioridad. La prioridad de cada elemento en una cola de prioridad se decide según el valor del elemento.

En informática, las colas son estructuras de datos que almacenan elementos en el orden primero en entrar, primero en salir (FIFO) . Hay algunos escenarios en los que el uso de esta estructura puede resultar útil.

Por ejemplo, suponga que está creando una aplicación de seguimiento de pedidos para un restaurante. La persona que hace un pedido primero debe ser atendida antes que las personas que hacen el pedido a continuación. Para realizar un seguimiento de los pedidos, le recomendamos que utilice una cola.

Hay dos formas de definir una cola de prioridad en Python:

El 81% de los participantes declaró que se sentía más seguro acerca de sus perspectivas laborales después de asistir a un campamento de entrenamiento. Asóciese a un bootcamp hoy.

El graduado promedio de un bootcamp pasó menos de seis meses en la transición profesional, desde comenzar un bootcamp hasta encontrar su primer trabajo.

Puede definir una cola de prioridad usando una estructura de lista. Pero esta estrategia es menos eficiente que usar la clase de cola PriorityQueue o el módulo heapq.




Priority Queue Python: queue.PriorityQueue

La queue.PriorityQueue La clase crea una cola de prioridad de Python. Esta clase es parte de la biblioteca de colas de Python. Necesita importar la biblioteca de colas para usar esta clase. Para recuperar un elemento de PriorityQueue, puede usar el método get ().

Para acceder a la clase PriorityQueue, necesitamos importarlo a nuestro código, lo que podemos hacer usando este Declaración de importación de Python :

 from queue import PriorityQueue 

Supongamos que queremos crear una cola de prioridad para los poseedores de entradas en un concierto local. Podríamos hacerlo usando este código:

 from queue import PriorityQueue ticket_holders = PriorityQueue () ticket_holders.put (( 3, 'Paul')) ticket_holders.put ((1,' Miles')) ticket_holders.put ((2, 'Dani')) mientras no ticket_holders.empty (): item = ticket_holders.get () print (item) 

Nuestro código devuelve:

 (1, 'Miles') (2, 'Dani') (3,' Paul') 

En nuestro código, primero importamos la clase PriorityQueue de la biblioteca queue , luego inicializamos una cola de prioridad denominada titulares de entradas . A continuación, insertamos tres tuplas en nuestra cola de prioridad, que almacenan los números de ticket y los nombres asociados con un ticket.

Usamos un bucle while de Python para revisar cada elemento en la cola de prioridad de titulares de entradas . Luego, recuperamos ese elemento usando get () .

El método queue.PriorityQueue es eficiente y fácil de usar, lo que lo convierte en una excelente opción para cuando necesite crear una cola de prioridad.




Módulo heapq de Python de cola de prioridad

El módulo heapq le permite definir una cola de prioridad de Python. Una estructura de datos heapq elimina elementos en orden de prioridad. El valor más bajo tiene la prioridad más baja y el valor más alto tiene la prioridad más alta en la estructura de heapq.


Antes de que podamos usar el módulo heapq, primero debemos importarlo a nuestro código usando la siguiente declaración de importación:

 import heapq 

Volvamos a nuestro ejemplo anterior. Supongamos que queremos crear una cola de prioridad para almacenar información sobre los titulares de entradas en un concierto. Podríamos hacer así que usando el módulo heapq y este programa:

 import heapq ticket_holders = [] heapq.heappush (ticket_holders, ( 3, 'Paul')) heapq.heappush (ticket_holders, (1,' Miles')) heapq.heappush (ticket_holders, (2, 'Dani')) while ticket_holders: item = heapq.heappop (ticket_holders) print (item) 

Nuestro código devuelve:

 (1, 'Miles') (2, 'Dani') (3,' Pa ul') 

Primero, importamos la biblioteca heapq y luego inicializamos una variable de Python llamada ticket_holders . Usamos el método heappush () para enviar tres tuplas a nuestra cola de prioridad. Esta cola almacena los números de boleto para cada titular de boleto y el nombre de cada titular de boleto.

Luego creamos un bucle while que recorre cada elemento en nuestra cola de prioridad. Este bucle elimina el elemento en la parte superior de la cola usando heappop () . Luego, el elemento eliminado se imprime en la consola. Como puede ver, todos los elementos de nuestra cola se imprimen en orden de prioridad.




Por qué no debe mantener una lista

Técnicamente, puede crear una cola de prioridad utilizando la estructura de datos de la lista de Python . Para hacerlo, debe crear una lista y luego ordenarla en orden ascendente.

Sin embargo, esta es una forma relativamente ineficiente de mantener una cola de prioridad. A medida que cambie elementos en la lista, necesitará reordenar la lista, lo que lleva tiempo.

Puede usar una lista tradicional como cola de prioridad si solo necesita almacenar algunos valores. Pero, si está buscando crear una cola más grande, las listas no son una buena opción.


Como referencia, veamos un ejemplo de una cola de prioridad que usa listas. Supongamos que queremos crear una cola de prioridad que almacene el orden de los poseedores de entradas que deben ingresar a un concierto primero. Podríamos use el siguiente código para crear esta cola:

"Career Karma entró en mi vida cuando más lo necesitaba y rápidamente me ayudó a combinar con un bootcamp. ¡Dos meses después de graduarme, encontré el trabajo de mis sueños que se alineaba con mis valores y metas en la vida! "

Venus, ingeniero de software en Rockbot

Nuestro código devuelve:

 (1, 'Miles') (2,' Dani') (3 , 'Paul') 

Hemos creado una lista llamada ticket_holders , luego agregamos tres tuplas a la lista. Cada tupla contenía el número de ticket de un titular de ticket y su nombre. Luego, usamos la función Python sort () para ordenar nuestra lista de titulares de boletos en orden inverso.

Creamos un ciclo while que recorre cada elemento en la lista de ticket_holders y el elemento en la parte superior de la lista. Luego, nuestro código imprime el elemento eliminado en la consola.




Conclusión

Los dos Lo más común para crear una cola de prioridad es usar el módulo heapq o la clase queue.PriorityQueue . Aunque técnicamente puedes usar una lista como cola de prioridad, esto El enfoque no escala bien.

Este tutorial discutió, con referencia a ejemplos, cómo crear una cola de prioridad en Python. ¡Ahora está equipado con el conocimiento que necesita para comenzar a crear sus propias colas prioritarias como un profesional de Python!

Para obtener más orientación sobre cómo aprender Python, consulte nuestro Guía de cómo aprender Python .





cola de prioridad de Python: StackOverflow Questions

Tutorials