Serwis Edukacyjny
w I-LO w Tarnowie
obrazek

Materiały dla uczniów liceum

  Wyjście       Spis treści       Wstecz       Dalej  

Autor artykułu: mgr Jerzy Wałaszek

©2024 mgr Jerzy Wałaszek
I LO w Tarnowie

Kolejki priorytetowe

SPIS TREŚCI W KONSERWACJI
Tematy pomocnicze

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 zostaną 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.

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 nowy element.

Typ elementu listy

Pascal
type
  PslistEl = ^slistEl;
  slistEl = record
    next  : PslistEl;
    prio  : integer; // priorytet
    data  : typ_danych;
  end;
C++
struct slistEl
{
  slistEl * next;
  int prio;  // priorytet
  typ_danych data;
};
Basic
Type slistEl
  next As slistEl Ptr
  prio As Integer  ' priorytet
  data As typ_danych
End Type

Kolejka priorytetowa – algorytm sprawdzania, 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
Pascal
function empty : boolean;
begin
  if head = nil then empty := true
  else empty := false;
end;
C++
bool empty (void)
{
  return !head;
}
Basic
Function empty() As Integer
  If head = 0 Then Return 1
  Return 0
End Function

Kolejka priorytetowa – algorytm odczytu kolejki

Wejście:

head  :  wskaźnik pierwszego elementu listy

Wyjście:

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

Lista kroków:

K01 Jeśli head = 0,
to zakończ z wynikiem wartość specjalna
kolejka pusta?
K02: Zakończ z wynikiem (head→data)  
Pascal
function front : typ_danych;
begin
  if head = nil then front := wartość_specjalna
  else               front := head^.data;
end;
C++
typ_danych front()
{
  if(head) return head->data;
  else     return wartość_specjalna;
}
Basic
Function front() As typ_danych
  If head = 0 then
    front = wartość_specjalna
  Else
    front = head->data
  End If
End Function

Kolejka priorytetowa – algorytm zapisu 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,
to idź do K10
kolejka jest pusta?
K07: head ← p jeśli tak, to wstawiamy element
K08: tail ← p  
K09: Zakończ  
K10: Jeśli (head→prio) ≥ prio,
to idź do K14
sprawdzamy, 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) obrazek (((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,
to
tail ← p
jeśli element jest na końcu, 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).

Pascal
procedure queue.push (prio: integer; v : typ_danych);
var
  p, r : PslistEl;
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;
C++
void queue::push (int prio, int v)
{
  slistEl * p, * r;
  p = new slistEl;
  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;
  }
}
Basic
Sub queue.push (ByVal prio As Integer, ByVal v As Integer)
  Dim p As slistEl Ptr
  Dim r As slistEl Ptr
  p = new slistEl
  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

Kolejka priorytetowa – algorytm usuwania 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,
to zakończ
jeśli lista jest pusta, kończymy
K02: p ← head ;zapamiętujemy adres pierwszego elementu
K03: head ← (head→next) ;odłączamy od listy pierwszy element
K04: Jeśli head = nil,
to tail ← nil
jeśli lista stała się pusta, to nie posiada ostatniego elementu
K05: Usuń z pamięci element
wskazywany przez p
 
K06: Zakończ  
Pascal
procedure pop;
var
  p : PslistEl;
begin
  if head <> nil then
  begin
    p := head;
    head := head^.next;
    if head = nil then tail := nil;
    dispose (p);
  end;
end;
C++
void pop()
{
  if(head)
  {
    slistEl * p = head;
    head = head->next;
    if(!head) tail = NULL;
    delete p;
  } 
}
Basic
 

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
  PslistEl = ^slistEl;
  slistEl = record
    next  : PslistEl;
    prio  : integer;
    data  : integer;
  end;

// Definicja typu obiektowego queue
//---------------------------------
  queue = object
    private
      head : PslistEl;
      tail : PslistEl;

    public
      constructor init;
      destructor destroy;
      function empty : boolean;
      function front : integer;
      function frontprio: integer;
      procedure push (prio, v : integer);
      procedure 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 empty do pop;
end;

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

// Zwraca początek kolejki.
// Wartość specjalna to -MAXINT
//-----------------------------
function queue.front : integer;
begin
  if head = nil then front := -MAXINT
  else               front := head^.data;
end;

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

// Zapisuje do kolejki
//--------------------
procedure queue.push (prio, v : integer);
var
  p, r : PslistEl;
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.pop;
var
  p : PslistEl;
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
  Q : queue;   // kolejka
  i, p, v : integer;

begin
  Randomize;

  Q.init;

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

  writeln('----');

  while not Q.empty do
  begin
    writeln(Q.front:2, ':', Q.frontprio);
    Q.pop;
  end;

  Q.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 slistEl
{
  slistEl * next;
  int prio, data;
};

// Definicja typu obiektowego queue
//---------------------------------
class queue
{
  private:
    slistEl * head;
    slistEl * 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 początek 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)
{
  slistEl * p, * r;
  p = new slistEl;
  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)
  {
    slistEl * p = head;
    head = head->next;
    if(!head) tail = NULL;
    delete p;
  }
}

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

int main()
{
  queue Q;   // 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;
     Q.push (p, v);
  }

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

  while(!Q.empty())
  {
    cout << setw (2) << Q.front() << ":" << Q.frontprio() << endl;
    Q.pop();
  }
}
Basic
' Prosta kolejka priorytetowa
' Data: 17.11.2012
' (C)2020 mgr Jerzy Wałaszek
'------------------------------

Const MAXINT = 2147483647

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

' Definicja typu obiektowego queue
'---------------------------------
Type queue
  Private:
    head As slistEl Ptr
    tail As slistEl Ptr

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

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

Dim Q 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
  Q.push (p, v)
Next

Print "----"

While Q.empty() = 0
  Print Using "##:#";Q.front();Q.frontprio()
  Q.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 empty: 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
    front = -MAXINT
  Else
    front = head->data
  End If
End Function

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

' Zapisuje do kolejki
'--------------------
Sub queue.push (ByVal prio As Integer, ByVal v As Integer)
  Dim p As slistEl Ptr
  Dim r As slistEl Ptr
  p = new slistEl
  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 slistEl Ptr
  If head Then
    p = head
    head = head->next
    If head = 0 Then tail = 0
    Delete p
  End If
End Sub
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

Na początek:  podrozdziału   strony 

Zespół Przedmiotowy
Chemii-Fizyki-Informatyki

w I Liceum Ogólnokształcącym
im. Kazimierza Brodzińskiego
w Tarnowie
ul. Piłsudskiego 4
©2024 mgr Jerzy Wałaszek

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.