Sortowanie stogowe
           Heap Sort


Podrozdziały     Tematy pokrewne
 

Kopiec
Heap

Kopiec jest drzewem binarnym, w którym wszystkie węzły spełniają następujący warunek (zwany warunkiem kopca):

 

Węzeł nadrzędny jest większy lub równy węzłom potomnym (w porządku malejącym relacja jest odwrotna - mniejszy lub równy).

 

Konstrukcja kopca jest nieco bardziej skomplikowana od konstrukcji drzewa binarnego, ponieważ musimy dodatkowo troszczyć się o zachowanie warunku kopca. Zatem po każdym dołączeniu do kopca nowego węzła, sprawdzamy odpowiednie warunki i ewentualnie dokonujemy wymian węzłów na ścieżce wiodącej od dodanego węzła do korzenia.

 

Przykład:

Skonstruować kopiec z elementów zbioru {7 5 9 6 7 8 10}

 

Operacja Opis

7 5 9 6 7 8 10
Budowę kopca rozpoczynamy od pierwszego elementu zbioru, który staje się korzeniem.

7 5 9 6 7 8 10
Do korzenia dołączamy następny element. Warunek kopca jest zachowany.

7 5 9 6 7 8 10
Dodajemy kolejny element ze zbioru.
Po dodaniu elementu 9 warunek kopca przestaje być spełniony. Musimy go przywrócić. W tym celu za nowy węzeł nadrzędny wybieramy nowo dodany węzeł. Poprzedni węzeł nadrzędny wędruje w miejsce węzła dodanego - zamieniamy węzły 7 i 9 miejscami.
Po wymianie węzłów 7 i 9 warunek kopca jest spełniony.

7 5 9 6 7 8 10
Dołączamy kolejny element 6. Znów warunek kopca przestaje być spełniony - zamieniamy miejscami węzły 5 i 6.
Po wymianie węzłów 5 i 6 warunek kopca jest spełniony.

7 5 9 6 7 8 10
Dołączamy kolejny element 7. Warunek kopca przestaje obowiązywać. Zamieniamy miejscami węzły 6 i 7.
Po wymianie węzłów 6 i 7 warunek kopca obowiązuje.

7 5 9 6 7 8 10
Dołączamy kolejny węzeł. Powoduje on naruszenie warunku kopca, zatem wymieniamy ze sobą węzły 7 i 8.
Po wymianie węzłów 7 i 8 warunek kopca znów obowiązuje.

7 5 9 6 7 8 10
Dołączenie ostatniego elementu znów narusza warunek kopca. Zamieniamy miejscami węzeł 8 z węzłem 10.
Po wymianie węzłów 8 i 10 warunek kopca został przywrócony na tym poziomie. Jednakże węzeł 10 stał się dzieckiem węzła 9. Na wyższym poziomie drzewa warunek kopca jest naruszony. Aby go przywrócić znów wymieniamy miejscami węzły, tym razem węzeł 9 z węzłem 10.
Po wymianie tych węzłów warunek kopca obowiązuje w całym drzewie - zadanie jest wykonane.

 

Charakterystyczną cechą kopca jest to, iż korzeń zawsze jest największym (w porządku malejącym najmniejszym) elementem z całego drzewa binarnego.

 

Algorytm

Poniżej przedstawiamy algorytm konstrukcji kopca z elementów zbioru.

 

Specyfikacja problemu

Dane wejściowe

d[ ] - Zbiór zawierający elementy do wstawienia do kopca. Numeracja elementów rozpoczyna się od 1.
n - Ilość elementów w zbiorze,  n N

Dane wyjściowe

d[ ] - Zbiór zawierający kopiec

Zmienne pomocnicze

i - zmienna licznikowa pętli umieszczającej kolejne elementy zbioru w kopcu,  i N, i {2,3,...,n}
j,k - indeksy elementów leżących na ścieżce od wstawianego elementu do korzenia,  j,k C
x - zmienna pomocnicza przechowująca tymczasowo element wstawiany do kopca

 

Lista kroków

K01: Dla i = 2, ..., n: wykonuj K02...K05
K02:     ji;   kj div 2
K03:     x ← d[i]
K04:     Dopóki (k > 0) ∧ (d[k] < x): wykonuj
        d[j] ← d[k]
        jk
        kj div 2
K05:     d[j] ← x
K06: Zakończ

Uwaga: przy porządku malejącym należy zmienić drugi warunek w kroku K04 z d[k] < x na d[k] > x.

 

Schemat blokowy

flow

Algorytm tworzy kopiec w tym samym zbiorze wejściowym d[ ]. Nie wymaga zatem dodatkowych struktur danych i ma złożoność pamięciową klasy O(n).

Pętla nr 1 wyznacza kolejne elementy wstawiane do kopca. Pierwszy element pomijamy, ponieważ zostałby i tak na swoim miejscu. Dlatego pętla rozpoczyna wstawianie od elementu nr 2.

Wewnątrz pętli nr 1 inicjujemy kilka zmiennych:

 

j  - pozycja wstawianego elementu (liścia)
k  - pozycja elementu nadrzędnego (przodka)
x  - zapamiętuje wstawiany element

 

Następnie rozpoczynamy pętlę warunkową nr 2, której zadaniem jest znalezienie w kopcu miejsca do wstawienia zapamiętanego elementu w zmiennej x. Pętla ta wykonuje się do momentu osiągnięcia korzenia kopca (k = 0) lub znalezienia przodka większego od zapamiętanego elementu. Wewnątrz pętli przesuwamy przodka na miejsce potomka, aby zachować warunek kopca, a następnie przesuwamy pozycję j na pozycję zajmowaną wcześniej przez przodka. Pozycja k staje się pozycją nowego przodka i pętla się kontynuuje. Po jej zakończeniu w zmiennej j znajduje się numer pozycji w zbiorze d[ ], na której należy umieścić element w x.

Po zakończeniu pętli nr 1 w zbiorze zostaje utworzona struktura kopca.


 

Programy

Programy tworzą kopiec z pseudolosowo wygenerowanych 15 elementów zbioru. Wynik działania jest następnie prezentowany w formie drzewa binarnego.

 

Efekt uruchomienia programu
   Tworzenie  kopca
----------------------
(C)2005 Jerzy Walaszek

               9
       9               9
   7       8       8       9
 7   3   4   6   8   5   8   6
0 5 0 1 1 4 2 4 2 5 2 0 4 6 4 5

 

DevPascal
// Konstruowanie kopca
//--------------------------------------------------------
// (C)2012 mgr Jerzy Wałaszek
// I Liceum Ogólnokształcące
// im. K. Brodzińskiego
// w Tarnowie
//--------------------------------------------------------

program kopiec;

const N = 31; // liczba elementów
var
  d       : array[1..N] of integer;
  i,j,k,x : integer;

begin
  randomize;
  writeln('   Tworzenie  kopca');
  writeln('----------------------');
  writeln('(C)2005 Jerzy Walaszek');
  writeln;

// Inicjujemy zbiór d[] liczbami pseudolosowymi od 0 do 9

  for i := 1 to N do d[i] := random(10);

// Budujemy kopiec

  for i := 2 to N do
  begin
    j := i; k := j div 2;
    x := d[i];
    while (k > 0) and (d[k] < x) do
    begin
      d[j] := d[k];
      j := k; k := j div 2;
    end;
    d[j] := x;
  end;

// Prezentujemy wyniki

  x := (N + 1) div 2; k := 2;
  for i := 1 to N do
  begin
    for j := 1 to x - 1 do write(' ');
    write(d[i]);
    for j := 1 to x do write(' ');
    if i + 1 = k then
    begin
      k := k + k; x := x div 2; writeln;
    end;
  end;

// Gotowe

  writeln; writeln;
  write('KONIEC, nacisnij klawisz Enter...');
  readln;

end.
Code::Blocks
// Konstruowanie kopca
//--------------------------------------------------------
// (C)2012 mgr Jerzy Wałaszek
// I Liceum Ogólnokształcące
// im. K. Brodzińskiego
// w Tarnowie
//--------------------------------------------------------

#include <iostream>
#include <cstdlib>
#include <time.h>

using namespace std;

int main()
{
  const int N = 31; // liczba elementów
  int d[N + 1],i,j,k,x;

  srand((unsigned)time(NULL));

  cout << "   Tworzenie  kopca\n"
          "----------------------\n"
          "(C)2005 Jerzy Walaszek\n\n";

// Inicjujemy zbiór d[] liczbami pseudolosowymi od 0 do 9

  for(i = 1; i <= N; i++) d[i] = rand() % 10;

// Budujemy kopiec

  for(i = 2; i <= N; i++)
  {
    j = i; k = j / 2;
    x = d[i];
    while((k > 0) && (d[k] < x))
    {
      d[j] = d[k];
      j = k; k = j / 2;
    }
    d[j] = x;
  }

// Prezentujemy wyniki

  x = (N + 1) / 2; k = 2;
  for(i = 1; i <= N; i++)
  {
    for(j = 1; j <= x - 1; j++) cout << " ";
    cout << d[i];
    for(j = 1; j <= x; j++) cout << " ";
    if(i + 1 == k)
    {
      k += k; x /= 2; cout << endl;
    }
  }

// Gotowe

  cout << endl << endl;
  return 0;
}
Free Basic
' Konstruowanie kopca
'--------------------------------------------------------
' (C)2012 mgr Jerzy Wałaszek
' I Liceum Ogólnokształcące
' im. K. Brodzińskiego
' w Tarnowie
'--------------------------------------------------------

CONST N = 31 ' liczba elementów

DIM d(N) AS INTEGER
DIM i AS INTEGER, j AS INTEGER, k AS INTEGER, x AS INTEGER

RANDOMIZE
PRINT "   Tworzenie  kopca"
PRINT "----------------------"
PRINT "(C)2005 Jerzy Walaszek"
PRINT

' Inicjujemy zbiór d[] liczbami pseudolosowymi od 0 do 9

FOR i = 1 TO N: d(i) = INT(RND * 10): NEXT

' Budujemy kopiec

FOR i = 2 TO N
  j = i: k = j \ 2
  x = d(i)
  WHILE (k > 0) AND (d(k) < x)
    d(j) = d(k)
    j = k: k = j / 2
  WEND
  d(j) = x
NEXT

' Prezentujemy wyniki

x = (N + 1) \ 2: k = 2
FOR i = 1 TO N
  FOR j = 1 TO x - 1: PRINT " ";: NEXT
  PRINT USING "#";d(i);
  FOR j = 1 TO x: PRINT " ";: NEXT
  IF i + 1 = k THEN
    k = k + k: x = x \ 2:
    PRINT
  END IF
NEXT

' Gotowe

PRINT: PRINT
PRINT "KONIEC, nacisnij klawisz Enter..."
SLEEP
END
JavaScript
<html>
  <head>
  </head>
  <body>
    <form style="BORDER-RIGHT: #ff9933 1px outset;
                 PADDING-RIGHT: 4px; BORDER-TOP: #ff9933 1px outset;
                 PADDING-LEFT: 4px; PADDING-BOTTOM: 1px;
                 BORDER-LEFT: #ff9933 1px outset; PADDING-TOP: 1px;
                 BORDER-BOTTOM: #ff9933 1px outset;
                 BACKGROUND-COLOR: #ffcc66" name="frmheap">
      <h3 style="text-align: center">Tworzenie kopca</h3>
      <p style="TEXT-ALIGN: center">
        (C)2012 mgr Jerzy Wałaszek - I LO w Tarnowie
      </p>
      <hr>
      <p style="TEXT-ALIGN: center">
<input onclick="main()" type="button" value="Buduj Kopiec" name="B1">
      </p>
      <p style="TEXT-ALIGN: center">
        <font face="Courier New"><span id="t_out">.</span></font>
      </p>
    </form>

<script language=javascript>

// Konstruowanie kopca
//--------------------------------------------------------
// (C)2012 mgr Jerzy Wałaszek
// I Liceum Ogólnokształcące
// im. K. Brodzińskiego
// w Tarnowie
//--------------------------------------------------------


function main()
{
  var N = 31; // liczba elementów
  var d = new Array(N+1);
  var i,j,k,x,t;

// Inicjujemy zbiór d[] liczbami pseudolosowymi od 0 do 9

  for(i = 1; i <= N; i++) d[i] = Math.floor(Math.random() * 10);

// Budujemy kopiec

  for(i = 2; i <= N; i++)
  {
    j = i; k = Math.floor(j / 2);
    x = d[i];
    while((k > 0) && (d[k] < x))
    {
      d[j] = d[k];
      j = k; k = Math.floor(j / 2);
    }
    d[j] = x;
  }

// Prezentujemy wyniki

  t = ""; x = (N + 1) / 2; k = 2;
  for(i = 1; i <= N; i++)
  {
    for(j = 1; j <= x - 1; j++) t += "&nbsp;";
    t += d[i];
    for(j = 1; j <= x; j++) t += "&nbsp;";
    if(i + 1 == k)
    {
      k += k; x = Math.floor(x / 2); t += "<BR>";
    }
  }

// Gotowe

  document.getElementById("t_out").innerHTML = t;
}

</script> 

  </body>
</html>

 

Tutaj możesz przetestować działanie prezentowanego skryptu:

Tworzenie kopca

(C)2012 mgr Jerzy Wałaszek - I LO w Tarnowie


.

 

Podsumowanie

W rozdziale opisaliśmy bardzo prosty algorytm pozwalający konstruować kopiec. Algorytm ten posiada pesymistyczną klasę złożoności czasowej O(n log n) (liniowo logarytmiczną) - każde wstawienie nowego elementu na stos może wymagać tyle przesunięć, ile jest węzłów kopca na ścieżce od miejsca wstawiania do korzenia drzewa. Nie trudno zauważyć, iż liczba ta jest równa lub mniejsza od wysokości kopca, czyli log2n. Ponieważ operację tę wykonujemy (n - 1) razy, to dostajemy górne oszacowanie właśnie O(n log n).

W przypadku optymistycznym, gdy dodanie nowego elementu nie narusza warunku kopca, algorytm ma klasę czasowej złożoności obliczeniowej O(n) (liniową). Jednakże cecha ta nie bardzo się nam przyda przy sortowaniu, ponieważ zbiór ze strukturą kopca nie tworzy zbioru uporządkowanego liniowo - bardzo łatwo się możesz o tym przekonać analizując podany na początku rozdziału przykład.

 

Zadania dla ambitnych

  1. Na podstawie naszego algorytmu wyznacz maksymalną liczbę operacji porównań przy tworzeniu kopca z 31 elementów.
  2. Nasz algorytm nie jest najefektywniejszym algorytmem do konstrukcji kopców. Poszukaj w sieci Internet informacji o algorytmie Floyda.
  3. Zaprojektuj algorytm, który przyjmie jako parametry wejściowe liczbę elementów oraz zbiór ze strukturą kopca i sprawdzi, czy faktycznie jest w niej zachowany warunek kopca dla wszystkich węzłów. Jeśli tak, to algorytm powinien zwracać wartość logiczną true, a false w przypadku przeciwnym.

Zobacz również na: | Drzewo binarne | Rozbiór kopca | Sortowanie przez kopcowanie

 



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.