Algorytmy i Struktury Danych - Kolejki priorytetowe

Kolejka priorytetowa (ang. priority queue) jest kolejką, w której elementy są ułożone nie w kolejności wprowadzania, lecz w kolejności priorytetu. Każdy element kolejki posiada dodatkowe pole prio, w którym przechowuje swój priorytet – czyli ważność. Gwarantuje to pobieranie z kolejki jako pierwszych elementów o najwyższym priorytecie. Elementy o priorytetach niższych będą pobrane dopiero wtedy, gdy zostaną usunięte wszystkie elementy o priorytetach wyższych.

Sposobów tworzenia kolejek priorytetowych jest wiele. Różnią się one miedzy sobą klasami złożoności dla operacji wstawiania elementu. My podamy najprostsze z nich. Resztę poznasz na studiach informatycznych.

Do realizacji naszej kolejki priorytetowej posłużymy się lekko zmodyfikowaną listą jednokierunkową. Będziemy potrzebowali dwóch wskaźników:

head : wskaźnik pierwszego elementu na liście.
tail : wskaźnik ostatniego elementu na liście.

W naszej implementacji operacje empty, front i pop niczym się nie różnią od takich samych operacji dla zwykłej kolejki. Jedyna różnica pojawia się przy operacji push, która umieszcza w kolejce nowy element. W tym przypadku algorytm przegląda listę od początku do końca, aby znaleźć w niej element o priorytecie bezpośrednio niższym od priorytetu dodawanego elementu. Przed znalezionym elementem zostaje dodany wstawiany na listę element.

Typ elementu listy priorytetowej

Pascal

type
  PSLel = ^SLel;
  SLel = record
    next  : PSLel;
    prio  : integer; // priorytet
    Data: typ_danych;
  end;

C++

struct SLel
{
  SLel * next;
  int prio;  // priorytet
  typ_danych data;
};

Basic

Type SLel
  next As SLel Ptr
  prio As Integer  ' priorytet
  data As typ_danych
End Type

Python (dodatek)

class SLel:


    def __init__(self, p, v):
        self.next = None
        self.prio = p # priorytet
        self.data = v

Kolejka priorytetowa – empty( ) : sprawdza, czy kolejka jest pusta

Wejście:

head : wskaźnik początku kolejki.

Wyjście:

True, jeśli kolejka jest pusta, inaczej false.

Lista kroków:

K01: Jeśli head = nil, 
     to zakończ z wynikiem true
K02: Zakończ z wynikiem false

Kolejka priorytetowa – front( ) : odczyt początku kolejki

Wejście:

head : wskaźnik początku kolejki.

Wyjście:

Wartość elementu na początku kolejki lub wartość specjalna, jeśli kolejka jest pusta.

Lista kroków:

K01: Jeśli head = 0, ; kolejka pusta?
     to zakończ z wynikiem wartość specjalna
K02: Zakończ z wynikiem head→data

Kolejka priorytetowa – push(prio, v) : zapis do kolejki

Wejście:

head : wskaźnik pierwszego elementu listy.
tail : wskaźnik ostatniego elementu listy.
prio : priorytet dopisywanego elementu.
v : dopisywany element.

Wyjście:

Kolejka z dopisanym elementem o wartości v, który zostaje umieszczony na liście zgodnie ze swoim priorytetem.

Elementy pomocnicze:

p, r : wskaźniki elementu listy.

Lista kroków:

K01: Utwórz nowy element listy
K02: p ← adres nowego elementu
K03: p→next ← nil ; inicjujemy pola nowego elementu
K04: p→prio ← prio ; priorytet
K05: p→data ← v
K06: Jeśli head ≠ nil, ; kolejka jest pusta?
     to idź do K10
K07: head ← p ; jeśli tak, to wstawiamy element
K08: tail ← p
K09: Zakończ
K10: Jeśli head→prio ≥ prio, ; sprawdzamy, 
     to idź do K14 ; czy element ma najwyższy priorytet
K11: p→next ← head ; element wstawiamy na początek listy
K12: head ← p
K13: Zakończ
K14: r ← head ; rozpoczynamy od początku listy
K15: Dopóki r→next ≠ nil  r→next→prio ≥ prio,
     wykonuj r ← r→next ; szukamy na liście pierwszego
     ; elementu o niższym priorytecie
K16: p→next ← r→next ; nowy element wstawiamy
     ; przed element r→next
K17: r→next ← p
K18: Jeśli p→next = nil, ; jeśli element jest na końcu, 
     to tail ← p          ; to uaktualniamy tail
K19: Zakończ

Wstawianie elementu do kolejki priorytetowej w tej implementacji posiada czasową złożoność liniową O(n). Zmieniając typ struktury tworzącej kolejkę, można uzyskać złożoność czasową rzędu O(log n). Taką własność posiadają kolejki zbudowane na kopcach (ang. heap).

Kolejka priorytetowa – pop( ) : usuwanie z kolejki

Wejście:

head : wskaźnik pierwszego elementu listy.
tail : wskaźnik ostatniego elementu listy.

Wyjście:

Kolejka pomniejszona o pierwszy element.

Elementy pomocnicze:

p : wskaźnik elementu listy.

Lista kroków:

K01: Jeśli head = nil, ; jeśli lista jest pusta, kończymy
     to zakończ
K02: p ← head ; zapamiętujemy adres pierwszego elementu
K03: head ← head→next ; odłączamy od listy pierwszy element
K04: Jeśli head = nil, ; jeśli lista stała się pusta, 
     to tail ← nil ; to nie posiada ostatniego elementu
K05: Usuń z pamięci element
     wskazywany przez p
K06: Zakończ

Przykładowe programy

Uwaga:

Zanim uruchomisz program, przeczytaj wstęp do tego artykułu, w którym wyjaśniamy funkcje tych programów oraz sposób korzystania z nich.

Program prezentuje przykładową implementację kolejki priorytetowej. Tworzy on 10 elementów o losowych priorytetach i umieszcza je w kolejce, po czym odczytuje zawartość kolejki i wyświetla ją w oknie konsoli.

Pascal

// Prosta kolejka priorytetowa
// Data: 17.11.2012
// (C)2020 mgr Jerzy Wałaszek
//------------------------------

program prioqueue;

// Definicja typu elementów listy
//-------------------------------
type
  PSLel = ^SLel;
  SLel = record
    next  : PSLel;
    prio  : integer; // priorytet
    Data: integer;
  end;

// Definicja typu obiektowego Queue
//----------------------------------
  Queue = object
    private
      head : PSLel;
      tail : PSLel;

    public
      constructor init;
      destructor destroy;
      function q_empty : boolean;
      function q_front : integer;
      function q_frontprio: integer;
      procedure push(prio, v : integer);
      procedure q_pop;
  end;

//---------------------
// Metody obiektu queue
//---------------------

// Konstruktor - tworzy pustą listę
//---------------------------------
constructor Queue.init;
begin
  head := nil;
  tail := nil;
end;

// Destruktor - usuwa listę z pamięci
//-----------------------------------
destructor Queue.destroy;
begin
  while not q_empty do q_pop;
end;

// Sprawdza, czy kolejka jest pusta
//---------------------------------
function Queue.q_empty : boolean;
begin
  if head = nil then
    q_empty := true
  else
    q_empty := false;
end;

// Zwraca wartość z początku kolejki.
// Wartość specjalna to -MAXINT
//-----------------------------
function Queue.q_front : integer;
begin
  if head = nil then
    q_front := -MAXINT
  else
    q_front := head^.data;
end;

// Zwraca priorytet pierwszego elementu
//-------------------------------------
function Queue.q_frontprio : integer;
begin
  if head = nil then
    q_frontprio := -MAXINT
  else
    q_frontprio := head^.prio;
end;

// Zapisuje do kolejki
//--------------------
procedure Queue.push(prio, v : integer);
var
  p, r : PSLel;
begin
  new(p);
  p^.next := nil;
  p^.prio := prio;
  p^.Data:= v;

  if head = nil then
  begin
    head := p;
    tail := p;
  end
  else if head^.prio < prio then
       begin
         p^.next := head;
         head    := p;
       end
       else
       begin
         r := head;
         while(r^.next <> nil) and
              (r^.next^.prio >= prio) do
           r := r^.next;
         p^.next := r^.next;
         r^.next := p;
         if p^.next = nil then
           tail := p;
       end;
end;

// Usuwa z kolejki
//----------------
procedure Queue.q_pop;
var
  p : PSLel;
begin
  if head <> nil then
  begin
    p := head;
    head := head^.next;
    if head = nil then
      tail := nil;
    dispose(p);
  end;
end;

//---------------
// Program główny
//---------------

var
  K : Queue; // kolejka
  i, p, v : integer;

begin
  Randomize;

  K.init;

  for i := 1 to 10 do
  begin
    v := random(100);
    p := random(10);
    writeln(v:2, ':', p);
    K.push(p, v);
  end;

  writeln('----');

  while not K.q_empty do
  begin
    writeln(K.q_front:2, ':', K.q_frontprio);
    K.q_pop;
  end;

  K.destroy;
end.

C++

// Prosta kolejka priorytetowa
// Data: 17.11.2012
// (C)2020 mgr Jerzy Wałaszek
//------------------------------

#include <iostream>
#include <iomanip>
#include <ctime>
#include <cstdlib>

using namespace std;

const int MAXINT = -2147483647;

// Definicja typu elementów listy
//-------------------------------
struct SLel
{
  SLel * next;
  int prio, data;
};

// Definicja typu obiektowego Queue
//----------------------------------
class Queue
{
  private:
    SLel * head;
    SLel * tail;

  public:
    Queue();  // konstruktor
    ~Queue(); // destruktor
    bool empty(void);
    int  front(void);
    int  frontprio(void);
    void push(int prio, int v);
    void pop(void);
};

//----------------------
// Metody obiektu Queue
//----------------------

// Konstruktor - tworzy pustą listę
//---------------------------------
Queue::Queue()
{
  head = tail = NULL;
}

// Destruktor - usuwa listę z pamięci
//-----------------------------------
Queue::~Queue()
{
  while(head) pop();
}

// Sprawdza, czy kolejka jest pusta
//---------------------------------
bool Queue::empty(void)
{
  return !head;
}

// Zwraca wartość z począteku kolejki.
// Wartość specjalna to -MAXINT
//-----------------------------
int Queue::front(void)
{
  if(head)
    return head->data;
  else
    return -MAXINT;
}

// Zwraca priorytet pierwszego elementu
//-------------------------------------
int Queue::frontprio(void)
{
  if(!head)
    return -MAXINT;
  else
    return head->prio;
}

// Zapisuje do kolejki
//--------------------
void Queue::push(int prio, int v)
{
  SLel *p, *r;
  p = new SLel;
  p->next = NULL;
  p->prio = prio;
  p->data = v;

  if(!head)
    head = tail = p;
  else
    if(head->prio < prio)
    {
      p->next = head;
      head    = p;
    }
    else
    {
      r = head;
    while((r->next) &&
          (r->next->prio >= prio))
      r = r->next;
    p->next = r->next;
    r->next = p;
    if(!p->next)
      tail = p;
    }
}

// Usuwa z kolejki
//----------------
void Queue::pop(void)
{
  if(head)
  {
    SLel * p = head;
    head = head->next;
    if(!head)
      tail = NULL;
    delete p;
  }
}

//---------------
// Program główny
//---------------

int main()
{
  Queue K;   // kolejka
  int i, p, v;

  srand(time(NULL));

  for(i = 0; i < 10; i++)
  {
     v = rand() % 100;
     p = rand() %  10;
     cout << setw(2) << v
          << ":" << p
          << endl;
     K.push(p, v);
  }

  cout << "----\n";

  while(!K.empty())
  {
    cout << setw(2) << K.front() << ":"
         << K.frontprio() << endl;
    K.pop();
  }
}

Basic

' Prosta kolejka priorytetowa
' Data: 17.11.2012
' (C)2020 mgr Jerzy Wałaszek
'------------------------------

Const MAXINT = 2147483647

' Definicja typu elementów listy
'-------------------------------
Type SLel
  next As SLel Ptr
  prio As Integer
  data As Integer
End Type

' Definicja typu obiektowego Queue
'----------------------------------
Type Queue
  Private:
    head As SLel Ptr
    tail As SLel Ptr

  Public:
    Declare Constructor()
    Declare Destructor()
    Declare Function empty() As Integer
    Declare Function q_front As Integer
    Declare Function q_frontprio As Integer
    Declare Sub push(ByVal prio As Integer, _
                       ByVal v As Integer)
    Declare Sub pop()
End Type

'---------------
' Program główny
'---------------

Dim K As Queue
Dim As Integer i, p, v

Randomize

For i = 1 To 10
  v = Int(Rnd()*100)
  p = Int(Rnd()*10)
  Print Using "##:#";v;p
  K.push(p, v)
Next

Print "----"

While K.empty() = 0
  Print Using "##:#";K.front();K.frontprio()
  K.pop()
Wend

End

'---------------------
' Metody obiektu queue
'---------------------

' Konstruktor - tworzy pustą listę
'---------------------------------
Constructor Queue()
  head = 0
  tail = 0
End Constructor

' Destruktor - usuwa listę z pamięci
'-----------------------------------
Destructor Queue()
  While Not q_empty: q_pop: Wend
End Destructor

' Sprawdza, czy kolejka jest pusta
'---------------------------------
Function Queue.empty() As Integer
  If head = 0 Then Return 1
  Return 0
End Function

' Zwraca początek kolejki.
' Wartość specjalna to -MAXINT
'-----------------------------
Function Queue.front() As Integer
  If head = 0 then
    q_front = -MAXINT
  Else
    q_front = head->data
  End If
End Function

' Zwraca priorytet pierwszego elementu
'-------------------------------------
Function Queue.frontprio() As Integer
  If head = 0 then
    q_frontprio = -MAXINT
  Else
    q_frontprio = head->prio
  End If
End Function

' Zapisuje do kolejki
'--------------------
Sub Queue.push(ByVal prio As Integer, _
                  ByVal v As Integer)
  Dim p As SLel Ptr
  Dim r As SLel Ptr

  p = new SLel
  p->next = 0
  p->prio = prio
  p->data = v
 
  If head = 0 Then
  	 head = p
  	 tail = p
  ElseIf head->prio < prio Then
    p->next = head
    head    = p
  Else
    r = head
    while(r->Next <> 0) AndAlso _
         (r->next->prio >= prio)
      r = r->Next
    Wend
    p->next = r->Next
    r->next = p
    If p->Next = 0 Then _
      tail = p
  End If
End Sub

' Usuwa z kolejki
'----------------
Sub Queue.pop()
  Dim p As SLel Ptr
  If head Then
    p = head
    head = head->next
    If head = 0 Then tail = 0
    Delete p
  End If
End Sub

Python (dodatek)

# Prosta kolejka priorytetowa
# Data: 30.06.2024
# (C)2024 mgr Jerzy Wałaszek
#------------------------------

import random

MAXINT = 2147483647


# klasa elementów listy
class SLel:


    # Konstruktor
    def __init__(self, v, p):
        self.next = None
        self.prio = p
        self.data = v


# klasa kolejki priorytetowej Queue
class Queue:


    # Konstruktor
    def __init__(self):
        self.head = None
        self.tail = None


    # destruktor
    def __del__(self):
        while not self.empty():
            self.pop()
        self.head = None
        self.tail = None


    # Sprawdza, czy kolejka jest pusta
    def empty(self):
        return not self.head


    # zwartość z począteku kolejki
    # wartość specjalna to -MAXINT
    def front(self):
        if self.head:
            return self.head.data
        else:
            return -MAXINT


    # priorytet pierwszego elementu
    # wartość specjalna to -MAXINT
    def frontprio(self):
        if self.head:
            return self.head.prio
        else:
            return -MAXINT


    # zapis do kolejki
    def push(self, prio, v):
        p = SLel(v, prio)
        if not bool(self.head):
            self.head = p
            self.tail = p
        elif self.head.prio < prio:
            p.next = self.head
            self.head = p
        else:
            r = self.head
            while r.next and \
                  r.next.prio >= prio:
                r = r.next
            p.next = r.next
            r.next = p
            if not p.next:
                self.tail = p


    # usuwa z kolejki
    def pop(self):
        if self.head:
            self.head = self.head.next
            if not self.head:
                self.tail = None


#---------------
# Program główny
#---------------

q = Queue()
for i in range(10):
    v = random.randrange(100)
    p = random.randrange(10)
    print("%2d:%1d" % (v, p))
    push(p, v)
print("----")
while not q.empty():
    print("%2d:%1d" % \
          (q.front(),
           q.frontprio()))
    q.pop()
q = None

Wynik:

77:3
91:3
73:2
97:9
93:3
72:6
37:9
32:6
83:3
46:3
----
97:9
37:9
72:6
32:6
77:3
91:3
93:3
83:3
46:3
73:2

do podrozdziału do strony

Materiały tylko do użytku dydaktycznego. Ich kopiowanie i powielanie jest dozwolone pod warunkiem podania źródła oraz niepobierania za to pieniędzy.
Pytania proszę przesyłać na adres email: i-lo@eduinf.waw.pl
Serwis wykorzystuje pliki cookies. Jeśli nie chcesz ich otrzymywać, zablokuj je w swojej przeglądarce.

Informacje dodatkowe.