Cua de prioritats
Una cua de prioritats és una estructura de dades semblant a una cua, però cada element porta associada una prioritat. En una cua ordinària, l'ordre habitual és primer en entrar, primer en sortir; en una cua de prioritats, en canvi, l'element que es recupera primer és el que té la prioritat més alta segons el criteri definit. Si dos elements tenen la mateixa prioritat, l'ordre pot dependre de la implementació o d'un segon camp de desempat.
Operacions i implementació
[modifica]Les operacions bàsiques són inserir un element amb una prioritat, consultar o eliminar l'element prioritari, comprovar si la cua és buida i obtenir-ne la mida. Es pot implementar amb una llista ordenada, una llista no ordenada o altres estructures, però una opció habitual és el munticle, perquè permet inserir elements i extreure'n el prioritari de manera eficient.[1] En un munticle binari, l'element de més prioritat queda a l'arrel, i l'estructura es reajusta després de cada inserció o extracció.
Ús en programació asíncrona
[modifica]Les cues de prioritats són útils quan no totes les tasques tenen la mateixa urgència. En un servei concurrent, per exemple, es poden processar abans les peticions crítiques, les tasques d'administració o els treballs d'usuaris amb més prioritat, sense deixar de conservar la resta de tasques pendents. Aquest ús és especialment rellevant en arquitectures basades en productors i consumidors, on diversos productors afegeixen feina a una cua i diversos treballadors la processen.
En Python, el mòdul asyncio inclou PriorityQueue, una cua asíncrona que retorna primer les entrades de prioritat més alta segons l'ordre dels valors introduïts.[2] Fowler presenta aquest mecanisme dins de les cues asíncrones i mostra que, internament, les cues de prioritats es basen en munticles; també explica que sovint s'usen tuples o classes ordenables per separar la prioritat de les dades de la tasca.[3]
Limitacions
[modifica]Una cua de prioritats pot provocar inanició si sempre arriben elements d'alta prioritat i els de baixa prioritat no s'arriben a processar. També cal definir bé el criteri d'ordenació, perquè una prioritat mal triada pot fer que el sistema respongui de manera injusta o imprevisible.
Referències
[modifica]- ↑ «heapq — Heap queue algorithm» (en anglès). Python 3 documentation. Python Software Foundation. [Consulta: 28 maig 2026].
- ↑ «asyncio queues» (en anglès). Python 3 documentation. Python Software Foundation. [Consulta: 28 maig 2026].
- ↑ Fowler, Matthew. «12, secció 12.2». A: Python Concurrency with asyncio. Manning Publications, 2022. ISBN 9781617298660.
