Heap Sort

 Heap Sort Algorithm

Heap sort is one of the sorting algorithms used to arrange a list of elements in order. Heap sort algorithm uses one of the tree concepts called Heap Tree. In this sorting algorithm, we use Max Heap to arrange list of elements in Descending order and Min Heap to arrange list elements in Ascending order.

What is a Heap ?

Heap is a special tree-based data structure which satisfies the following special heap properties:

1. 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 child nodes, heap is called a Max-Heap, and if the parent nodes are smaller than their child nodes, heap is called Min-Heap.

Step by Step Process

The Heap sort algorithm to arrange a list of elements in ascending order is performed using following steps...

• Step 1 - Construct a Binary Tree with given list of Elements.

• Step 2 - Transform the Binary Tree into Min Heap.

• Step 3 - Delete the root element from Min Heap using Heapify method.

• Step 4 - Put the deleted element into the Sorted list.

• Step 5 - Repeat the same until Min Heap becomes empty.

• Step 6 - Display the sorted list.

 

Example

Complexity

Complexity	Best Case	Average Case	Worst case
Time Complexity	Ω(n log (n))	θ(n log (n))	O(n log (n))
Space Complexity			O(1)

Algorithm

HEAP_SORT(ARR, N)

• Step 1: [Build Heap H]
  Repeat for i=0 to N-1
  CALL INSERT_HEAP(ARR, N, ARR[i])
  [END OF LOOP]

• Step 2: Repeatedly Delete the root element
  Repeat while N > 0
  CALL Delete_Heap(ARR,N,VAL)
  SET N = N+1
  [END OF LOOP]

• Step 3: END

C Program

#include<stdio.h>  

int temp;  

  

void heapify(int arr[], int size, int i)  

{  

int largest = i;    

int left = 2*i + 1;    

int right = 2*i + 2;    

  

if (left < size && arr[left] >arr[largest])  

largest = left;  

  

if (right < size && arr[right] > arr[largest])  

largest = right;  

  

if (largest != i)  

{  

temp = arr[i];  

    arr[i]= arr[largest];   

    arr[largest] = temp;  

heapify(arr, size, largest);  

}  

}  

  

void heapSort(int arr[], int size)  

{  

int i;  

for (i = size / 2 - 1; i >= 0; i--)  

heapify(arr, size, i);  

for (i=size-1; i>=0; i--)  

{  

temp = arr[0];  

    arr[0]= arr[i];   

    arr[i] = temp;  

heapify(arr, i, 0);  

}  

}  

  

void main()  

{  

int arr[] = {1, 10, 2, 3, 4, 1, 2, 100,23, 2};  

int i;  

int size = sizeof(arr)/sizeof(arr[0]);  

  

heapSort(arr, size);  

  

printf("printing sorted elements\n");  

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

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

}  

Output:

printing sorted elements 

 

1

1

2

2

2

3

4

10

23

100