Kopiec binarny


Tematy pokrewne   Podrozdziały
Drzewa
Podstawowe pojęcia dotyczące drzew
Przechodzenie drzew binarnych – DFS: pre-order, in-order, post-order
Przechodzenie drzew binarnych – BFS
Badanie drzewa binarnego
Prezentacja drzew binarnych
Kopiec
Drzewa wyrażeń
Drzewa poszukiwań binarnych – BST
Tworzenie drzewa BST
Równoważenie drzewa BST – algorytm DSW
Proste zastosowania drzew BST
Drzewa AVL
Drzewa Splay
Drzewa Czerwono-Czarne
Kompresja Huffmana
Zbiory rozłączne – implementacja za pomocą drzew
Podstawowe operacje na tablicach
Kolejki priorytetowe
  Wstawianie elementu do kopca
Usuwanie elementu ze szczytu kopca
Kolejka priorytetowa z kopcem
W dotąd omawianych przez nas drzewach nie interesowały nas zależności pomiędzy zawartościami węzłów, a jedynie struktura samego drzewa. W tym i następnych rozdziałach będziemy omawiać drzewa binarne, których węzły są powiązane ze sobą nie tylko krawędziami, lecz dodatkowymi warunkami. Pierwszą taką strukturą będzie kopiec (ang. heap).

Kopiec binarny (ang. binary heap) jest kompletnym drzewem binarnym, co oznacza, że posada zapełnione wszystkie poziomy za wyjątkiem ostatniego, a ostatni poziom jest zapełniany bez przerw, poczynając od strony lewej do prawej.

 

  To drzewo nadaje się na kopiec, ponieważ jest kompletne. Ostatni poziom węzły wypełniają bez przerw od lewej do prawej.
  To drzewo nie nadaje się na kopiec. Na ostatnim poziomie brakuje pierwszego węzła.
  To drzewo również nie nadaje się na kopiec. Na ostatnim poziomie mamy przerwę w ciągu węzłów.

 

Oprócz wymogu strukturalnego (drzewo binarne musi być kompletne) kopiec posiada dodatkowy warunek: żaden z synów węzła nie jest od niego większy, czyli nie przechowuje w swoim polu data wartości większej od zawartości pola data swojego ojca.

 

  To jest kopiec, ponieważ drzewo jest drzewem kompletnym, a żaden z synów nie ma wartości większej od swojego ojca.
  To nie jest kopiec, ponieważ zaznaczone na czerwono węzły nie spełniają warunku kopca.

 

Ponieważ kopiec jest drzewem kompletnym, to daje się łatwo zrealizować w tablicy:

 

 

Zwróć uwagę, że w tablicy odkładamy kolejne poziomy drzewa. Na poziomie 0 mamy tylko korzeń, czyli węzeł nr 1. Na poziomie 1 są węzły 1 i 2. Na poziomie 2 mamy węzły 3, 4, 5 i 6. Ponieważ tylko ostatni poziom może nie być w całości zapełniony, w strukturze tej nie występują przerwy – jest ciągiem kolejnych węzłów. Indeksy elementów tablicy odpowiadają numerom węzłów. W drzewie kompletnym nie musimy osobno zapamiętywać krawędzi, ponieważ struktura drzewa zależy w prosty sposób od liczby węzłów i zawsze da się ją odtworzyć. Zatem do utworzenia kopca binarnego potrzebujemy odpowiednio dużej tablicy na elementy oraz dodatkowej zmiennej, która zapamiętuje liczbę elementów przechowywanych w kopcu.

Powiązania pomiędzy węzłami określają proste wzory. Niech n będzie liczbą węzłów w drzewie, a k numerem węzła. Wtedy:

 

numer lewego syna = 2k + 1

numer prawego syna = 2k + 2

numer ojca = [(k - 1) / 2], dla k > 0

lewy syn istnieje, jeśli 2k + 1 < n

prawy syn istnieje, jeśli 2k + 2 < n

węzeł k jest liściem, jeśli 2k + 2 > n

 

Wzory te pozwalają poruszać się po strukturze kopca w górę i w dół.

 

Dla kopca istnieją dwie operacje standardowe: push – wstawianie nowego elementu oraz pop – usuwanie korzenia. Opisujemy je poniżej.

 

Wstawianie elementu do kopca – push

Dodawany element wstawiamy jako ostatni liść kopca. Następnie sprawdzamy kolejno, czy jest on mniejszy lub równy swojemu rodzicowi. Jeśli nie, to zamieniamy wstawiony element z jego rodzicem. Operację kontynuujemy, aż znajdziemy rodzica większego lub równego elementowi lub dojdziemy do korzenia drzewa. Prześledź poniższą tabelkę:

 

  Nowy element wstawiamy jako ostatni liść kopca. Następnie sprawdzamy, czy jest on niewiększy od rodzica. Ponieważ warunek kopca nie jest spełniony, wymieniamy ze sobą węzeł wstawiony z jego rodzicem.
  Na wyższym poziomie znów sprawdzamy warunek kopca - czy syn nie jest większy od rodzica. Warunek nie jest spełniony, zatem wymieniamy rodzica ze wstawionym węzłem i przechodzimy na kolejny poziom drzewa.
  Znów warunek kopca nie jest spełniony, wymieniamy zatem rodzica ze wstawionym węzłem i przechodzimy na kolejny poziom drzewa.
  Kończymy, ponieważ doszliśmy do korzenia drzewa, który nie ma już rodzica. Element został wstawiony do kopca.

 

Algorytm dodawania nowego elementu do kopca

Wejście
T    tablica zawierająca kopiec. Tablica powinna być wystarczająco duża na pomieszczenie dodawanego elementu.
n   liczba elementów w kopcu, n C
v   wartość dodawanego elementu
Wyjście:
T    tablica z kopcem powiększonym o dodany element v.
n   zwiększone o 1
Elementy pomocnicze:
i,j    indeksy elementów w kopcu, i,j C
Lista kroków:
K01: in ; ustawiamy indeks i na pozycję wstawianego elementu
K02: nn + 1 ; kopiec będzie zawierał o 1 element więcej
K03: j ← (i - 1) div 2 ; obliczamy indeks rodzica
K04: Dopóki i > 0 T[j] < v, wykonuj K05...K07 ; sprawdzamy warunek kopca
K05:     T[i] ← T[j] ; umieszczamy rodzica na miejscu syna
K06:     ij ; przenosimy się na pozycję ojca
K07:     j ← (i - 1) div 2 ; obliczamy indeks ojca
K08: T[i] ← v ; wstawiamy element do kopca
K09: Zakończ  

 

Operacja dodawania nowego elementu do kopca posiada klasę złożoności obliczeniowej O(log n).

 

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 generuje 15 liczb pseudolosowych z zakresu od 0 do 99. Następnie tworzy kopiec wprowadzając do niego kolejno wygenerowane liczby. Na końcu wyświetla zawartość kopca w postaci drzewa binarnego, wykorzystując zmodyfikowany nieco algorytm z poprzedniego rozdziału.

 

Lazarus
// Tworzenie kopca w tablicy
// Data: 27.02.2013
// (C)2013 mgr Jerzy Wałaszek
//------------------------------

program create_heap;

// Zmienne globalne

var
  cr,cl,cp : string;            // łańcuchy do znaków ramek
  T : array [0..14] of integer; // kopiec
  n : integer;                  // liczba węzłów

// Procedura wypisuje drzewo
//--------------------------
procedure printBT(sp,sn : string; v : integer);
var
  s : string;
begin
  if v < n then
  begin
    s := sp;
    if sn = cr then s[length(s) - 1] := ' ';
    printBT(s+cp,cr,2 * v + 2);

    s := Copy(sp,1,length(sp)-2);
    writeln(s,sn,T[v]);

    s := sp;
    if sn = cl then s[length(s) - 1] := ' ';
    printBT(s+cp,cl,2 * v + 1);
  end;
end;

// procedura wstawia v do kopca
//-----------------------------
procedure heap_push(v : integer);
var
  i,j : integer;
begin
  i := n;
  inc(n);
  j := (i - 1) div 2;

  while (i > 0) and (T[j] < v) do
  begin
    T[i] := T[j];
    i := j;
    j := (i - 1) div 2;
  end;

  T[i] := v;
end;

// **********************
// *** PROGRAM GŁÓWNY ***
// **********************

var
  i, v : integer;
begin
  // ustawiamy łańcuchy znakowe, ponieważ nie wszystkie edytory pozwalają
  // wstawiać znaki konsoli do tworzenia ramek.
  // cr = +--
  //      |

  // cl = |
  //      +--

  // cp = |
  //      |

  cr := #218#196;
  cl := #192#196;
  cp := #179#32;

  randomize;

  n := 0;

  for i := 1 to 15 do
  begin
    v := random(100);
    write(v,' ');
    heap_push(v);
  end;

  writeln;
  writeln;

  printBT('','',0);
end.
Code::Blocks
// Tworzenie kopca w tablicy
// Data: 27.02.2013
// (C)2013 mgr Jerzy Wałaszek
//------------------------------

#include <iostream>
#include <string>
#include <ctime>
#include <cstdlib>

using namespace std;

// Zmienne globalne

string cr,cl,cp;      // łańcuchy do znaków ramek
int T[15], n = 0;

// Procedura wypisuje drzewo
//--------------------------
void printBT(string sp, string sn, int v)
{
  string s;

  if(v < n)
  {
    s = sp;
    if(sn == cr) s[s.length() - 2] = ' ';
    printBT(s + cp, cr, 2 * v + 2);

    s = s.substr(0,sp.length()-2);

    cout << s << sn << T[v] << endl;

    s = sp;
    if(sn == cl) s[s.length() - 2] = ' ';
    printBT(s + cp, cl, 2 * v + 1);
  }
}

// procedura wstawia v do kopca
//-----------------------------
void heap_push(int v)
{
  int i,j;

  i = n++;
  j = (i - 1) / 2;

  while(i > 0 && T[j] < v)
  {
    T[i] = T[j];
    i = j;
    j = (i - 1) / 2;
  }

  T[i] = v;
}

// **********************
// *** PROGRAM GŁÓWNY ***
// **********************

int main()
{
  int i, v;

  srand(time(NULL));

  // ustawiamy łańcuchy znakowe, ponieważ nie wszystkie edytory pozwalają
  // wstawiać znaki konsoli do tworzenia ramek.
  // cr = +--
  //      |

  // cl = |
  //      +--

  // cp = |
  //      |

  cr = cl = cp = "  ";
  cr[0] = 218; cr[1] = 196;
  cl[0] = 192; cl[1] = 196;
  cp[0] = 179;

  for(i = 0; i < 15; i++)
  {
    v = rand() % 100;
    cout << v << " ";
    heap_push(v);
  }

  cout << endl << endl;

  printBT("","",0);
}
Free Basic
' Tworzenie kopca w tablicy
' Data: 27.02.2013
' (C)2013 mgr Jerzy Wałaszek
'------------------------------

Dim Shared As Integer T(0 To 14)
Dim Shared As Integer n = 0
Dim Shared As String * 2 cr,cl,cp

' Procedura wypisuje drzewo
'--------------------------
Sub printBT(sp As String, sn As String, v As Integer)

  Dim As String s

  If v < n Then
    s = sp
    If sn = cr Then Mid(s,Len(s) - 1, 1) = " "
    printBT(s + cp, cr, 2 * v + 2)

    s = Mid(s,1, Len(sp)-2)
    Print Using "&&&";s;sn;T(v)

    s = sp
    If sn = cl Then Mid(s,Len(s) - 1, 1) = " "
    printBT(s + cp, cl, 2 * v + 1)
  End If
End Sub

' procedura wstawia v do kopca
'-----------------------------
Sub heap_push(v As Integer)

  Dim As Integer i,j

  i = n
  n += 1
  j = (i - 1) \ 2

  While i > 0 AndAlso T(j) < v
    T(i) = T(j)
    i = j
    j = (i - 1) \ 2
  Wend

  T(i) = v
End Sub

' **********************
' *** PROGRAM GŁÓWNY ***
' **********************

Dim As Integer i, v

Randomize

' ustawiamy łańcuchy znakowe, ponieważ nie wszystkie edytory pozwalają
' wstawiać znaki konsoli do tworzenia ramek.
' cr = +--
'      |

' cl = |
'      +--

' cp = |
'      |

cr = Chr(218) + Chr(196)
cl = Chr(192) + Chr(196)
cp = Chr(179) + " "
  
For i = 1 To 15
  v = Int(Rnd() * 100)
  print v;
  heap_push(v)
Next

Print
Print

printBT("","",0)

End
Wynik
41 84 98 87 82 14 59 18 71 34 43 83 23 65 36

    ┌─36
  ┌─65
  │ └─59
┌─84
│ │ ┌─23
│ └─83
│   └─14
98
│   ┌─43
│ ┌─82
│ │ └─34
└─87
  │ ┌─41
  └─71
    └─18


Usuwanie elementu ze szczytu kopca – pop

Usuwamy korzeń drzewa, wstawiając na jego miejsce ostatni z liści. Następnie idziemy kolejnymi poziomami w dół drzewa, sprawdzając warunek kopca. Jeśli nie jest spełniony, to zamieniamy ojca z największym z synów. Operację kontynuujemy aż do momentu spełnienia warunku kopca lub osiągnięcia liścia. Prześledź poniższą tabelkę:

 

  Korzeń drzewa usuwamy, zastępując go przez ostatni liść.
  Sprawdzamy warunek kopca. Nie jest spełniony, zatem wymieniamy miejscami ojca z największym synem i przechodzimy na niższy poziom drzewa.
  Sprawdzamy warunek kopca. Nie jest spełniony, zatem wymieniamy ojca z największym synem i przechodzimy na niższy poziom drzewa.
  Sprawdzamy warunek kopca. Nie jest spełniony, zatem wymieniamy ojca z największym synem i przechodzimy na niższy poziom drzewa.
  Ponieważ element stał się liściem i nie ma synów, kończymy.

 

Operacja usuwania elementu z kopca ma klasę złożoności obliczeniowej równą O(log n). Zwróć uwagę, że usuwany element posiada zawsze największą wartość w kopcu. Ta cecha czyni kopiec idealnym materiałem dla kolejek priorytetowych. Umożliwia również wykonanie sortowania o klasie złożoności obliczeniowej równej O(nlog n) – sortowanie kopcowe (ang. heap sort).

 

Algorytm usuwania szczytu kopca

Wejście
T tablica przechowująca elementy kopca
n liczba elementów w kopcu, n C
Wyjście:
T tablica z kopcem, z którego usunięto szczyt
n zmniejszone o 1
Elementy pomocnicze:
i,j indeksy elementów, i,j C
v przechowuje element kopca
Lista kroków:
K01: Jeśli n = 0, to zakończ ; kopiec jest pusty
K02: nn - 1 ; kopiec będzie zawierał o 1 element mniej
K03: vT[n] ; w v zapamiętujemy ostatni element kopca
K04: i ← 0 ; przeszukiwanie drzewa rozpoczynamy od korzenia
K05: j ← 1 ; j wskazuje lewego syna
K06: Dopóki j < n: wykonuj K07...K11 ; idziemy w dół kopca
K07:     Jeśli (j + 1 < n) (T[j + 1] > T[j]), to jj + 1 ; szukamy większego syna
K08:     Jeśli v ≥ T[j], to Idź do K12 ; jeśli warunek kopca spełniony, wychodzimy z pętli
K09:     T[i] ← T[j] ; inaczej kopiujemy większego syna do ojca
K10:     ij ; przechodzimy na pozycję większego syna
K11:     j ← 2j + 1 ; j wskazuje lewego syna
K12 T[i] ← v ; umieszczamy v w kopcu
K13: Zakończ  

 

Operacja usuwania elementu z kopca posiada klasę złożoności obliczeniowej O(log n).

 

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 tworzy kopiec z 200 liczb pseudolosowych od -99 do 99. Następnie kolejno pobiera elementy ze szczytu kopca, aż kopiec będzie pusty. Pobierane elementy są wyświetlane w oknie konsoli. Zwróć uwagę, że są one uporządkowane malejąco. Własność ta pozwala wykorzystać kopiec do szybkiego sortowania w czasie O(n log n). Sortowanie może odbywać się w miejscu. Więcej na ten temat znajdziesz w artykule o sortowaniu przez kopcowanie.

 

Lazarus
// Usuwanie elementu z kopca
// Data: 5.03.2013
// (C)2013 mgr Jerzy Wałaszek
//------------------------------

program heapsort;

var
  T : array [0..199] of integer; // kopiec
  n : integer;                   // liczba węzłów

// Procedura wstawia v do kopca
//-----------------------------
procedure heap_push(v : integer);
var
  i,j : integer;
begin
  i := n;
  inc(n);
  j := (i - 1) div 2;

  while (i > 0) and (T[j] < v) do
  begin
    T[i] := T[j];
    i := j;
    j := (i - 1) div 2;
  end;

  T[i] := v;
end;

// Procedura usuwa korzeń z kopca
//------------------------------
procedure heap_pop;
var
  i,j,v : integer;
begin
  if n > 0 then
  begin
    dec(n);

    v := T[n];

    i := 0;
    j := 1;

    while j < n do
    begin
      if (j + 1 < n) and (T[j + 1] > T[j]) then inc(j);
      if v >= T[j] then break;
      T[i] := T[j];
      i := j;
      j := 2 * j + 1;
    end;

    T[i] := v;
  end;
end;

// **********************
// *** PROGRAM GŁÓWNY ***
// **********************

var
  i, v : integer;
begin
  randomize;

  n := 0;

  // Tworzymy kopiec

  for i := 1 to 200 do
  begin
    v := random(199) - 99;
    write(v:4);
    heap_push(v);
  end;

  writeln;
  writeln;

  // Rozbieramy kopiec

  while n > 0 do
  begin
    write(T[0]:4);
    heap_pop;
  end;

  writeln;
  writeln;

end.
Code::Blocks
// Usuwanie elementu z kopca
// Data: 5.03.2013
// (C)2013 mgr Jerzy Wałaszek
//------------------------------

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

using namespace std;

int T[200];    // kopiec
int n = 0;     // liczba węzłów

// Procedura wstawia v do kopca
//-----------------------------
void heap_push(int v)
{
  int i,j;

  i = n++;
  j = (i - 1) / 2;

  while(i > 0 && T[j] < v)
  {
    T[i] = T[j];
    i = j;
    j = (i - 1) / 2;
  }

  T[i] = v;
}

// Procedura usuwa korzeń z kopca
//------------------------------
void heap_pop()
{
  int i,j,v;

  if(n--)
  {
    v = T[n];

    i = 0;
    j = 1;

    while(j < n)
    {
      if(j + 1 < n && T[j + 1] > T[j]) j++;
      if(v >= T[j]) break;
      T[i] = T[j];
      i = j;
      j = 2 * j + 1;
    }

    T[i] = v;
  }
}

// **********************
// *** PROGRAM GŁÓWNY ***
// **********************

int main()
{
  int i,v;

  srand(time(NULL));

  // Tworzymy kopiec

  for(i = 0; i < 200; i++)
  {
    v = (rand() % 199) - 99;
    cout << setw(4) << v;
    heap_push(v);
  }

  cout << endl << endl;

  // Rozbieramy kopiec

  while(n)
  {
    cout << setw(4) << T[0];
    heap_pop();
  }

  cout << endl << endl;

  return 0;
}
Free Basic
' Usuwanie elementu z kopca
' Data: 5.03.2013
' (C)2013 mgr Jerzy Wałaszek
'------------------------------

Dim Shared As integer T(0 To 199)    ' kopiec
Dim Shared As Integer n = 0          ' liczba węzłów

' Procedura wstawia v do kopca
'-----------------------------
Sub heap_push(ByVal v As Integer)
  Dim As Integer i,j

  i = n
  n += 1
  j = (i - 1) \ 2

  While (i > 0) andalso (T(j) < v)
    T(i) = T(j)
    i = j
    j = (i - 1) / 2
  Wend

  T(i) = v
End Sub

' Procedura usuwa korzeń z kopca
'------------------------------
Sub heap_pop()
  Dim As Integer i,j,v

  If n > 0 Then
    n -= 1
    
    v = T(n)

    i = 0
    j = 1

    While j < n
      If (j + 1 < n) AndAlso (T(j + 1) > T(j)) Then j += 1
      If v >= T(j) Then Exit While
      T(i) = T(j)
      i = j
      j = 2 * j + 1
    Wend

    T(i) = v
  End If
End Sub

' **********************
' *** PROGRAM GŁÓWNY ***
' **********************

Dim As Integer i,v

Randomize

' Tworzymy kopiec

For i = 1 To 200
  v = Int(Rnd() * 199) - 99
  Print Using "####";v;
  heap_push(v)
Next

Print
Print

' Rozbieramy kopiec

While n > 0
  Print Using "####";T(0);
  heap_pop()
Wend

Print
Print

End
Wynik
 -55 -46 -45  13  31  75  84 -75  89   2 -26  64  -3 -31  77  14  25  91 -10 -91
  28  51 -72  42 -41  70  47   2  64 -14 -48  66  70  94 -99  94 -61  72 -90 -61
  42 -37  86  55  47 -38 -36 -67  77 -20  21  65  21  95 -91   2  75  60  95  11
  89 -59 -71  24  21  13  61  17   0 -70 -16  57  22  98  44  57   7 -86  66 -78
  19  20 -37  51  -6  85  65 -47  61  40 -80 -38 -90   2  -2  50 -46  79  86  80
  10 -85 -72 -56 -51 -68  76  43 -36 -75  32 -42 -90  46  65 -23 -46  72  55 -96
  99 -76  37  55 -72 -33  32 -42  38  93 -85 -86 -87  63 -80  37  10  27  90  75
  80  90 -99 -37 -93 -14  46  67 -84  26 -99  78 -90  22  12 -97 -86  55 -51  29
  63 -64  51  55 -52  22  50 -77  -4  91   1  25 -41  15 -84 -34 -69  92  29  85
 -21  91 -21   5 -15 -50 -10 -74 -95  48  95 -10 -39  33 -55  71  45   7 -23 -79


  99  98  95  95  95  94  94  93  92  91  91  91  90  90  89  89  86  86  85  85
  84  80  80  79  78  77  77  76  75  75  75  72  72  71  70  70  67  66  66  65
  65  65  64  64  63  63  61  61  60  57  57  55  55  55  55  55  51  51  51  50
  50  48  47  47  46  46  45  44  43  42  42  40  38  37  37  33  32  32  31  29
  29  28  27  26  25  25  24  22  22  22  21  21  21  20  19  17  15  14  13  13
  12  11  10  10   7   7   5   2   2   2   2   1   0  -2  -3  -4  -6 -10 -10 -10
 -14 -14 -15 -16 -20 -21 -21 -23 -23 -26 -31 -33 -34 -36 -36 -37 -37 -37 -38 -38
 -39 -41 -41 -42 -42 -45 -46 -46 -46 -47 -48 -50 -51 -51 -52 -55 -55 -56 -59 -61
 -61 -64 -67 -68 -69 -70 -71 -72 -72 -72 -74 -75 -75 -76 -77 -78 -79 -80 -80 -84
 -84 -85 -85 -86 -86 -86 -87 -90 -90 -90 -90 -91 -91 -93 -95 -96 -97 -99 -99 -99

 

Kolejka priorytetowa z kopcem

Kopiec szczególnie dobrze nadaje się do realizacji kolejki priorytetowej. Poniżej przedstawiamy prosty przykład programu obiektowego, który tworzy taką kolejkę i wykorzystuje ją. Program jest modyfikacją programu przedstawionego w rozdziale o kolejkach priorytetowych.

Program tworzy obiekt kolejki priorytetowej o rozmiarze 10 elementów. Generuje dziesięć razy liczbę losową od 0 do 99 oraz odpowiadający jej priorytet od 0 do 9. Liczbę z priorytetem umieszcza w kolejce. Następnie pobiera z kolejki kolejne elementy i wyświetla w oknie konsoli. Zwróć uwagę, że liczby zostają z kolejki pobrane zgodnie z malejącą kolejnością ich priorytetów.

Uwaga, program nie sprawdza, czy dane mieszczą się w kolejce.

 

Lazarus
// Kolejka priorytetowa z kopcem
// Data: 5.03.2013
// (C)2013 mgr Jerzy Wałaszek
//------------------------------

program heap_queue;

// Definicja typu obiektowego queue
//---------------------------------
  type
    qelement = record
      prio : integer;
      data : integer;
    end;

    Tqelement = array of qelement;

  queue = object
    private

      T : Tqelement;  // kopiec dynamiczny
      n : integer;    // liczba elementów

    public
      constructor init(max_n : integer);
      destructor  destroy;
      function    empty : boolean;
      function    front : integer;
      function    frontprio: integer;
      procedure   push(prio,v : integer);
      procedure   pop;
  end;

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

// Konstruktor - rezerwuje pamięć na kopiec
//-----------------------------------------
constructor queue.init(max_n : integer);
begin
  SetLength(T,max_n);  // tworzymy tablicę dynamiczną
  n := 0;              // kopiec jest pusty
end;

// Destruktor - usuwa tablicę z pamięci
//-------------------------------------
destructor queue.destroy;
begin
  SetLength(T,0);
end;

// Sprawdza, czy kolejka jest pusta
//---------------------------------
function queue.empty : boolean;
begin
  empty := (n = 0);
end;

// Zwraca początek kolejki.
// Wartość specjalna to -MAXINT
//-----------------------------
function queue.front : integer;
begin
  if n = 0 then front := -MAXINT
  else          front := T[0].data;
end;

// Zwraca priorytet pierwszego elementu
//-------------------------------------
function queue.frontprio : integer;
begin
  if n = 0 then frontprio := -MAXINT
  else          frontprio := T[0].prio;
end;

// Zapisuje do kolejki wg priorytetu
//----------------------------------
procedure queue.push(prio,v : integer);
var
  i,j : integer;
begin
  i := n;
  inc(n);
  j := (i - 1) div 2;

  while (i > 0) and (T[j].prio < prio) do
  begin
    T[i] := T[j];
    i := j;
    j := (i - 1) div 2;
  end;

  T[i].prio := prio;
  T[i].data := v;

end;

// Usuwa z kolejki
//----------------
procedure queue.pop;
var
  i,j,v,p : integer;
begin
  if n > 0 then
  begin
    dec(n);

    p := T[n].prio;
    v := T[n].data;

    i := 0;
    j := 1;

    while j < n do
    begin
      if (j + 1 < n) and (T[j + 1].prio > T[j].prio) then inc(j);
      if p >= T[j].prio then break;
      T[i] := T[j];
      i := j;
      j := 2 * j + 1;
    end;

    T[i].prio := p;
    T[i].data := v;
  end;

end;

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

var
  Q : queue;   // kolejka 10-cio elementowa
  i,p,v : integer;

begin
  Randomize;

  Q.init(10);

  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
// Kolejka priorytetowa z kopcem
// Data: 5.03.2013
// (C)2013 mgr Jerzy Wałaszek
//------------------------------

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

using namespace std;

const int MAXINT = -2147483647;

// Definicja typu obiektowego queue
//---------------------------------

 struct qelement
 {
   int prio, data;
 };

class queue
{
  private:
    qelement * T;  // kopiec dynamiczny
    int n;         // liczba elementów

  public:
    queue(int max_n);
    ~queue();
    bool empty();
    int  front();
    int  frontprio();
    void push(int prio, int v);
    void pop();
};

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

// Konstruktor - rezerwuje pamięć na kopiec
//-----------------------------------------
queue::queue(int max_n)
{
  T = new qelement[max_n];  // tworzymy tablicę dynamiczną
  n = 0;                    // kopiec jest pusty
}

// Destruktor - usuwa tablicę z pamięci
//-------------------------------------
queue::~queue()
{
  delete [] T;
}

// Sprawdza, czy kolejka jest pusta
//---------------------------------
bool queue::empty()
{
  return !n;
}

// Zwraca początek kolejki.
// Wartość specjalna to -MAXINT
//-----------------------------
int queue::front()
{
  return n ? T[0].data : -MAXINT;
}

// Zwraca priorytet pierwszego elementu
//-------------------------------------
int queue::frontprio()
{
  return n ? T[0].prio : -MAXINT;
}

// Zapisuje do kolejki wg priorytetu
//----------------------------------
void queue::push(int prio, int v)
{
  int i,j;

  i = n++;
  j = (i - 1) / 2;

  while(i > 0 && T[j].prio < prio)
  {
    T[i] = T[j];
    i = j;
    j = (i - 1) / 2;
  }

  T[i].prio = prio;
  T[i].data = v;
}

// Usuwa z kolejki
//----------------
void queue::pop()
{
  int i,j,v,p;

  if(n--)
  {
    p = T[n].prio;
    v = T[n].data;

    i = 0;
    j = 1;

    while(j < n)
    {
      if(j + 1 < n && T[j + 1].prio > T[j].prio) j++;
      if(p >= T[j].prio) break;
      T[i] = T[j];
      i = j;
      j = 2 * j + 1;
    }

    T[i].prio = p;
    T[i].data = v;
  }
}

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

int main()
{
  queue Q(10);   // kolejka 10-cio elementowa
  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
' Kolejka priorytetowa z kopcem
' Data: 5.03.2013
' (C)2012 mgr Jerzy Wałaszek
'------------------------------

Const MAXINT = 2147483647

' Definicja typu obiektowego queue
'---------------------------------
Type qelement
  prio As Integer
  Data As Integer
End Type

Type queue
  Private:
    T As qelement Ptr
    n As Integer

  Public:
    Declare Constructor(max_n As integer)
    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 = 10  ' kolejka 10-cio elementowa
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(max_n As Integer)
  T = New qelement[max_n]
  n = 0
End Constructor

' Destruktor - usuwa listę z pamięci
'-----------------------------------
Destructor queue()
  Delete [] T
End Destructor

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

' Zwraca początek kolejki.
' Wartość specjalna to -MAXINT
'-----------------------------
Function queue.front() As Integer
  If n = 0 then
    front = -MAXINT
  Else
    front = T[0].data
  End If
End Function

' Zwraca priorytet pierwszego elementu
'-------------------------------------
Function queue.frontprio() As Integer
  If n = 0 then
    frontprio = -MAXINT
  Else
    frontprio = T[0].prio
  End If
End Function

' Zapisuje do kolejki
'--------------------
Sub queue.push(ByVal prio As Integer, ByVal v As Integer)
  Dim As Integer i,j

  i = n
  n += 1
  j = (i - 1) \ 2

  While i > 0 AndAlso T[j].prio < prio
    T[i] = T[j]
    i = j
    j = (i - 1) \ 2
  Wend

  T[i].prio = prio
  T[i].data = v
End Sub

' Usuwa z kolejki
'----------------
Sub queue.pop()
  Dim As Integer i,j,v,p

  If n > 0 Then
    n -= 1
    
    p = T[n].prio
    v = T[n].data

    i = 0
    j = 1

    While j < n
      If (j + 1 < n) AndAlso (T[j + 1].prio > T[j].prio) Then j += 1
      If p >= T[j].prio Then Exit While
      T[i] = T[j]
      i = j
      j = 2 * j + 1
    Wend

    T[i].prio = p
    T[i].data = v
  End If
End Sub
Wynik
 3:1
61:6
82:8
77:1
 5:7
60:4
99:2
53:7
91:0
12:9
----
12:9
82:8
53:7
 5:7
61:6
60:4
99:2
 3:1
77:1
91:0

 

 


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

©2018 mgr Jerzy Wałaszek

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

Pytania proszę przesyłać na adres email: i-lo@eduinf.waw.pl

W artykułach serwisu są używane cookies. Jeśli nie chcesz ich otrzymywać,
zablokuj je w swojej przeglądarce.
Informacje dodatkowe