Algorytmy Sortujące - Sortowanie przez kopcowanie

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

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.
Jeśli jest to konieczne, przywróć warunek kopca idąc od korzenia w dół.
Kontynuuj od kroku 1, aż kopiec będzie pusty.

Przykład:

Dokonaj rozbioru następującego kopca:

obrazek

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.

Na początek: podrozdziału strony

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 kroki K02...K08
K02:	d[1] ↔ d[i]
K03:	j ← 1; k ← 2
K04:	Dopóki (k < i): wykonuj kroki K05...K08
K05:	Jeżeli (k + 1 < i) ∧ (d[k + 1] > d[k]), to m ← k + 1 inaczej m ← k
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:	j ← m; k ← j + j
K09:	Zakończ

Schemat blokowy

obrazek

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 log₂n razy. Daje to zatem górne oszacowanie O(n logn) 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.

Na początek: podrozdziału strony

C++

// 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;
}

Pascal

// 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.

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>

Wynik:

    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

Na początek: podrozdziału strony

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.

Sortowanie stogowe
Heap Sort

Algorytm rozbioru kopca

Opis algorytmu

Specyfikacja problemu

Dane wejściowe

Dane wyjściowe

Zmienne pomocnicze

Lista kroków

Schemat blokowy

Przykładowe programy

Rozbiór kopca

Sortowanie stogowe Heap Sort

Algorytm rozbioru kopca

Opis algorytmu

Specyfikacja problemu

Dane wejściowe

Dane wyjściowe

Zmienne pomocnicze

Lista kroków

Schemat blokowy

Przykładowe programy

Rozbiór kopca

Sortowanie stogowe
Heap Sort