Algorithms
Topics:
Heap Sort

Heap Sort

Heap Sort

Heaps can be used in sorting an array. In max-heaps, maximum element will always be at the root. Heap Sort uses this property of heap to sort the array.

Consider an array $$ Arr $$ which is to be sorted using Heap Sort.

  • Initially build a max heap of elements in $$ Arr $$.
  • The root element, that is $$Arr[1]$$, will contain maximum element of $$ Arr $$. After that, swap this element with the last element of $$ Arr $$ and heapify the max heap excluding the last element which is already in its correct position and then decrease the length of heap by one.
  • Repeat the step 2, until all the elements are in their correct position.

Implementation:

    void heap_sort(int Arr[ ])
{ int heap_size = N;
build_maxheap(Arr); for(int i = N; i >= 2 ; i-- ) { swap|(Arr[ 1 ], Arr[ i ]); heap_size = heap_size - 1; max_heapify(Arr, 1, heap_size); } }

Complexity:
max_heapify has complexity $$ O(logN) $$, build_maxheap has complexity $$O(N)$$ and we run max_heapify $$N-1$$ times in heap_sort function, therefore complexity of heap_sort function is $$O(NlogN)$$.

Example:
In the diagram below,initially there is an unsorted array Arr having 6 elements and then max-heap will be built.

enter image description here

After building max-heap, the elements in the array $$Arr$$ will be:

enter image description here

Step 1: 8 is swapped with 5.
Step 2: 8 is disconnected from heap as 8 is in correct position now and.
Step 3: Max-heap is created and 7 is swapped with 3.
Step 4: 7 is disconnected from heap.
Step 5: Max heap is created and 5 is swapped with 1.
Step 6: 5 is disconnected from heap.
Step 7: Max heap is created and 4 is swapped with 3.
Step 8: 4 is disconnected from heap.
Step 9: Max heap is created and 3 is swapped with 1.
Step 10: 3 is disconnected.

enter image description here

After all the steps, we will get a sorted array.

enter image description here

Contributed by: Akash Sharma
Notifications
View All Notifications