HeapSort:
Heap Sort is the sorting technique based on the interpretation of the given sequence of elements as a binary tree. For interpretation the principle given below has to be used.
1.If a given node is in position I then the position of the left child and the right child can be calculated using Left (L) = 2I and Right (R) = 2I + 1.
To check whether the right child exists or not, use the condition R ≤ N. If true, Right child exists otherwise not.
The last node of the tree is N/2. After this position tree has only leaves.
Principle: The Max heap has the greatest element in the root. Hence the element in the root node is pushed to the last position in the array and the remaining elements are converted into a max heap. The root node of this new max heap will be the second largest element and hence pushed to the last but one position in the array. This process is repeated till all the elements get sorted.
Algorithm:
Algorithm HeapSort(A)
BuildHeap(A)
for i ← length[A] down to 2
Swap(A[1], A[i])
heapsize[A] ← heapsize[A] − 1
Heapify(A, 1)
Procedure BuildHeap(A)
heapsize[A] ← length[A]
for i ← blength[A]/2c down to 1
Heapify(A, i)
Procedure Heapify(A, i)
l ← Left[i], r ← Right[i]
if l ≤ heapsize[A] ∧ A[l] > A[i]
largest ← l
else largest ← i
if r ≤ heapsize[A] ∧ A[r] > A[largest]
largest ← r
if largest =/ i
Swap(A[i], A[largest])
Heapify(A, largest)
The HEAP procedure is used to convert a tree into a heap. If this algorithm is applied to the interpreted tree, then the tree will gets converted to a max heap. In the above given HEAP algorithm, the element at the given node is compared with it parent and is swapped if the parent is less the element that we have considered the process gets repeated for the all the upper levels till the root node gets considered else we got some node whose parent is having greater value. The process has to be repeated for all the elements under consideration. After completion of a pass the largest element will be placed in the root of the heap. The largest element will gets pushed to the last position by exchanging the values. Since the heap property gets affected try to include it among N-1 elements so once again the largest among N-1 elements will be pushed to the root. The process has to be repeated till the total number of elements under consideration becomes one.
Example:
Given a list A with 8 elements:
42
|
23
|
74
|
11
|
65
|
58
|
94
|
36
|
The given list is first converted into a binary tree as shown
Binary tree:
Phase 1:
The rearranged tree elements after the first phase is
Phase:2
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)
Heap sort 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