The heap data structure is a vector which can be represented as an almost complete binary tree. Every vertice belongs to an element of the vector, which contains the values attached to the vertice. The tree is full, except maybe the last level, which is full from left to right, only up to a certain position. A vector V which represents a heap has two characteristics: length and heap dimension. The length represents the number of elements of the vector.The heap dimension represents the number of the elements of the heap memorized in the vector. The root of the tree is V[1]. Given an index i which correspond to a vertice, one can easily determine the index of the parent( [ i/2 ] ), of the left son( 2*i ) and of the right son( 2*i+1) :

For every index i which is not the root, the following heap property is valid:

V[ parent( i ) ]>= V[ i ],

which means that the value attached to a vertice is smaller or equal to the value attached to its parent.

This way, the biggest element from the heap is saved in the root and the values of the vertices of every sub-tree of a vertice are smaller or equal to the value of the vertice.

The sorting method has three procedures: rebuild, build and heapsort.

The "rebuild" procedure uses as entry data the vector V and an index i of the vector. When the procedure is called the sub-trees of the vertice i are heaps. But the element V[i] can be smaller than its descendents, so it isn't a heap. The procedure finds the position that V[i] should take so that the sub-tree which has in its root the value of the index i is a heap.

The "build" procedure can be used " bottom to top " for transforming the vector V [1..n] in a heap. Because all of the elements of the vector V [ ( [n/2]+1 )..n] are leaves, they can be considered heaps formed by one element. This way, the procedure "build" only has to deal with the rest of the elements and to do "rebuild" for every vertice it comes across to. The order the vertices are dealt with assures that the sub-trees having as root descensents of the vertice i form heaps before "rebuild" is executed for this vertices.

The "heapsort" procedure begins with the call of the procedure "build", in order to transorm the vector V[1..n] in a heap. Because the biggest element of the vector is attached to the root, this will have the last position in the ordered vector by its interchanging with V[n]. Then, excluding the n-th element of the vector and decreasing with one the length of the heap, the same algorithm is applied until the heap has only one element left.

 

Pascal Program:

var v:array[1..1000] of integer;

last,dim,i,j,k,l,m,n:integer;

f,g:text;

procedure readdata;

var i,j:integer;

begin

assign(f,'in.txt');

reset(f);

readln(f,n);

for i:=1 to n do

read(f,v[i]);

close(f);

end;

procedure rebuild(i:integer);

var aux,k,l,j:integer;

gasit:boolean;

begin

l:=0;

gasit:=false;

k:=0;

if 2*i<=dim then

if v[2*i]>v[i] then

begin k:=v[2*i];

l:=2*i;

gasit:=true;

end;

if 2*i+1<=dim then

if ((v[i]<v[2*i+1]) and (a[2*i+1]>k)) then

begin

k:=v[2*i+1];

l:=2*i+1;

gasit:=true;

end;

if gasit then

begin

v[l]:=v[i];

v[i]:=k;

rebuild(l);

end;

end;

procedure build;

var i,j,k:integer;

begin

for i:=last downto 1 do

rebuild(i);

end;

procedure heapsort;

var i,j,k,l:integer;

begin

dim:=n;

last:=dim div 2;

while dim>1 do

begin

build;

k:=v[1];

v[1]:=v[dim];

v[dim]:=k;

dim:=dim-1;

last:=dim div 2;

end;

end;

begin

readdata;

heapsort;

assign(g,'out.txt');

rewrite(g);

for i:=1 to n do

write(g,v[i], ' ');

close(g);

end.

 

C++ Program:

#include <iostream.h>
#include<fstream.h>
int v[1000],last,dim,i,j,k,l,m,n;
fstream f("in.txt",ios::in);

void readdata()
{
int i,j;
f>>n;
for (i=1;i<=n;i++)
{
f>>v[i];
}
}

void rebuild(int i)
{
int aux,k,l,j,gasit;
l=0;
gasit=0;
k=0;
if (2*i<=dim)
{
if (v[2*i]>v[i])
{
k=v[2*i];
l=2*i;
gasit=1;
}
}
if (2*i+1<=dim)
{
if ((v[i]<v[2*i+1])&&(v[2*i+1]>k))
{
k=v[2*i+1];
l=2*i+1;
gasit=1;
}
}
if (gasit==1)
{
v[l]=v[i];
v[i]=k;
rebuild(l);
}
}

void build()
{
int i;
for (i=last;i>=1;i--)
{
rebuild(i);
}
}

void heapsort()
{
int i,j,k,l;
dim=n;
last=dim/2;
while (dim>1)
{
build();
k=v[1];
v[1]=v[dim];
v[dim]=k;
dim-=1;
last=dim/2;
}
}

void main()
{
fstream g("out.txt",ios::out);
readdata();
heapsort();
for (i=1;i<=n; i++)
{
g<<v[i]<<" ";
}
f.close();
g.close();
}

 

Time:O(n log n)