// HeapSort.cpp : Defines the entry point for the console application.
#include <iostream>
#include <conio.h>
#include <malloc.h>
void Heap_Sort(int [], int, int);
void Max_Heapify(int [], int, int);
void Build_Max_Heap(int [], int);
void Heap_Sort(int A[], int length, int heapsize)
{
Build_Max_Heap(A, length);
for(int i = length; i >= 2; i--)
{
int temp;
temp = A[1];
A[1] = A[i];
A[i] = temp;
heapsize = heapsize-1;
Max_Heapify(A, 1, heapsize);
}
}
void Build_Max_Heap(int A[], int length)
{
int heapsize;
heapsize = length;
for(int i = (length/2); i >= 1; i--)
Max_Heapify(A, i, heapsize);
}
void Max_Heapify(int A[], int i, int heapsize)
{
int l, r, largest;
l = 2*i;
r = l+1;
if(l <= heapsize && A[l] > A[i])
largest = l;
else
largest = i;
if(r <= heapsize && A[r] > A[largest])
largest = r;
if(largest != i)
{
int temp;
temp = A[i];
A[i] = A[largest];
A[largest] = temp;
Max_Heapify(A, largest, heapsize);
}
}
int main()
{
int length,heapsize;
int A[10];
cout << "Enter the no of elements: ";
cin >> length;
heapsize =length;
//A = (int*) malloc(sizeof(int)*length);
cout << "\nEnter the elements :\n\n";
for(int i=1; i <= length; i++)
cin >> A[i];
Heap_Sort(A, length, heapsize);
cout << "\nSorted array is : ";
for(int i = 1; i <= length; i++)
cout << A[i] << " ";
getch();
return 0;
}
No comments:
Post a Comment