Algorytmy Sortujące - Sortowanie przez kopcowanie

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.

do podrozdziału do strony

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 kroki K02...K05
K02:	j ← i; k ← j div 2
K03:	x ← d[i]
K04:	Dopóki (k > 0) ∧ (d[k] < x): wykonuj: d[j] ← d[k] j ← k k ← j 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

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.

do podrozdziału do strony

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

C++

// Konstruowanie kopca
//--------------------
// (C)2012 mgr Jerzy Wałaszek
// I Liceum Ogólnokształcące
// 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 && (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;
  system("pause");
  return 0;
}

Pascal

// Konstruowanie kopca
//--------------------
// (C)2012 mgr Jerzy Wałaszek
// I Liceum Ogólnokształcące
// 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)2012 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;
  writeln('Nacisnij Enter...');
  readln;
end.

Basic

' Konstruowanie kopca
'--------------------
' (C)2012 mgr Jerzy Wałaszek
' I Liceum Ogólnokształcące
' w Tarnowie

CONST N = 31 ' liczba elementów

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

RANDOMIZE
PRINT "   Tworzenie  kopca"
PRINT "----------------------"
PRINT "(C)2012 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 "Nacisnij Enter..."
SLEEP
END

Python (dodatek)

# Konstruowanie kopca
#--------------------
# (C)2012 mgr Jerzy Wałaszek
# I Liceum Ogólnokształcące
# w Tarnowie

import random

n = 31 # liczba elementów
d = [random.randrange(10) for i in range(n+1)]

print("   Tworzenie  kopca")
print("----------------------")
print("(C)2026 Jerzy Wałaszek")
print()

# Budujemy kopiec

for i in range(2,n+1):
    j = i
    k = j // 2
    x = d[i]
    while (k > 0) and (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 in range(1,n + 1):
    for j in range(1,x):
        print(" ",end="")
    print("%1d" % (d[i]),end="")
    for j in range(1,x+1):
        print(" ",end="")
    if i + 1 == k:
        k += k
        x //= 2
        print()

# Gotowe

print()
input("Naciśnij Enter...")

Wynik:

   Tworzenie  kopca
----------------------
(C)2026 Jerzy Wałaszek

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

Naciśnij Enter...

JavaScript

<html>
  <head>
  </head>
  <body>

<div style="overflow-x: auto;"
     align="center">
  <table
  border="0"
  cellpadding="4"
  style="border-collapse:
         collapse">
    <tr>
      <td nowrap>
        <form
        name="frm"
        style="text-align:
               center;
               background-color:
               #E7E7DA">
          <b>
          Tworzenie Kopca
          </b><br>
          &nbsp;&nbsp;(C)2026 mgr
          Jerzy Wałaszek
          &nbsp;&nbsp;<hr/>
          <input
          onclick="main()"
          value="Buduj Kopiec"
          name="B1"
          type="button">
          <hr/>
          <div id="out">.</div>
        </form>
      </td>
    </tr>
  </table>
</div>

<script language="javascript">

// Konstruowanie kopca
//--------------------
// (C)2005 mgr Jerzy Wałaszek
// I Liceum Ogólnokształcące
// w Tarnowie

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

  // Gotowe
  t = "<pre>" + t + "</pre>";
  document.getElementById("out")
  .innerHTML = t;
}

</script>

  </body>
</html>

do podrozdziału do strony

W rozdziale opisaliśmy bardzo prosty algorytm pozwalający konstruować kopiec. Algorytm ten posiada pesymistyczną klasę złożoności czasowej O(n logn) (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 log₂n. Ponieważ operację tę wykonujemy (n - 1) razy, to dostajemy górne oszacowanie właśnie O(n logn).

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.

do podrozdziału do strony

Na podstawie naszego algorytmu wyznacz maksymalną liczbę operacji porównań przy tworzeniu kopca z 31 elementów.
Nasz algorytm nie jest najefektywniejszym algorytmem do konstrukcji kopców. Poszukaj w sieci Internet informacji o algorytmie Floyda.
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.

do podrozdziału do 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

Kopiec (Heap)

Algorytm budowy kopca

Specyfikacja problemu

Dane wejściowe

Dane wyjściowe

Zmienne pomocnicze

Lista kroków

Schemat blokowy

Przykładowe programy

Podsumowanie

Zadania dla ambitnych

Sortowanie stogowe Heap Sort

Kopiec (Heap)

Algorytm budowy kopca

Specyfikacja problemu

Dane wejściowe

Dane wyjściowe

Zmienne pomocnicze

Lista kroków

Schemat blokowy

Przykładowe programy

Podsumowanie

Zadania dla ambitnych

Sortowanie stogowe
Heap Sort