Kolejka priorytetowa w Pytonie

---

Kolejka priorytetowa

Kolejka priorytetowa to specjalny rodzaj struktury danych, który umożliwia przechowywanie elementów wraz z ich priorytetami. W odróżnieniu od zwykłej kolejki (FIFO - First In, First Out), w kolejce priorytetowej elementy są usuwane w kolejności wynikającej z ich priorytetów, a nie z kolejności, w jakiej zostały dodane.

Główne cechy kolejki priorytetowej:

Priorytety elementów:

• Każdy element w kolejce ma przypisany priorytet (np. liczba całkowita, gdzie niższa wartość oznacza wyższy priorytet).
• Kolejka priorytetowa usuwa elementy w kolejności priorytetów, a nie w kolejności dodania.

Porządek elementów:

• Elementy z wyższym priorytetem (np. mniejsze liczby) są obsługiwane przed elementami z niższym priorytetem.
• Kolejka może być skonfigurowana jako "max-heap" (gdzie wyższe liczby mają wyższy priorytet) lub "min-heap" (gdzie niższe liczby mają wyższy priorytet).

Typowe operacje:

• Wstawianie elementu: Dodanie elementu do kolejki z określonym priorytetem.
• Usuwanie elementu o najwyższym priorytecie: Usunięcie i zwrócenie elementu z najwyższym priorytetem.
• Podgląd elementu o najwyższym priorytecie: Sprawdzenie, który element ma najwyższy priorytet, bez jego usuwania.

Kolejkę priorytetową możemy zaimplementować na kilka sposobów, w zależności od potrzeb.

1. Użycie modułu queue.PriorityQueue

Moduł queue udostępnia klasę PriorityQueue, która pozwala utworzyć kolejkę priorytetową.

Przykład:

from queue import PriorityQueue

# Tworzenie kolejki
pq = PriorityQueue()

# Dodawanie elementów (priorytet, wartość)
pq.put((1, "Najwyższy priorytet"))
pq.put((3, "Najniższy priorytet"))
pq.put((2, "Średni priorytet"))

# Pobieranie i usuwanie elementów w kolejności priorytetów
while not pq.empty():
    print(pq.get()[1])

Wyjście:

Najwyższy priorytet
Średni priorytet
Niższy priorytet

Metody kolejki priorytetowej

1. put(item)

Dodaje element do kolejki priorytetowej.

Parametry:

• item: Element do dodania. Najczęściej jest to krotka (priorytet, wartość).

Przykład:

from queue import PriorityQueue
pq = PriorityQueue()
pq.put((1, "Pierwszy element"))
pq.put((3, "Trzeci element"))

2. get()

Pobiera i usuwa z kolejki element o najwyższym priorytecie.

Zwraca:

Element o najwyższym priorytecie.

Przykład:

item = pq.get()
print(item)  # Wyświetli element o najwyższym priorytecie.

3. qsize()

Zwraca liczbę elementów aktualnie znajdujących się w kolejce.

Przykład:

size = pq.qsize()
print(f"Liczba elementów w kolejce: {size}")

4. empty()

Sprawdza, czy kolejka jest pusta.

Zwraca:

• True, jeśli kolejka jest pusta.
• False, jeśli kolejka zawiera elementy.

Przykład:

if pq.empty():
    print("Kolejka jest pusta!")

2. Użycie modułu heapq

Moduł heapq implementuje kopiec (heap), który można wykorzystać jako bazę do kolejki priorytetowej. Jest szybszy od PriorityQueue, ale nie ma wbudowanej synchronizacji.

Przykład:

import heapq

# Tworzenie listy jako kopca
pq = []

# Dodawanie elementów (priorytet, wartość)
heapq.heappush(pq, (1, "Najwyższy priorytet"))
heapq.heappush(pq, (3, "Niższy priorytet"))
heapq.heappush(pq, (2, "Średni priorytet"))

# Pobieranie i usuwanie elementów w kolejności priorytetów
while pq:
    print(heapq.heappop(pq)[1])

Wyjście:

Najwyższy priorytet
Średni priorytet
Najniższy priorytet