Heap Sort Algorithm in Data Structure
 |
| Heap Sort |
Because it is in place and has no quadratic worst-case situations, heap sort is one of the best sorting methods. The heapsort algorithm is split into two parts:
- Creating a Heap of the unsorted list.
- Then a sorted array is created by repeatedly removing the largest/smallest element from the heap, and inserting it into the array. The heap is reconstructed after each removal.
What is a Heap?
- Heap is a special tree-based data structure, that satisfies the following special heap properties :
- Shape Property:
- Heap data structure is always a Complete Binary Tree, which means all levels of the tree are fully filled.
2. Heap Property:
- All nodes are either [greater than or equal to] or [less than or equal to] each of its children. If the parent nodes are greater than their children, the heap is called a Max-Heap, and if the parent nodes are smaller than their child nodes, the heap is called Min-Heap.
How Heap Sort Works
- The initial stage in heap sort is to establish a Heap data structure after receiving an unsorted list (Max-Heap or Min-Heap).
- Once the heap is constructed, the first element of the heap is either the largest or the smallest (depending on Max-Heap or Min-Heap), therefore we place it in our array.
- Then, using the remaining elements, we construct another heap and pick the first element of the heap to place into the array.
- We continue in this manner until we have a complete sorted list in our array.
- In the below algorithm, initially heapsort() function is called, which calls buildheap() to build heap, which inturn uses satisfyheap() to build the heap.
Sorting using Heap Sort Algorithm
/* Below program is written in C++ language */
void heapsort(int[], int);
void buildheap(int [], int);
void satisfyheap(int [], int, int);
void main()
{
int a[10], i, size;
cout << "Enter size of list"; // less than 10, because max size of array is 10
cin >> size;
cout << "Enter" << size << "elements";
for( i=0; i < size; i++)
{
cin >> a[i];
}
heapsort(a, size);
getch();
}
void heapsort(int a[], int length)
{
buildheap(a, length);
int heapsize, i, temp;
heapsize = length - 1;
for( i=heapsize; i >= 0; i--)
{
temp = a[0];
a[0] = a[heapsize];
a[heapsize] = temp;
heapsize--;
satisfyheap(a, 0, heapsize);
}
for( i=0; i < length; i++)
{
cout << "\t" << a[i];
}
}
void buildheap(int a[], int length)
{
int i, heapsize;
heapsize = length - 1;
for( i=(length/2); i >= 0; i--)
{
satisfyheap(a, i, heapsize);
}
}
void satisfyheap(int a[], int i, int heapsize)
{
int l, r, largest, temp;
l = 2*i;
r = 2*i + 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)
{
temp = a[i];
a[i] = a[largest];
a[largest] = temp;
satisfyheap(a, largest, heapsize);
}
}
Complexity Analysis of Heap Sort
Worst Case Time Complexity : O(n log n)
Best Case Time Complexity : O(n log n)
Average Time Complexity : O(n log n)
Space Complexity : O(n)
- Heapsort is not a Stable sort and requires a constant space for sorting a list.
- Heap Sort is very fast and is widely used for sorting.
Program for Heap Sort in C
#include <stdio.h>
int main()
{
int h[20],num,i,j,root,t,x;
printf("Enter number of elements :");
scanf("%d", &num);
printf("\nEnter the elements : ");
for (i = 0; i < num; i++)
scanf("%d", &h[i]);
// build max heap
for(i=0;i<num;i++)
{
x=i;
do
{
root = (x - 1) / 2;
if (h[root] < h[x])
{
t = h[root];
h[root] = h[x];
h[x] = t;
}
x = root;
} while (x != 0);
}
printf("Heap array formed is: ");
for (i = 0; i < num; i++)
printf("%d\t ", h[i]);
for (j = num - 1; j >= 0; j--)
{
t = h[0];
h[0] = h[j];
h[j] = t;
root = 0;
do
{
x = 2 * root + 1;
if ((h[x] < h[x + 1]) && x < j-1)
x++;
if (h[root]<h[x] && x<j)
{
t = h[root];
h[root] = h[x];
h[x] = t;
}
root = x;
} while (x < j);
}
printf("\nThe sorted array is : ");
for (i = 0; i < num; i++)
printf("\t %d", h[i]);
}
