## 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..

*Related*

**Explore posts in the same categories:**C++

This entry was posted on October 15, 2010 at 11:32 PM and is filed under C++. You can subscribe via RSS 2.0 feed to this post's comments.

**Tags:** c++, heap, implementation, menu driven, sort

July 9, 2011 at 8:50 AM

You should use the [/source] tags to use the WordPress syntax highlighter ðŸ™‚ http://goo.gl/flRYH

July 9, 2011 at 2:01 PM

Ahh, I had been looking all over for it.. Used and [pre] tags to save at least the spaces..

Thanks for the info.. ðŸ™‚