Wygląd tablicy można tu schematycznie przedstawić następująco:
kopiec elementów do posortowania posortowana tablica
Tym razem kopiec kurczy się, a tablica przyrasta (od elementu ostatniego do pierwszego).
W tej fazie wykonuje się, jak w poprzedniej, n kroków (usuwanie elementu połączone z odtwarzaniem porządku kopcowego), każdy o koszcie logarytmicznym, zatem złożoność tej fazy to także O(n log n).
sort (T[1..n]) for i ← n downto 2 swap (T, T[i]) shift-down (T[1..i-1], 1)
Implementacja Powyższy pseudokod zaimplementowany w Pascalu będzie miał postać: {$APPTYPE CONSOLE} type TElem = integer; const Size = 13; var T:array[1..Size] of TElem = (4,1,3,2,16,9,10,14,8,7,99,78,55);
//procedura testowa sprawdzająca czy dane mają postać kopca function check_heap(n: integer): boolean; var i: integer; begin result:=false; for i:=2 to n do if T[i]>T[i div 2] then exit; result:=true; end;
procedure shift_down(n,i: integer); var j,k: integer; aux: TElem; begin k := i; repeat j := k; if (2*j <= n) and (T[2*j] > T[k]) then k := 2*j; if (2*j+1 <= n) and (T[2*j+1] > T[k]) then k := 2*j+1; aux:=T[j]; T[j]:=T[k]; T[k]:=aux; until j = k; end;
procedure build_heap; var i: integer; begin for i := Size div 2 downto 1 do shift_down (Size,i); end;