Sortowanie stogowe
           Heap Sort


Podrozdziały   Tematy pokrewne

Algorytm

W tym rozdziale nauczymy się rozbierać kopiec.  Zasada jest następująca:

  1. Zamień miejscami korzeń z ostatnim liściem, który wyłącz ze struktury kopca. Elementem pobieranym z kopca jest zawsze jego korzeń, czyli element największy.
  2. Jeśli jest to konieczne, przywróć warunek kopca idąc od korzenia w dół.
  3. Kontynuuj od kroku 1, aż kopiec będzie pusty.

Przykład:

Dokonaj rozbioru następującego kopca:

 


Operacja Opis

9
Rozbiór kopca rozpoczynamy od korzenia, który usuwamy ze struktury kopca. W miejsce korzenia wstawiamy ostatni liść.
   
Poprzednia operacja zaburzyła strukturę kopca. Idziemy zatem od korzenia w dół struktury przywracając warunek kopca - przodek większy lub równy od swoich potomków. Praktycznie polega to na zamianie przodka z największym potomkiem. Operację kontynuujemy dotąd, aż natrafimy na węzły spełniające warunek kopca.
 
8 9
Usuwamy z kopca kolejny korzeń zastępując go ostatnim liściem
   W nowym kopcu przywracamy warunek kopca.
 
7 8 9
Usuwamy z kopca kolejny korzeń zastępując go ostatnim liściem
    

W nowym kopcu przywracamy warunek kopca. W tym przypadku już po pierwszej wymianie węzłów warunek koca jest zachowany w całej strukturze.

   
5 7 8 9
Usuwamy z kopca kolejny korzeń zastępując go ostatnim liściem
 

Przywracamy warunek kopca w strukturze.

 
4 5 7 8 9
Usuwamy z kopca kolejny korzeń zastępując go ostatnim liściem
      

Przywracamy warunek kopca w strukturze.

    
2 4 5 7 8 9
Usuwamy z kopca kolejny korzeń zastępując go ostatnim liściem.
            
1 2 4 5 7 8 9
Po wykonaniu poprzedniej operacji usunięcia w kopcu pozostał tylko jeden element - usuwamy go. Zwróć uwagę, iż usunięte z kopca elementy tworzą ciąg uporządkowany.

 

Operację rozbioru kopca można przeprowadzić w miejscu. Jeśli mamy zbiór d[ ] ze strukturą kopca, to idąc od końca zbioru (ostatnie liście drzewa) w kierunku początku zamieniamy elementy z pierwszym elementem zbioru (korzeń drzewa), a następnie poruszając się od korzenia w dół przywracamy warunek kopca w kolejno napotykanych węzłach.

 

Specyfikacja problemu

Dane wejściowe

d[ ] - Zbiór zawierający poprawną strukturę kopca. Elementy są numerowane począwszy od 1.
n - Ilość elementów w zbiorze,  n N

Dane wyjściowe

d[ ] - Zbiór zawierający elementy pobrane z kopca ułożone w porządku rosnącym

Zmienne pomocnicze

i - zmienna licznikowa pętli pobierającej kolejne elementy z kopca,  i N, i {n,n-1,...,2}
j,k - indeksy elementów leżących na ścieżce w dół od korzenia,  j,k N
m - indeks większego z dwóch elementów potomnych, m N

 

Lista kroków

K01: Dla i = n, n - 1, ..., 2: wykonuj K02...K08
K02:     d[1] ↔ d[i]
K03:     j ← 1;  k ← 2
K04:     Dopóki (k < i) wykonuj K05...K08
K05:         Jeżeli (k + 1 < i) ∧ (d[k + 1] > d[k]), to mk + 1
        inaczej  mk
K06:         Jeżeli d[m] ≤ d[j], to wyjdź z pętli K04 i kontynuuj następny obieg K01
K07:         d[j] ↔ d[m]
K08:         jmkj + j
K09: Zakończ

 

Schemat blokowy

flow

Rozbiór kopca wykonywany jest w dwóch zagnieżdżonych pętlach. Pętla nr 1 zamienia miejscami kolejne liście ze spodu drzewa z korzeniem. Zadaniem pętli nr 2 jest przywrócenie w strukturze warunku kopca.

Pętla nr 1 przebiega wstecz indeksy elementów zbioru d[ ] poczynając od indeksu n a kończąc na indeksie 2. Element i-ty jest wymieniany z korzeniem kopca. Po tej wymianie rozpoczynamy w pętli nr 2 przeglądanie drzewa od korzenia w dół. Zmienna j przechowuje indeks przodka, zmienna k przechowuje indeks lewego potomka. Pętla nr 2 kończy się, gdy węzeł j-ty nie posiada potomków. Wewnątrz pętli wyznaczamy w zmiennej m indeks większego z dwóch węzłów potomnych. Następnie sprawdzamy, czy w węźle nadrzędnym j-tym jest zachowany warunek kopca. Jeśli tak, to następuje wyjście z pętli nr 2. W przeciwnym razie zamieniamy miejscami węzeł nadrzędny j-ty z jego największym potomkiem m-tym i za nowy węzeł nadrzędny przyjmujemy węzeł m-ty. W zmiennej k wyznaczamy indeks jego lewego potomka i kontynuujemy pętlę nr 2.

Po wyjściu z pętli nr 2 zmniejszamy zmienną i o 1 - przenosimy się do kolejnego, ostatniego liścia drzewa i kontynuujemy pętlę nr 1.

W celu wyznaczenia klasy złożoności obliczeniowej algorytmu rozbioru kopca zauważamy, iż pętla zewnętrzna nr 1 wykona się n - 1 razy, a w każdym obiegu tej pętli pętla wewnętrzna wykona się maksymalnie log2n razy. Daje to zatem górne oszacowanie O(n log n) w przypadku pesymistycznym oraz O(n) w przypadku optymistycznym, który wystąpi tylko wtedy, gdy zbiór d[ ] będzie zbudowany z ciągu tych samych elementów.


 

Programy

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

Zbior wejsciowy ze struktura kopca:

 9 7 8 0 6 2 6 0 0 0 4 0 0 6 4

       9
   7       8
 0   6   2   6
0 0 0 4 0 0 6 4

Zbior wyjsciowy po rozbiorze kopca:

 0 0 0 0 0 0 2 4 4 6 6 6 7 8 9

 

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

program kopiec;

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

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

// W zbiorze d konstruujemy kopiec

   d[1] := 9;
   for i := 2 to N do d[i] := random(d[i div 2] + 1);

// Prezentujemy kopiec

  writeln('Zbior wejsciowy ze struktura kopca:');
  writeln;
  for i := 1 to N do write(d[i]:2);
  writeln; writeln;
  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;

// Rozbieramy kopiec

  for i := N downto 2 do
  begin
    x := d[1]; d[1] := d[i]; d[i] := x;
    j := 1; k := 2;
    while k < i do
    begin
      if (k + 1 < i) and (d[k + 1] > d[k]) then
        m := k + 1
      else
        m := k;
      if d[m] <= d[j] then break;
      x := d[j]; d[j] := d[m]; d[m] := x;
      j := m; k := j + j;
    end;
  end;

// Wyświetlamy wynik rozbioru kopca

  writeln;
  writeln('Zbior wyjsciowy po rozbiorze kopca:');
  writeln;
  for i := 1 to N do write(d[i]:2);

// Gotowe

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

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

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

using namespace std;

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

  srand((unsigned)time(NULL));

  cout << "    Rozbior  kopca\n"
          "----------------------\n"
          "(C)2005 Jerzy Walaszek\n\n"
          "Zbior wejsciowy ze struktura kopca:\n\n";

// W zbiorze d konstruujemy kopiec

   d[1] = 9;
   for(i = 2; i <= N; i++) d[i] = rand() % (d[i / 2] + 1);

// Prezentujemy kopiec

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

// Rozbieramy kopiec

  for(i = N; i > 1; i--)
  {
    swap(d[1], d[i]);
    j = 1; k = 2;
    while(k < i)
    {
      if((k + 1 < i) && (d[k + 1] > d[k]))
        m = k + 1;
      else
        m = k;
      if(d[m] <= d[j]) break;
      swap(d[j], d[m]);
      j = m; k = j + j;
    }
  }

// Wyświetlamy wynik rozbioru kopca

  cout << endl << "Zbior wyjsciowy po rozbiorze kopca:\n\n";
  
  for(i = 1; i <= N; i++) cout << setw(2) << d[i];
  cout << endl << endl;

// Gotowe

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

CONST N = 15 ' liczba elementów

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

RANDOMIZE

PRINT "    Rozbior  kopca"
PRINT "----------------------"
PRINT "(C)2005 Jerzy Walaszek"
PRINT

' W zbiorze d konstruujemy kopiec

d(1) = 9
FOR i = 2 TO N: d(i) = INT(RND * (d(i \ 2) + 1)): NEXT

' Prezentujemy kopiec

PRINT "Zbior wejsciowy ze struktura kopca:"
PRINT
FOR i = 1 TO N: PRINT USING "##";d(i);:NEXT
PRINT: PRINT
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

' Rozbieramy kopiec

FOR i = N TO 2 STEP -1
  SWAP d(1), d(i)
  j = 1: k = 2
  WHILE k < i
    IF (k + 1 < i) AND (d(k + 1) > d(k)) THEN
      m = k + 1
    ELSE
      m = k
    END IF
    IF d(m) <= d(j) THEN EXIT WHILE
    SWAP d(j), d(m)
    j = m: k = j + j
  WEND
NEXT

' Wyświetlamy wynik rozbioru kopca

PRINT
PRINT "Zbior wyjsciowy po rozbiorze kopca:"
PRINT
FOR i = 1 TO N: PRINT USING "##";d(i);:NEXT
PRINT: PRINT

' Gotowe

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">Rozbiór 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="Rozbierz Kopiec" name="B1">
      </p>
      <p style="TEXT-ALIGN: center">
        <font face="Courier New"><span id="t_out">.</span></font>
      </p>
    </form>

<script language=javascript>

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


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

// W zbiorze d konstruujemy kopiec

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

// Prezentujemy kopiec

  t = "";
  for(i = 1; i <= N; i++) t += d[i] + " ";
  t += "<BR><BR>";
  x = Math.floor((N + 1) / 2); k = 2;
  for(i = 1; i <= N; i++)
  {
    for(j = 1; j < x; 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>";
    }
  }

// Rozbieramy kopiec

  for(i = N; i > 1; i--)
  {
    x = d[1]; d[1] = d[i]; d[i] = x;
    j = 1; k = 2;
    while(k < i)
    {
      if((k + 1 < i) && (d[k + 1] > d[k]))
        m = k + 1;
      else
        m = k;
      if(d[m] <= d[j]) break;
      x = d[j]; d[j] = d[m]; d[m] = x;
      j = m; k = j + j;
    }
  }

// Wyświetlamy wynik rozbioru kopca

  t += "<BR>";
  for(i = 1; i <= N; i++) t += d[i] + " ";

// Gotowe

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

</script> 

  </body>
</html>

 

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

Rozbiór kopca

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


.

 


Zobacz również na: Drzewo binarne | Tworzenie 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.