Introducció

Les cues de prioritat són una variant de les cues en què cada element té una "prioritat" associada. En lloc de seguir l'ordre FIFO (First In, First Out) com en les cues tradicionals, els elements amb una prioritat més alta es processen abans que els elements amb una prioritat més baixa.

Conceptes Clau

Prioritat: Un valor associat a cada element que determina l'ordre en què es processaran els elements.
Cua de Prioritat Màxima: Els elements amb la prioritat més alta es processen primer.
Cua de Prioritat Mínima: Els elements amb la prioritat més baixa es processen primer.

Operacions Bàsiques

Les operacions bàsiques en una cua de prioritat són similars a les d'una cua tradicional, però amb l'afegit de gestionar les prioritats.

Inserir (enqueue): Afegir un element a la cua amb una prioritat específica.
Eliminar (dequeue): Eliminar i retornar l'element amb la prioritat més alta (o més baixa, depenent del tipus de cua de prioritat).
Consultar (peek): Retornar l'element amb la prioritat més alta (o més baixa) sense eliminar-lo de la cua.

Implementació

Utilitzant un Heap

Una manera eficient d'implementar una cua de prioritat és utilitzar un heap. Els heaps són estructures de dades que permeten inserir elements i extreure l'element amb la prioritat més alta en temps logarítmic.

Heap Màxim

En un heap màxim, el node amb el valor més gran és sempre la arrel del heap.

class MaxHeap:
    def __init__(self):
        self.heap = []

    def insert(self, element):
        self.heap.append(element)
        self._heapify_up(len(self.heap) - 1)

    def extract_max(self):
        if len(self.heap) == 0:
            return None
        if len(self.heap) == 1:
            return self.heap.pop()
        root = self.heap[0]
        self.heap[0] = self.heap.pop()
        self._heapify_down(0)
        return root

    def _heapify_up(self, index):
        parent_index = (index - 1) // 2
        if index > 0 and self.heap[index] > self.heap[parent_index]:
            self.heap[index], self.heap[parent_index] = self.heap[parent_index], self.heap[index]
            self._heapify_up(parent_index)

    def _heapify_down(self, index):
        left_child_index = 2 * index + 1
        right_child_index = 2 * index + 2
        largest = index

        if left_child_index < len(self.heap) and self.heap[left_child_index] > self.heap[largest]:
            largest = left_child_index
        if right_child_index < len(self.heap) and self.heap[right_child_index] > self.heap[largest]:
            largest = right_child_index
        if largest != index:
            self.heap[index], self.heap[largest] = self.heap[largest], self.heap[index]
            self._heapify_down(largest)

Utilitzant una Llista Ordenada

Una altra manera d'implementar una cua de prioritat és utilitzar una llista ordenada. Tot i que aquesta implementació és menys eficient per a grans quantitats de dades, és més senzilla d'entendre i implementar.

class PriorityQueue:
    def __init__(self):
        self.queue = []

    def insert(self, element, priority):
        self.queue.append((priority, element))
        self.queue.sort(reverse=True)  # Ordenar per prioritat descendent

    def extract_max(self):
        if len(self.queue) == 0:
            return None
        return self.queue.pop(0)[1]  # Retornar l'element amb la prioritat més alta

    def peek(self):
        if len(self.queue) == 0:
            return None
        return self.queue[0][1]  # Retornar l'element amb la prioritat més alta sense eliminar-lo

Aplicacions de les Cues de Prioritat

Les cues de prioritat tenen moltes aplicacions en informàtica i altres camps:

Planificació de tasques: Assignar recursos a tasques basant-se en la seva prioritat.
Algoritmes de grafs: Utilitzades en algoritmes com Dijkstra per trobar el camí més curt.
Gestió d'esdeveniments: En simulacions, per processar esdeveniments en l'ordre correcte.

Exercici Pràctic

Exercici 1: Implementació d'una Cua de Prioritat

Implementa una cua de prioritat utilitzant un heap mínim. La cua ha de suportar les operacions d'inserir, extreure el mínim i consultar el mínim.

class MinHeap:
    def __init__(self):
        self.heap = []

    def insert(self, element):
        self.heap.append(element)
        self._heapify_up(len(self.heap) - 1)

    def extract_min(self):
        if len(self.heap) == 0:
            return None
        if len(self.heap) == 1:
            return self.heap.pop()
        root = self.heap[0]
        self.heap[0] = self.heap.pop()
        self._heapify_down(0)
        return root

    def peek(self):
        if len(self.heap) == 0:
            return None
        return self.heap[0]

    def _heapify_up(self, index):
        parent_index = (index - 1) // 2
        if index > 0 and self.heap[index] < self.heap[parent_index]:
            self.heap[index], self.heap[parent_index] = self.heap[parent_index], self.heap[index]
            self._heapify_up(parent_index)

    def _heapify_down(self, index):
        left_child_index = 2 * index + 1
        right_child_index = 2 * index + 2
        smallest = index

        if left_child_index < len(self.heap) and self.heap[left_child_index] < self.heap[smallest]:
            smallest = left_child_index
        if right_child_index < len(self.heap) and self.heap[right_child_index] < self.heap[smallest]:
            smallest = right_child_index
        if smallest != index:
            self.heap[index], self.heap[smallest] = self.heap[smallest], self.heap[index]
            self._heapify_down(smallest)

Solució

La implementació anterior defineix una classe MinHeap que suporta les operacions d'inserir, extreure el mínim i consultar el mínim. Utilitza dos mètodes auxiliars _heapify_up i _heapify_down per mantenir la propietat del heap després de cada operació.

Conclusió

Les cues de prioritat són una eina poderosa per gestionar elements amb prioritats. La seva implementació pot variar des de llistes ordenades fins a heaps, oferint diferents nivells d'eficiència. Comprendre com funcionen i com implementar-les és essencial per resoldre problemes complexos de manera eficient.

Cues de Prioritat

Introducció

Conceptes Clau

Operacions Bàsiques

Implementació

Utilitzant un Heap

Heap Màxim

Utilitzant una Llista Ordenada

Aplicacions de les Cues de Prioritat

Exercici Pràctic

Exercici 1: Implementació d'una Cua de Prioritat

Solució

Conclusió

Curs d'Estructures de Dades

Mòdul 1: Introducció a les Estructures de Dades

Mòdul 2: Llistes

Mòdul 3: Piles

Mòdul 4: Cues

Mòdul 5: Arbres

Mòdul 6: Grafs

Mòdul 7: Conclusions i Recursos Addicionals