Heapsort – array based

May 3rd, 2011

In today’s algorithm review, I thought to cover the heapsort in C++ implementation. This is one of the well-known techniques though, in my opinion, it is harder to code than recursive quicksort. Non-recursive quicksort will be covered in next posts.

/*

================
Sifts item with index k down the heap
Parameters:
a         – the array to be sorted
n        – the size of the array
k        – index of the item to be sifted

Returns:    – none
Globals:    – none
================
*/

void siftDown(int * a, int n, int k){
      int l = k;
do{
k  = l;
int cl = 2 * k + 1;
int cr = cl + 1;

if (cl < n && a[cl] > a[k]){
l = cl;
}
if (cr < n && a[cr] > a[k] && a[cr] > a[cl]){
l = cr;
}

if (l != k){
int t = a[k];
a[k]=a[l];
a[l]=t;
}

} while (l != k);
}

/*
================
Reorganizes array so it satisfies heap property

Parameters:
a         – the array to be sorted
n        – the size of the array

Returns:    – none
Globals:    – none
================
*/

void heapify(int * a, int n){
for (int i = n / 2; i >= 0; i–){
siftDown(a,n,i);
}
}

/*
================
Sorts the array using heap

Parameters:
a         – the array to be sorted
n        – the size of the array

Returns:    – none
Globals:    – none
================
*/
void heapsort(int * a, int n){
heapify(a,n);
for (int i = n – 1; i > 1; i–){
int t = a[0];
a[0] = a[i];
a[i]=t;
siftDown(a,i-1,0);
}
}

Advertisements

~ by Monsi.Terdex on May 4, 2011.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

 
Normal Boy

Nothing out of the ordinary

Data Engineering Blog

Compare different philosophies, approaches and tools for Analytics.

%d bloggers like this: