Program to show Heap Sort Example in C++

#include

#include

int arr[20],n;

class heap

{

	private:

		int loc,num,par;

	public:

		void del_root(int);

		void create_heap();

		void display();

		void heap_sort();

		void insert(int,int);

};

void heap::insert(int num,int loc)

{

int par;

	while(loc>0)

	{

		par=(loc-1)/2;

			if(num<=arr[par])

			{

				arr[loc]=num;

				return;

			}

			arr[loc]=arr[par];

			loc=par;

	}

	arr[0]=num;

}

void heap::display()

{

	int i;

	for(i=0;i	{

	cout<	}

}

void heap::create_heap()

{

	int i;

	for(i=0;i	{

		insert(arr[i],i);

	}

}

void heap::heap_sort()

{

	int last;

	for(last=n-1;last>0;last--)

	{

		del_root(last);

	}

}

void heap::del_root(int last)

{

	int left,right,i,temp;

	i=0;

	temp=arr[i];

	arr[i]=arr[last];

	arr[last]=temp;

	left=2*i+1;

	right=2*i+2;

	while(right	{

		if(arr[i]<=arr[left]&&arr[i]>=arr[right])

			return;

		if(arr[right]<=arr[left])

		{

			temp=arr[i];

			arr[i]=arr[left];

			arr[left]=temp;

			i=left;

		}

		else

		{

			temp=arr[i];

			arr[i]=arr[right];

			arr[right]=temp;

			i=right;

		}

		left=2*i+1;

		right=2*i+2;

	}

	if(left==last-1 && arr[i]	{

		temp=arr[i];

		arr[i]=arr[left];

		arr[left]=temp;

	}

}



void main()

{

	int i;

	clrscr();

	cout<	cin>>n;

	for(i=0;i	{

		cout<		cin>>arr[i];

	}

	cout<	heap h;

	h.display();

	h.create_heap();

	cout<	h.display();

	h.heap_sort();

	cout<<"Sorted list is:";

	h.display();

	getch();

}

Related Links :