Kolejki priorytetowe


Tematy pokrewne
Podstawowe operacje na tablicach
Podstawowe pojęcia dotyczące list
Reprezentacja list w pamięci komputera
Operacje na listach jednokierunkowych
Sortowanie przez wstawianie z wykorzystaniem listy jednokierunkowej

Kolejka priorytetowa zbudowana na kopcu
Kolejka priorytetowa zbudowana na drzewie BST


Kolejki
Podstawowe pojęcia dotyczące kolejek
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 (headdata)  

 

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: (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: headp ; jeśli tak, to wstawiamy element
K08: tailp  
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 headp  
K13 Zakończ  
K14: rhead ; rozpoczynamy od początku listy
K15: Dopóki ((rnext) ≠ nil) (((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 tailp ; 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:
p  –  wskaźnik elementu listy
Lista kroków:
K01 Jeśli head = nil, to zakończ ; jeśli lista jest pusta, kończymy
K02: phead ;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  

 

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

 



List do administratora Serwisu Edukacyjnego Nauczycieli I LO

Twój email: (jeśli chcesz otrzymać odpowiedź)
Temat:
Uwaga: ← tutaj wpisz wyraz  ilo , inaczej list zostanie zignorowany

Poniżej wpisz swoje uwagi lub pytania dotyczące tego rozdziału (max. 2048 znaków).

Liczba znaków do wykorzystania: 2048

 

W związku z dużą liczbą listów do naszego serwisu edukacyjnego nie będziemy udzielać odpowiedzi na prośby rozwiązywania zadań, pisania programów zaliczeniowych, przesyłania materiałów czy też tłumaczenia zagadnień szeroko opisywanych w podręcznikach.



   I Liceum Ogólnokształcące   
im. Kazimierza Brodzińskiego
w Tarnowie

©2017 mgr Jerzy Wałaszek

Dokument ten rozpowszechniany jest zgodnie z zasadami licencji
GNU Free Documentation License.