Złożoność czasowa:

• pesymistyczna: O(n * log n)
• średnia: O(n * log n)
  Złożoność pamięciowa: O(1)

Jest to metoda bardziej skomplikowana od poprzednich. Zrozumienie algorytmu HeapSort wymaga zaznajomienia się z pojęciem Kopca/Stogu. Budowa drzewa binarnego z elementów tablicy, którą mamy posortować wygląda następująco:
Zaczynamy od pierwszego elementu tablicy, który będzie korzeniem
Każdy następny i-ty element tablicy będzie miał co najwyżej dwa następniki o wyrazach odpowiednio: 2i oraz 2i+1
Łatwo stwierdzić, że dla każdego i-tego elementu (oprócz korzenia) numer elementu w tablicy, będącego jego poprzednikiem określa się wzorem: i div 2
Po zbudowaniu drzewa należy wykonać odpowiednie instrukcje, które zapewnią mu warunek kopca. Należy więc sprawdzać (poczynając od poprzednika ostatniego liścia schodząc w górę do korzenia) czy poprzednik jest mniejszy od następnika i jeżeli tak jest to zamienić je miejscami. Po wykonaniu tych czynności drzewo binarne zamieniło się w stóg. Z jego własności wynika, że w korzeniu znajduje się największy element. Korzystając z tego faktu możemy go pobrać na koniec tablicy wynikowej a na jego miejsce wstawić ostatni liść. Po pobraniu korzenia tablica źródłowa zmniejszyła się o 1 element a porządek kopca został zaburzony (nie wiadomo, czy ostatni liść będący teraz korzeniem jest rzeczywiście największym elementem). By przywrócić warunek stogu należy ponownie uporządkować jego elementy, tym razem jednak zaczynając od korzenia (ponieważ to on jest nowym elementem). Po przywróceniu porządku w kopcu możemy znów pobrać korzeń i wstawić go do tablicy wynikowej (tym razem na drugie miejsce od końca), wstawić na jego miejsce liść i zmniejszyć rozmiar tablicy źródłowej o 1. Tu pętla się zamyka. Wykonujemy te czynności aż do ostatniego korzenia. Po całkowitym wyczyszczeniu kopca w tablicy wynikowej będziemy mieli posortowane elementy z tablicy wejściowej. Aby zlikwidować drugą tablicę (co zwiększa złożoność pamięciową algorytmy) wystarczy w kolejnych krokach odkładać korzenie w tej samej tablicy, od końca zmniejszając jednocześnie zmienną, która odpowiada za liczbę elementów kopca. Po zmniejszeniu tej liczby algorytm nie będzie "widział" tylnej, posortowanej już części tablicy.

Implementacja (Delphi)

//Program pobrany ze strony www.algorytm.cad.pl
//Opracował Michał Knasiecki
unit Unit1;

interface

uses
  Windows, Messages, SysUtils, Classes, Graphics, Controls, Forms, Dialogs,
  StdCtrls;

type
  TForm1 = class(TForm)
    ListBox1: TListBox;
    Button1: TButton;
    ListBox2: TListBox;
    procedure Button1Click(Sender: TObject);
  end;
  
  Tablica = array[1..10]of integer;

var
  Form1: TForm1;
  A : Tablica; //Tablica źródłowa
  N : Integer; //Liczba elementów (w listbox1) do posortowania

implementation

{$R *.DFM}

procedure Sort_up(K : Integer); //Porządkowanie stogu od dołu
var 
  L, V : Integer;
begin
  V := A[k];
  L := K div 2;
  while A[L] < V do
  begin
    A[k] := A[L];
    K := L;
    L := L div 2;
  end;
  A[k] := V;
end;

procedure Insert(V : Integer); //Dodawanie elementu do stogu
begin
  N := N + 1;
  A[n] := V;
  Sort_up(N);
end;

procedure Sort_dn(K : Integer);  //Porządkowanie stogu od góry
label en;
var 
  J, V, P : Integer;
begin
  V := A[k];
  while (k <= (n div 2)) do
  begin
    j := 2*k;
    if (j <n ) and (a[j] < a[j+1]) then j:=j+1;
    if V< A[j] then
    begin
      P := A[k];
      A[k] := A[j];
      A[j] := P;
      k := j;
    end else 
    begin 
      A[k] := V;
      break;
    end;
  end;
end;


procedure Delete_root; //Usuwanie korzenia (największego elementu
var 
  P : Integer;
begin                  //i przenoszenie ostatniego liscia w miejsce korzenia
  P := A[n];//zapisanie ostatniego liscia
  A[n] := A[1]; //przeniesienie korzenia (największego elementu) do tablicy od końca
  Dec(n); //Po usunięciu korzenia tablica źródlowa zmniejsza się o 1
  A[1] := P; //Ostatni lisc staje się korzeniem
  Sort_dn(1); //Przywracanie porządku po zmianie korzenia
end;

procedure Build_heap;//porządkowanie stogu w dól zaczynając od 
poprzednika ostatniego liscia
var 
  i : Integer;
begin
  for i := (n div 2) downto 1 do Sort_dn(i);
end;


procedure Heap_sort; //Glówna procedura
var 
  M : Integer;
begin
  M := N;
  Build_Heap; //po zbudowaniu drzewa binarnego nalezy je uporządkowac tak, 
by spelnialo warunek stogu
  repeat
     Delete_root; //Gdy stóg jest gotowy można usuwac korzeń
  until N = 1;
  N := M;
end;


procedure TForm1.Button1Click(Sender: TObject);
var 
  I : Integer;
begin
  N := 10;
  for I := 1 to 10 do 
     A[i] := StrToInt(ListBox1.Items[i-1]); //pobieranie elementów z listboxa 
do tablicy wejsciowej

  Heap_sort; //sortowanie
  ListBox2.clear;
  for i := 1 to 10 do
    ListBox2.Items.Add(IntToStr(A[i]));//wypisywanie tablicy wynikowej w listbox
end;


end.

Heap.zip ( 5 kB )
Michał Knasiecki

Implementacja (Python)

Python posiada moduł heapq, który dostarcza gotowych funkcji do obsługi kopca. Możemy je wykorzystać do zaimplementowania sortowania.

from heapq import heappush, heappop

def heapsort(a):
    # budowanie kopca
    heap = []
    for i in a:
        heappush(heap, i)
    size = len(heap)
    # zdejmowanie kolejno najmniejszych elementow z kopca
    return [heappop(heap) for i in range(size)]

Implementacja (C/C++)

Wersje libc systemów z rodziny BSD (m. in. FreeBSD, OpenBSD, NetBSD i Mac OS X) posiadają implementację heapsort.

int
heapsort(void *base, size_t nmemb, size_t size, int (*compar)(const void *, const void *));