Heap sort in Data structure is a sorting technique which is based on the comparison.

Page Contents

## Heap sort

What is Heap sort?
Heap sort in Data structure is a much more efficient version of selection sort it also works by determining the largest element of the list, placing that at the end (or beginning) of the list then continuing with the rest of all list, by accomplishes this task efficiently by using a data structure called HEAP.

This is a special type of binary tree once the data list has been made into a heap the root node is generated to be a large or smaller element when it is removed and placed at end of the list the heap is rearranged so the largest element remaining moves to root.

### Heap sort technique

Heap sort in Data structure is similar to selection sort where we first find the maximum element and place the maximum element at the end. We repeat the same process for the remaining element.
Heap sort algorithm is based on the creation of max heap (to sort in ascending order). In a max heap, the largest element is root and all child are less than root.
It is based on the deletion of the root element and readjustment of the heap to restore the heap property
A process is carried out repeatedly to generate element in descending order.

### Heap sort algorithm

1. Create a new node at the end of the heap.
2. Assign a new value to the node.
3. Compare the value of this child node with its parent.
4. If the value of a parent is less than a child, then swap them.
5. Repeat step 3 & 4 until Heap property holds.

### Heap sort example        ### Heap sort program in c

```#include<stdio.h>

void main()
{
int heap,n,i,last,temp;
printf("Enter no. of elements:");
scanf("%d",&n);
printf("\nEnter elements:");
for(i=1;i<=n;i++)
scanf("%d",&heap[i]);

heap=n;

//sorting
while(heap > 1)
{
//swap heap and heap[last]
last=heap;
temp=heap;
heap=heap[last];
heap[last]=temp;
heap--;
}

//print sorted data
printf("\nArray after sorting:\n");
for(i=1;i<=n;i++)
printf("%d ",heap[i]);
}

{
int i,n;
n=heap; //no. of elements
for(i=n/2;i>=1;i--)
}

{
int j,temp,n,flag=1;
n=heap;

while(2*i<=n && flag==1)
{
j=2*i; //j points to left child
if(j+1<=n && heap[j+1] > heap[j])
j=j+1;
if(heap[i] > heap[j])
flag=0;
else
{
temp=heap[i];
heap[i]=heap[j];
heap[j]=temp;
i=j;
}
}
}```

#### Output: ### The complexity of Heap sort

The time complexity for Heap sort
The worst-case and average-case complexity: O(nlogn).
The Best case complexity of Heap sort: O(nlogn).
Space complexity for Heap sort: O(n)