Data Structure

# Heap sort

Heapsort is a comparison-based sorting algorithm to create a sorted array (or list), and is part of the selection sort family.
Although somewhat slower in practice on most machines than a well-implemented quicksort, it has the advantage of a more favorable worst-case O(n log n) runtime.

### Algorithm

```
MAX-HEAPIFY(A,i)

1. l = LEFT(i)

2. r = RIGHT(i)

3. if l <= A.heap-size and A[l] > A[i]

4. 		largest = l

5. else largest = i

6. if r <= A.heap-size and A[r] > A[largest]

7. 		largest = r

8. if largest != i

9. 		exchange A[i] with A[largest]

10.		MAX-HEAPIFY(A,largest)

BUILD-MAX-HEAP(A)

1. A.heap-size = A.length

2. for i = [A.length/2] downto 1

3. 		MAX-HEAPIFY(A, i)

HEAPSORT(A)

1. BUILD-MAX-HEAP(A)

2. for i = A.length downto 2

3. 		exchange A[1] with A[i]

4. 		A.heap-size = A.heap-size - 1

5. 		MAX-HEAPIFY(A, 1)

```

### Heap sort Implementation

```
#include<stdio.h>

#include<conio.h>

void manage(int *, int);

void heapsort(int *, int, int);

void main()

{

int arr[20];

int i,j,size,tmp,k;

clrscr();

printf("\n\t\t\t------- Heap sorting method -------\n\n");

printf("Enter the number of elements to sort : ");

scanf("%d",&size);

printf("Enter The Element In Array\n");

for(i=1; i<=size; i++)

{

scanf("%d",&arr[i]);

manage(arr,i);

}

j=size;

for(i=1; i<=j; i++)

{

tmp=arr[1];

arr[1]=arr[size];

arr[size]=tmp;

size--;

heapsort(arr,1,size);

}

printf("\n\t\t\t------- Heap sorted elements -------\n\n");

size=j;

printf("Sorted Elements:\t");

for(i=1; i<=size; i++)

printf("%d\t ",arr[i]);

getch();

}

void manage(int *arr, int i)

{

int tmp;

tmp=arr[i];

while((i>1) && (arr[i/2]< tmp))

{

arr[i]=arr[i/2];

i=i/2;

}

arr[i]=tmp;

}

void heapsort(int *arr, int i, int size)

{

int tmp,j;

tmp=arr[i];

j=i*2;

while(j<=size)

{

if((j < size) && (arr[j] < arr[j+1]))

j++;

if(arr[j] < arr[j/2])

break;

arr[j/2]=arr[j];

j=j*2;

}

arr[j/2]=tmp;

}

```