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

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 in Data structure

Heap sort in Data structure

Heap sort in Data structure

Heap sort in Data structure

Heap sort in Data structure

Heap sort in Data structure

Heap sort in Data structure

Heap sort in Data structure

Heap sort program in c

#include<stdio.h>

void add(int []);
void adjust(int [],int);

void main()
{
int heap[30],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]);

//add a heap
heap[0]=n;
add(heap);

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

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

void add(int heap[])
{
int i,n;
n=heap[0]; //no. of elements
for(i=n/2;i>=1;i--)
adjust(heap,i);
}

void adjust(int heap[],int i)
{
int j,temp,n,flag=1;
n=heap[0];

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:

Heap sort

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)

Advantages of Heap sort

  • The Heap sort algorithm is very efficient.
  • Its memory usage is minimal.
  • Heap sort algorithm is simpler to understand than other equally efficient sorting algorithms.
  • Equally well in best, average and worst cases.

Disadvantages of Heap sort

  • Memory management is complex.
  • Heap sort is slower

Write A Comment