© metamorworks / Shutterstock.com
When sorting an array of data, it’s crucial to familiarize yourself with sorting algorithms. In data structures, sorting is arranging data in a specific format based on a linear relationship among data items.
Sorting is essential as data search can be optimized at a very high level when data is sorted in a given format. Furthermore, sorting can represent data in a more readable format. We have a wide range of sorting algorithms, but in this article, we will examine what Heap sort is, and how to use it. Let’s get right into it!
What is Heap Sort: An Exact Definition
Heap sort is a well-known and efficient sorting algorithm. It’s a concept used to sort array data by eliminating elements one by one from the heap- a complete binary tree- part of the list, and then inserting them into the sorted part of the list.
Heap sort basically has two phases involved:
- Creating a heap, either max-heap or min-heap using elements of a specified array.
- Recursively deleting the root element of the heap built in the first phase.
How Does the Heap Sort Algorithm Work?
Here is how the heap sort algorithm is implemented:
- Create a max heap to store data from the unsorted list.
- Take out the largest value from the heap and insert it into a sorted list.
- Swap the root of the heap with the last element in the list, and then rebalance the heap.
- Once the max-heap is completely empty, return the sorted list.
Here is the algorithm
HeapSort(arr)
CreateMaxHeap(arr)
for i = length(arr) to 2
swap arr[1] with arr[i]
heap_size[arr] = heap_size[arr] ? 1
MaxHeapify(arr,1)
End
Let’s examine the steps a little more.
Step 1: Create a max-heap
CreateMaxHeap(arr)
heap_size(arr) = length(arr)
for i = length(arr)/2 to 1
MaxHeapify(arr,i)
End
In this algorithm, we will need to build out a max-heap. As we all know, in a max-heap, the largest value is the root value. Each parent node needs to have a larger value than its associated children.
Imagine we had the list below of unsorted values:
[14, 11, 2, 20, 3, 10, 3]
By placing our values into a max-heap data structure, this is how our list would look like:
[20, 11, 14, 2, 10, 5, 3]
We can present the above max-heap like this:
©History-Computer.com
Step 2: Take out the root of the heap
To sort out the data, we will repeatedly extract and eliminate the largest value from the heap until it’s empty. If we follow the principles of heaps, we can anticipate that the largest value will be located at the heap root.
After eliminating the largest value, we can’t just abandon the heap without a root, because it would result in two nodes being disconnected. Instead, we can exchange the root node with the last element in the heap. Since the last element has no children, it can be easily removed from the heap.
However, this step causes a major problem. By swapping the two elements, the root node now isn’t the largest in the heap. The heap will need to be restructured to ensure it’s balanced.
Step 3: Heapify down (restore the heap)
The root value not being the larger value, the heap principle has been violated as the parent must have a value greater than the children’s value.
However, there is a solution to this problem! We’ll need to heapify up, which involves adding a value to the end of the heap and working your way up the data structure until you find its appropriate position. To heapy down, you compare the new root value to its children, select the child with the greater value, and swap it with the root value. Work your way down the heap until it’s balanced.
©History-Computer.com
In the above example, you swap the original root value 20 with 3 – the right-most child. Having 3 as the new root, compare its value to its child value 14, and since it’s greater than 3, swap them to make 14 the new root. Next, compare 3 to its new child 5, and since 5 is greater than 3, swap them so that 5 is the new parent value. Since there are no other children to compare to 3, the heap is now balanced.
Step 4: Repeat
you‘ll need to repeat the procedure of swapping the root and the last element, taking out the largest value, and rebalancing the heap as long as the data structure contains a size greater than 1. When this criterion is met, you will have a sorted set of values.
Heap Sort Complexity
Time Complexity
Here is the time complexity of Heap Sort in the best case, average case, and worst case.
| Case | Time Complexity |
|---|---|
| Best Case | O(n log n) |
| Average Case | O(n log n) |
| Worst Case | O(n log n) |
- Best Case Complexity: Occurs when the array is already sorted, i.e no sorting required. O(n log n) is the best-case time complexity of heap sort.
- Average Case Complexity: It occurs when the elements in the array are not arranged in a properly ascending or descending order, resulting in a jumbled order. O(n log n) is the average case time complexity of heap sort.
- Worst Case Complexity: This happens when you need to sort the array elements in reverse order, meaning that if the elements are initially in descending order, you will need to sort them in ascending order. O(n log n) is the worst-case time complexity of heap sort.
Space Complexity
The space complexity of heap sort is O(1)
| Space Complexity | O(1) |
| Stable | N0 |
How Is the Heap Sort Algorithm Implemented?
Here’s how heap sort is implemented in Java programming language.
//To heapify a subtree. Here “i” is the root node index in arr[], and “x” is the heap size
public class HeapSort {
public static void sort(int[] arr) {
int x = arr.length;
//rearrange array (Build heap)
for (int i = x /2 – 1; i >= 0; i–)
heapify(arr, x, i);
// extract an element one by one from the heap
for (int i = x – 1; i > 0; i–) {
// move the initial root to the end
int temp = arr[0];
arr[0] = arr[i];
arr[i] = temp;
// call the max heapify function on the reduced heap
heapify(arr, i, 0);
}
}
static void heapify(int[] arr, int x, int i) {
int largest = i; //initialize largest as root
int l = 2 * i + 1; //left
int r = 2 * i + 2; // right
// if the left child is bigger than the root
if (l < x && arr[l] > arr[largest])
largest = l;
//if the right child is bigger than largest so far
if (r < x && arr[r] > arr[largest])
largest = r;
//if largest is not the root
if (largest != i){
int swap = arr[i];
arr[i] = arr[largest];
arr[largest] = swap;
//repeatedly heapify the affected sub-tree
heapify(arr, x, largest);
}
}
//a function to print an array of size x
static void printArray(int[]) {
int x = arr.length;
for (int i = 0; i < x; ++i)
System.out.print(arr[i] + ” “);
System.out.println();
}
// Driver code
public static void main (String[] args) {
int[] arr = { 13, 12, 14, 6, 7, 8 };
sort(arr);
System.out.println(“Sorted array is”);
printArray(arr);
}
}
Output
This is the sorted integer array in ascending order.
The sorted array is
6, 7, 8, 12, 13, 14
Pros and Cons of Heap Sort Algorithm
Pros
- Efficiency: This sorting algorithm is very efficient as the time required to sort a heap increases logarithmically, whereas in other algorithms time grows exponentially slower as the sorting items increase.
- Simplicity: Compared to other equally efficient algorithms, it’s simpler as it doesn’t use advanced computer science principles such as recursion.
- Memory Usage: Heap sort uses minimal memory to hold the initial list of items to be sorted, and no additional memory space is required to work.
Cons
- Expensive: Heap sorting is costly.
- Unstable: Heap sort is unreliable as it might rearrange the relevant order of elements.
- Inefficient: When dealing with highly complex data, Heap Sort is not very efficient.
Applications of Heap Sorting
You might have encountered Dijkstra’s algorithm, which uses heap sort to determine the shortest path. In Data Structure, heap sort allows the quick retrieval of either the smallest (shortest) or largest (longest) value. It has various applications, including determining the order in statistics, managing priority queues in Prim’s algorithm (also known as minimum spanning tree), and performing Huffman encoding or data compression.
Likewise, various operating systems use the Heap sort algorithm for jobs and process management, since it is based on a priority queue.
In a real-life scenario, heap sort can be applied in a SIM card store, where we have a long queue of customers waiting to be served. The customers who need to pay their bills can be prioritized, as their work takes minimal time. This approach will save time for many customers and avoid unnecessary delays, leading to a more efficient and satisfactory experience for all.
Wrapping Up
Every sorting or searching algorithm has its advantages and disadvantages, and Heap Sorting is no exception. However, the Heap Sort disadvantages are relatively minimal. For instance, It doesn’t require any additional memory space beyond what is already allocated.
Time is another factor. It is found that time complexity is determined using nlog(n), but the actual heap sort is less than O(nlog(n)). This is because extraction from the heap sort reduces the size, thus taking lesser time as the process goes on. Hence, Heap Sort is widely regarded as one of the “best” sorting algorithms in the realm of Data Structure for various reasons.
