Heap sort


Heap sort

1. Example: 

2. Code DEV C++

#include <iostream>
#include <conio.h>
#define max 100
using namespace std ;

void InputArray(int A[],int n)
{
for(int i=0; i<n; i++)
{
cout<<"A["<<i<<"] =";
cin>>A[i];
}
}

void OutputArray(int A[],int n)
{
cout<<endl;
for(int i=0; i<n; i++)
cout<<A[i]<<"\t";
}

void Swap(int &a,int &b)
{
int temp = a; a = b; b = temp;
}

//swap node

void Heapify(int A[],int n, int i)
{
int Left = 2*(i+1)-1;
int Right = 2*(i+1);
int Largest;
if(Left<n && A[Left]>A[i])
Largest = Left;
else Largest = i;
if(Right<n && A[Right]>A[Largest])
Largest = Right; if(i!=Largest)
{
Swap(A[i],A[Largest]);
Heapify(A,n,Largest);
}
}

//creat Heap
void BuildHeap(int A[], int n)
{
for(int i = n/2-1; i>=0; i--)
Heapify(A,n,i);
}

void HeapSort(int A[], int n)
{
BuildHeap(A,n);
for(int i = n-1; i>0; i--){
Swap(A[0],A[i]);
Heapify(A,i,0);
}
}

int main() {
int A[max], n;

cout<<"N:";
cin>>n;
InputArray(A,n);
cout<<"\n Array:";
OutputArray(A,n);
cout<<"\n Heap Sort:";
HeapSort(A,n);
OutputArray(A,n);


getch();
return 0;
}

Result:


Advertisements