Heapsort is an efficient sorting algorithm that works by creating a max-heap data structure from an array of elements. The algorithm then uses the heap structure to sort the elements in the array. Heapsort is often used in practice because of its lower time complexity and its ability to sort both ascending and descending order. In this article, we will discuss the Heapsort algorithm in detail, its time complexity, space complexity, and provide a Java implementation of the algorithm.
What is Heapsort?
Heapsort is an efficient sorting algorithm that works by creating a max-heap data structure from an array of elements. A max-heap is a complete binary tree in which each node is greater than its children. The algorithm then uses the heap structure to sort the elements in the array. Heapsort is often used in practice because of its lower time complexity and its ability to sort both ascending and descending order.
How does Heapsort Work?
Heapsort works by first creating a max-heap from the array of elements. The algorithm then starts by selecting the root node of the max-heap, which is the highest value in the array. The root node is then swapped with the last element in the array and the heap is then reduced by one. This process is repeated until all the elements in the array have been sorted.
Heapsort Algorithm
The following algorithm is used to sort an array of elements using Heapsort:
- Create a max-heap from the array of elements.
- Select the root node of the max-heap, which is the highest value in the array.
- Swap the root node with the last element in the array.
- Reduce the size of the heap by one.
- Repeat steps 2-4 until all the elements in the array have been sorted.
Java Implementation
The following Java program implements the Heapsort algorithm:
public class HeapSort
{
public void sort(int arr[])
{
int n = arr.length;
// Build heap (rearrange array)
for (int i = n / 2 - 1; i >= 0; i--)
heapify(arr, n, i);
// One by one extract an element from heap
for (int i=n-1; i>=0; i--)
{
// Move current root to end
int temp = arr[0];
arr[0] = arr[i];
arr[i] = temp;
// call max heapify on the reduced heap
heapify(arr, i, 0);
}
}
// To heapify a subtree rooted with node i which is
// an index in arr[]. n is size of heap
void heapify(int arr[], int n, int i)
{
int largest = i; // Initialize largest as root
int l = 2*i + 1; // left = 2*i + 1
int r = 2*i + 2; // right = 2*i + 2
// If left child is larger than root
if (l < n && arr[l] > arr[largest])
largest = l;
// If right child is larger than largest so far
if (r < n && arr[r] > arr[largest])
largest = r;
// 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);
}
}
/* A utility function to print array of size n */
static void printArray(int arr[])
{
int n = arr.length;
for (int i=0; i<n; ++i)
System.out.print(arr[i]+" ");
System.out.println();
}
// Driver program
public static void main(String args[])
{
int arr[] = {12, 11, 13, 5, 6, 7};
int n = arr.length;
HeapSort ob = new HeapSort();
ob.sort(arr);
System.out.println("Sorted array is");
printArray(arr);
}
}
Time and Space Complexity of Heapsort
The time complexity of Heapsort is O(n log n). This means that the algorithm takes O(n log n) time to sort an array of n elements. The worst case time complexity of Heapsort is also O(n log n).
The space complexity of the Heapsort algorithm is O(1). This means that the algorithm does not require any additional memory for its operation and thus, has a constant space complexity of O(1).
Conclusion
In conclusion, Heapsort is an efficient sorting algorithm that works by creating a max-heap data structure from an array of elements. The algorithm then uses the heap structure to sort the elements in the array. Heapsort is often used in practice because of its lower time complexity and its ability to sort both ascending and descending order. The time complexity of Heapsort is O(n log n) and the space complexity is O(1).
Exercises
Write a Java program to implement the Heapsort algorithm on an array of integers.
public class HeapSort
{
public void sort(int arr[])
{
int n = arr.length;
// Build heap (rearrange array)
for (int i = n / 2 - 1; i >= 0; i--)
heapify(arr, n, i);
// One by one extract an element from heap
for (int i=n-1; i>=0; i--)
{
// Move current root to end
int temp = arr[0];
arr[0] = arr[i];
arr[i] = temp;
// call max heapify on the reduced heap
heapify(arr, i, 0);
}
}
// To heapify a subtree rooted with node i which is
// an index in arr[]. n is size of heap
void heapify(int arr[], int n, int i)
{
int largest = i; // Initialize largest as root
int l = 2*i + 1; // left = 2*i + 1
int r = 2*i + 2; // right = 2*i + 2
// If left child is larger than root
if (l < n && arr[l] > arr[largest])
largest = l;
// If right child is larger than largest so far
if (r < n && arr[r] > arr[largest])
largest = r;
// 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);
}
}
/* A utility function to print array of size n */
static void printArray(int arr[])
{
int n = arr.length;
for (int i=0; i<n; ++i)
System.out.print(arr[i]+" ");
System.out.println();
}
// Driver program
public static void main(String args[])
{
int arr[] = {12, 11, 13, 5, 6, 7};
int n = arr.length;
HeapSort ob = new HeapSort();
ob.sort(arr);
System.out.println("Sorted array is");
printArray(arr);
}
}
What is the time complexity of Heapsort?
The time complexity of Heapsort is O(n log n). This means that the algorithm takes O(n log n) time to sort an array of n elements. The worst case time complexity of Heapsort is also O(n log n).
What is the space complexity of Heapsort?
The space complexity of the Heapsort algorithm is O(1). This means that the algorithm does not require any additional memory for its operation and thus, has a constant space complexity of O(1).
Write a Java program to create a max-heap from an array of elements.
public class Heap
{
public void buildMaxHeap(int arr[])
{
int n = arr.length;
// Build heap (rearrange array)
for (int i = n / 2 - 1; i >= 0; i--)
heapify(arr, n, i);
}
// To heapify a subtree rooted with node i which is
// an index in arr[]. n is size of heap
void heapify(int arr[], int n, int i)
{
int largest = i; // Initialize largest as root
int l = 2*i + 1; // left = 2*i + 1
int r = 2*i + 2; // right = 2*i + 2
// If left child is larger than root
if (l < n && arr[l] > arr[largest])
largest = l;
// If right child is larger than largest so far
if (r < n && arr[r] > arr[largest])
largest = r;
// 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);
}
}
/* A utility function to print array of size n */
static void printArray(int arr[])
{
int n = arr.length;
for (int i=0; i<n; ++i)
System.out.print(arr[i]+" ");
System.out.println();
}
// Driver program
public static void main(String args[])
{
int arr[] = {12, 11, 13, 5, 6, 7};
int n = arr.length;
Heap ob = new Heap();
ob.buildMaxHeap(arr);
System.out.println("Max Heap is");
printArray(arr);
}
}
Write a Java program to swap the root node of a max-heap with the last element in the array.
public class Heap
{
// To swap the root node of a max-heap with the last element in the array
public void swapRootNode(int arr[], int n)
{
int temp = arr[0];
arr[0] = arr[n-1];
arr[n-1] = temp;
}
/* A utility function to print array of size n */
static void printArray(int arr[])
{
int n = arr.length;
for (int i=0; i<n; ++i)
System.out.print(arr[i]+" ");
System.out.println();
}
// Driver program
public static void main(String args[])
{
int arr[] = {12, 11, 13, 5, 6, 7};
int n = arr.length;
Heap ob = new Heap();
ob.swapRootNode(arr, n);
System.out.println("Array after swapping root node is");
printArray(arr);
}
}