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 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

Lazarus

Code::Blocks

Free Basic

type
  PslistEl = ^slistEl;
  slistEl = record
    next  : PslistEl;
    prio  : integer; // priorytet
    data  : typ_danych;
  end;

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

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

Lazarus	Code::Blocks	Free Basic
function empty : boolean; begin if head = nil then empty := true else empty := false; end;	bool empty(void) { return !head; }	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)

Lazarus

function front : typ_danych;
begin
  if head = nil then front := wartość_specjalna
  else               front := head^.data;
end;

Code::Blocks

typ_danych front()
{
  if(head) return head->data;
  else     return wartość_specjalna;
}

Free 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) (((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).

Lazarus

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;

Code::Blocks

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;
  }
}

Free 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:

–

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

Lazarus

Code::Blocks

Free Basic

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;

void pop()
{
  if(head)
  {
    slistEl * p = head;
    head = head->next;
    if(!head) tail = NULL;
    delete p;
  }  
}

Sub 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

Program

Ważne:

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.

Lazarus

// Prosta kolejka priorytetowa
// Data: 17.11.2012
// (C)2012 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.

Code::Blocks

// Prosta kolejka priorytetowa
// Data: 17.11.2012
// (C)2012 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();
  }
}

Free Basic

' Prosta kolejka priorytetowa
' Data: 17.11.2012
' (C)2012 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

Kolejki priorytetowe

Typ elementu listy

Kolejka priorytetowa – algorytm sprawdzania, czy kolejka jest pusta

Wejście

Wyjście:

Lista kroków:

Kolejka priorytetowa – algorytm odczytu kolejki

Wejście

Wyjście:

Lista kroków:

Kolejka priorytetowa – algorytm zapisu do kolejki

Wejście

Wyjście:

Elementy pomocnicze:

Lista kroków:

Kolejka priorytetowa – algorytm usuwania z kolejki

Wejście

Wyjście:

Elementy pomocnicze:

Lista kroków:

Program

List do administratora Serwisu Edukacyjnego Nauczycieli I LO