Kolejka priorytetowa to ADT zawierający elementy z kluczami (priorytetami), która pozwala na przeprowadzenie co najmniej czterech pierwszych operacji:
Kolejka priorytetowa jest uogólnieniem stosu i kolejki, ponieważ używając odpowiednich przypisań priorytetów, struktury te jesteśmy w stanie zrealizować za pomocą kolejek priorytetowych. Zastosowania kolejek priorytetowych: planowanie zadań w systemach komputerowych, sortowanie rekordów, kompresja plików, itp.
Z definicji kolejki priorytetowej wynika, że dane (klucze) musimy umieć porównywać ze sobą. Ponadto chcemy mieć dane tak ułożone, aby szybko można było pobrać element o najwyższym priorytecie. Możemy sobie wyobrazić co najmniej trzy podejścia do implementacji kolejki priorytetowej.
Na nasze potrzeby zakładamy, że interfejs kolejki priorytetowej będzie miał cztery funkcje: __init__(), is_empty(), insert(), remove(). Warto zauważyć, że jeżeli chcemy tylko sprawdzić największy element w kolejce, to możemy kolejno zastosować metody remove() i insert(). Sprawdzimy różne sposoby implementacji kolejki priorytetowej. Dla prostoty będziemy elementy porównywać bezpośrednio, choć można zmodyfikować kod tak, aby funkcja porównująca była parametrem określanym w chwili tworzenia kolejki.
#from Queue import PriorityQueue # Py2 from queue import PriorityQueue # Py3 pq = PriorityQueue() # pq.put((priority, item)) # _, item = pq.get() # lowest first # pq.empty() # czy pusta
import heapq H = [] # zwykła lista Pythona # heapq.heappush(H, item) # item = heapq.heappop(H) # lowest first # len(H) == 0 # czy pusta
Badamy implementację kolejki z priorytetami za pomoca list Pythona. Element o największym priorytecie wyszukujemy w chwili, gdy chcemy go usunąć z kolejki. Łatwo można zmieniać priorytety elementów w kolejce.
class PriorityQueue:
def __init__(self):
self.items = []
def __str__(self): # podglądamy kolejkę
return str(self.items)
def is_empty(self):
return not self.items
def insert(self, item):
self.items.append(item)
def remove(self):
maxi = 0
for i in range(1, len(self.items)):
if self.items[i] > self.items[maxi]:
maxi = i
return self.items.pop(maxi) # mało wydajne
Po zapisaniu tego kodu do osobnego modułu pqueue.py możemy w dowolnym programie korzystać z kolejek priorytetowych.
import pqueue
pq = pqueue.PriorityQueue()
for item in [5, 3, 8]:
pq.insert(item)
# Usuwanie elmentów z kolejki w kolejności: 8, 5, 3.
while not pq.is_empty():
print(pq.remove())
Implementacja kolejki z priorytetami za pomocą listy jednokierunkowej. Lista jest stale uporządkowana, a największy element znajduje się na początku listy.
class Node:
def __init__(self, data=None, next=None):
self.data = data
self.next = next
def __str__(self):
return str(self.data)
class PriorityQueue:
def __init__(self):
self.head = None
def is_empty(self):
return not self.head
def insert(self, data):
node = Node(data)
# Największy element chcemy mieć na początku listy.
# Robimy widełki do wstawienia nowego elementu.
before = None
after = self.head # może być None
while after:
if after.data < node.data: break
before = after
after = after.next
if before is None: # przed początkiem listy
node.next = self.head
self.head = node
else: # jesteśmy w głębi listy, może na końcu
node.next = before.next
before.next = node
def remove(self): # constant-time, bo usuwamy początek
data = self.head.data
self.head = self.head.next
return data
Implementacja kolejki z priorytetami za pomocą listy jednokierunkowej. Nowe elementy dodajemy na początek listy, a szukamy elementu największego przy usuwaniu go z kolejki.
class Node:
def __init__(self, data=None, next=None):
self.data = data
self.next = next
def __str__(self):
return str(self.data) # bardzo ogólnie
class PriorityQueue:
def __init__(self):
self.head = None
def is_empty(self):
return not self.head
def insert(self, data): # constant-time, O(1)
self.head = Node(data, next=self.head)
def remove(self): # nie ma zabezpieczenia
# Etap 1 - wyszukanie węzła. Wydajność O(n).
before = None
best = self.head
node = self.head # następnego za tym będziemy sprawdzać
while node.next:
if node.next.data > best.data:
before = node
best = node.next
node = node.next
# Etap 2 - odłączanie węzła.
if before is None: # best to head
self.head = self.head.next
else: # poprawiamy linki
before.next = best.next
return best.data
Implementacja kolejki z priorytetami za pomocą tablicy. Tablica nie jest uporządkowana. Znajdujemy indeks największego elementu, zamieniamy go z ostatnim i skracamy tablicę jak dla stosu.
class PriorityQueue:
def __init__(self, size=10):
self.items = size * [None]
self.n = 0 # pierwszy wolny indeks
self.size = size
def is_empty(self):
return self.n == 0
def is_full(self):
return self.size == self.n
def insert(self, data):
# brak zabezpieczenia
self.items[self.n] = data
self.n += 1
def remove(self):
# brak zabezpieczenia
# Etap 1 - wyszukiwanie elementu.
maxi = 0
for i in range(self.n):
if self.items[i] > self.items[maxi]:
maxi = i
# Etap 2 - usuwanie elementu.
self.n -= 1
data = self.items[maxi]
self.items[maxi] = self.items[self.n]
self.items[self.n] = None # usuwamy referencję
return data
Implementacja kolejki z priorytetami za pomocą sterty. Metody klasy Heap będą dziedziczone przez klasę PriorityQueue.
import heap class PriorityQueue(heap.Heap): pass