Heap sort is a comparison-based sorting algorithm that uses a binary heap data structure to sort elements. It’s an in-place algorithm that has an average and worst-case time complexity of O(n log n), making it an efficient sorting algorithm for large dat
Various Sorting Algorithm
- Bubble sort
- Modified Bubble Sort
- Selection sort
- Insertion sort
- Quick sort
- Merge sort
- Heap sort
Heap Sort
0 1 2 3 4 5 6 7 8 9
78 21 60 37 88 42 18 51 25 10
H 0 1 2 3 4 5 6 7 8 9
10 18 21 25 37 42 51 60 79 88
temp[18]
The basic idea behind heap sort involves the following steps:
- Build a max-heap (or min-heap for descending order) from the array elements.
- Swap the first element of the heap with the last element.
- Reduce the size of the heap by 1.
- Heapify the root of the heap.
- Repeat steps 2-4 until the heap size is 1.
Algorithm
Heap sort is a comparison-based sorting algorithm that leverages the properties of a binary heap. It involves two main stages: creating a heap out of the array and then repeatedly removing the largest element from the heap and placing it at the end of the array. The steps for the heap sort algorithm are as follows:
- Build the Max Heap: Convert the array into a max heap, a complete binary tree where each parent node is greater than or equal to its children. This step ensures that the largest element is at the root.
- Heapify the Root: Swap the root element (largest) with the last element of the heap and decrease the size of the heap by one. Heapify the new root element to maintain the heap property.
- Repeat Heapify: Repeat the heapifying process for the reduced heap until the heap size is 1.
- Final Sorted Array: The array elements are now sorted in ascending order.
Here is a step-by-step breakdown of the algorithm:
heapSort(array)
buildMaxHeap(array)
// Build a max heap from the input data
for i = n to 1 do
swap(array[0], array[i])
// Move current root to end
heapify(array, i, 0)
// Call max heapify on the reduced heap
Working Of Heap Sort Algorithm
Heap sort is a comparison-based sorting algorithm that sorts an array by first creating a binary heap from the elements and then repeatedly extracting the maximum element from the heap and placing it at the end of the array. Here’s a step-by-step explanation of how heap sort works with an example and corresponding diagrams:
Let’s consider an example array: [12, 11, 13, 5, 6, 7]
- Build Max-Heap: Convert the array into a max-heap. The heap representation of the array would be as follows:
13
/ \
11 7
/ \ /
5 6 12
- Heapify and Sort: Swap the root element with the last element of the heap and reduce the heap size by 1. Heapify the root to maintain the heap property. This step involves repeatedly swapping elements to move the next maximum element to the end of the array. The process is illustrated step by step below:
Step 1: Initial Max-Heap
13
/ \
11 7
/ \ /
5 6 12
Step 2: After
swapping 13 and 12
12
/ \
11 7
/ \ /
5 6 13
Step 3: After heapify and
swapping 12 and 7
11
/ \
7 6
/ \ /
5 12 13
Step 4: After heapify
and swapping 11 and 5
7
/ \
5 6
/ \ /
11 12 13
Step 5: After heapify
and swapping 7 and 6
6
/ \
5 7
/ \ /
11 12 13
Step 6: After heapify
and swapping 6 and 5
5
/ \
6 7
/ \ /
11 12 13
- Final Sorted Array: After completing the heapifying process, the array is sorted in ascending order:
[5, 6, 7, 11, 12, 13].
Heap Sort Complexity
The time complexity of heap sort in different cases along with its space complexity is as follows:
| Case | Time Complexity |
|---|---|
| Best Case | O(n logn) |
| Average Case | O(n log n) |
| Worst Case | O(n log n) |
- Best Case Complexity – It occurs when there is no sorting required, i.e. the array is already sorted. The best-case time complexity of heap sort is O(n logn).
- Average Case Complexity – It occurs when the array elements are in jumbled order that is not properly ascending and not properly descending. The average case time complexity of heap sort is O(n log n).
- Worst Case Complexity – It occurs when the array elements are required to be sorted in reverse order. That means suppose you have to sort the array elements in ascending order, but its elements are in descending order. The worst-case time complexity of heap sort is O(n log n).
Implementation of Heapsort
Certainly! Below is an implementation of the heap sort algorithm in Python along with an example:
import java.util.Arrays;
public class HeapSort {
public void sort(int arr[]) {
int n = arr.length;
// Build max heap
for (int i = n / 2 - 1; i >= 0; i--)
heapify(arr, n, i);
// Heap sort
for (int i = n - 1; i > 0; i--) {
// Swap root with end
int temp = arr[0];
arr[0] = arr[i];
arr[i] = temp;
// Heapify the reduced heap
heapify(arr, i, 0);
}
}
void heapify(int arr[], int n, int i) {
int largest = i;
// Initialize largest as root
int left = 2 * i + 1; // Left child
int right = 2 * i + 2; // Right child
// If left child is larger than root
if (left < n && arr[left] > arr[largest])
largest = left;
// If right child is
larger than largest so far
if (right < n && arr[right] > arr[largest])
largest = right;
// If largest is not root
if (largest != i) {
int swap = arr[i];
arr[i] = arr[largest];
arr[largest] = swap;
// Recursively heapify
the affected sub-tree
heapify(arr, n, largest);
}
}
// Example usage
public static void main(String args[]) {
int arr[] = {12, 11, 13, 5, 6, 7};
System.out.println("Original array: "
+ Arrays.toString(arr));
HeapSort ob = new HeapSort();
ob.sort(arr);
System.out.println("Sorted array: "
+ Arrays.toString(arr));
}
}
