Heap Sort implementation


This following code is my own. It implements the Heap Sort via arrays. The program is a menu driven one.

//Program to implement heapsort
//Implementing Heap first as a tree in form of array

#include<iostream>

using namespace std;

#define MAX 65
#define left(i) 2*i
#define right(i) 2*i+1

unsigned int heap[MAX];
unsigned int heap_len=1;

typedef unsigned int uint;

void xchange(uint *a1,uint *a2) {
uint tem;
tem=*a1;
*a1=*a2;
*a2=tem;
}

void maxHeapify(unsigned int x) {
if (x==0) return; //invalid argument for heap
uint l=left(x);
uint r=right(x);
uint large=x;
if (l<heap_len && heap[l]>heap[x])
large=l;
if (r<heap_len && heap[r]>heap[large])
large=r;
if (large!=x) {
xchange(heap+x,heap+large);
maxHeapify(large);
}
}

void heapify() {
for (uint i=heap_len-1;i>=1;–i) {
maxHeapify(i);
}
}

void addNode(unsigned int x) {
heap[heap_len]=x;
++heap_len;
//maxHeapify(1); not of use as addition at end of array
}

void show() {
for (int i=1;i<heap_len;++i)
cout<<heap[i]<<” “;
cout<<“\n”;
}

void heap_sort(bool ch) {
uint temp=ch?heap_len:1;
for (int i=heap_len-1;i>1;–i) {
xchange(heap+1,heap+i);
–heap_len;
maxHeapify(1);
}
heap_len=temp;
}
int main() {
heap[0]=0;
char ans;
cout<<“Heap Implementation…\n”;
while (1) {
cout<<“1.Add\n2.Show\n3.Heapify\n4.Heap Sort\n9.Exit\nEnter your choice.. “;
cin>>ans;
switch (ans) {
case ‘1’:
cout<<“Enter value to be added.. “;
uint temp;
cin>>temp;
addNode(temp);
break;

case ‘2’:
show();
break;

case ‘9’:
return(EXIT_SUCCESS);

case ‘4’:
cout<<“Do you want to keep the heap? <1/0>\n”;
bool ch;
cin>>ch;
heap_sort(ch);
break;

case ‘3’:
heapify();
break;

default:
cout<<“Enter correct choice..\n”;
break;
}
}
}

You can download a pdf version of the above code using the below link..

heap_sort

Advertisements
Explore posts in the same categories: C++

Tags: , , , ,

You can comment below, or link to this permanent URL from your own site.

2 Comments on “Heap Sort implementation”

  1. ronzii Says:

    You should use the [/source] tags to use the WordPress syntax highlighter 🙂 http://goo.gl/flRYH


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


%d bloggers like this: