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

©2021 mgr Jerzy Wałaszek
I LO w Tarnowie

Kolejki priorytetowe

SPIS TREŚCI
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 ( headdata  )  
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

Zmienne pomocnicze:

p, r  –  wskaźniki elementu listy

Lista kroków:

K01 Utwórz nowy element listy  
K02: p  ← adres nowego elementu  
K03: ( pnext  ) ← nil inicjujemy pola nowego elementu
K04: ( pprio  ) ← prio priorytet
K05: ( pdata  ) ← 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 ( headprio  ) ≥ prio,
to idź do K14
sprawdzamy, czy element ma najwyższy priorytet
K11 ( pnext  ) ← head element wstawiamy na początek listy
K12 head  ← p  
K13 Zakończ  
K14: r  ← head rozpoczynamy od początku listy
K15: Dopóki ( ( rnext  ) ≠ nil ) obrazek ( ( ( rnext  )→prio  ) ≥ prio  ),
wykonuj
r  ← ( rnext  )
szukamy na liście pierwszego elementu o niższym priorytecie
K16: ( pnext  ) ← ( rnext  ) nowy element wstawiamy przed element ( r→next )
K17: ( rnext  ) ← p  
K18: Jeśli ( pnext  ) = 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.

Zmienne 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  ← ( headnext  ) ;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
©2021 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.