Serwis Edukacyjny w I-LO w Tarnowie ![]() Materiały dla uczniów liceum |
Wyjście Spis treści Wstecz Dalej Autor artykułu: mgr Jerzy Wałaszek |
©2023 mgr Jerzy Wałaszek |
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 od lewej strony. |
![]() |
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.
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. |
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 |
T | – | tablica z kopcem powiększonym o dodany element v. |
n | – | zwiększone o 1 |
i, j | – | indeksy elementów w kopcu, i, j ∈ C |
K01: | i ← n | ustawiamy indeks i na pozycję wstawianego elementu |
K02: | n ← n + 1 | kopiec będzie zawierał o 1 element więcej |
K03: | j ← ( i - 1 ) div 2 | obliczamy indeks rodzica |
K04: | Dopóki i > 0
![]() wykonuj kroki K05...K07 |
sprawdzamy warunek kopca |
K05: | T [ i ] ← T [ j ] | umieszczamy rodzica na miejscu syna |
K06: | i ← j | 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 ).
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 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. |
Pascal// 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. |
C++// 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 ); } |
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 |
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 ).
T | – | tablica przechowująca elementy kopca |
n | – | liczba elementów w kopcu, n ∈ C |
T | – | tablica z kopcem, z którego usunięto szczyt |
n | – | zmniejszone o 1 |
i, j | – | indeksy elementów, i, j ∈ C |
v | – | przechowuje element kopca |
K01: | Jeśli n = 0, to zakończ |
kopiec jest pusty |
K02: | n ← n - 1 | kopiec będzie zawierał o 1 element mniej |
K03: | v ← T [ 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 kroki K07...K11 |
idziemy w dół kopca |
K07: | Jeśli ( j
+ 1 <
n )
![]() to j ← j + 1 |
szukamy większego syna |
K08: | Jeśli v
≥ T [ j ], to Idź do kroku K12 |
jeśli warunek kopca spełniony, wychodzimy z pętli |
K09: | T [ i ] ← T [ j ] | inaczej kopiujemy większego syna do ojca |
K10: | i ← j | 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 ).
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 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. |
Pascal// 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. |
C++// 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; } |
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 |
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.
Pascal// 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. |
C++// 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( ); } } |
Basic' Kolejka priorytetowa z kopcem ' Data: 5.03.2013 ' (C)2020 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 |
![]() |
Zespół Przedmiotowy Chemii-Fizyki-Informatyki w I Liceum Ogólnokształcącym im. Kazimierza Brodzińskiego w Tarnowie ul. Piłsudskiego 4 ©2023 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.