Heap Sort Algorithm
Heap Sort Algorithm
Heap Sort is one of the best sorting methods being in-place and with no
quadratic worst-case running time. Heap sort involves building a Heap data
structure from the given array and then utilizing the Heap to sort the array.
You must be wondering, how converting an array of numbers into a heap
data structure will help in sorting the array. To understand this, let's start by
understanding what is a Heap.
?What is a Heap
Heap is a special tree-based data structure, that satisfies the following special
heap properties:
1. Shape Property: Heap data structure is always a Complete Binary
Tree, which means all levels of the tree are fully filled.
2. Heap Property: All nodes are either greater than or equal to or less
than or equal to each of its children. If the parent nodes are greater
than their child nodes, heap is called a Max-Heap, and if the parent
nodes are smaller than their child nodes, heap is called Min-Heap.
1
Heap Sort Algorithm
?How Heap Sort Works
Heap sort algorithm is divided into two basic parts:
Creating a Heap of the unsorted list/array.
Then a sorted array is created by repeatedly removing the
largest/smallest element from the heap, and inserting it into the array.
The heap is reconstructed after each removal.
Initially on receiving an unsorted list, the first step in heap sort is to create a
Heap data structure (Max-Heap or Min-Heap). Once heap is built, the first
element of the Heap is either largest or smallest (depending upon Max-Heap
or Min-Heap), so we put the first element of the heap in our array. Then we
again make heap using the remaining elements, to again pick the first
element of the heap and put it into the array. We keep on doing the same
repeatedly until we have the complete sorted list in our array.
In the below algorithm, initially heapsort() function is called, which
calls heapify() to build the heap.
2
Heap Sort Algorithm
Implementing Heap Sort Algorithm
Below we have a simple C++ program implementing the Heap sort
algorithm.
#include <iostream>
void heapify(int arr[], int n, int i)
{
int largest = i;
int l = 2*i + 1;
int r = 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)
{
swap(arr[i], arr[largest]);
heapify(arr, n, largest);
}
}
void heapSort(int arr[], int n)
{
// 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
swap(arr[0], arr[i]);
// call max heapify on the reduced heap
heapify(arr, i, 0);
}
}
/* function to print array of size n */
void printArray(int arr[], int n)
{
for (int i = 0; i < n; i++)
{
cout << arr[i] << " ";
}
cout << "\n";
}
int main()
{
int arr[] = {121, 10, 130, 57, 36, 17};
int n = sizeof(arr)/sizeof(arr[0]);
heapSort(arr, n);
cout << "Sorted array is \n";
printArray(arr, n);
3
Heap Sort Algorithm
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(1)
Comparing Heapsort with Other Efficient Sorting Algorithms
The following diagram shows the Ultimate Test results of Heapsort
compared to the ones of Quicksort and Merge Sort from the respective
articles:
Heapsort is slower than Quicksort by factor 3.6 and slower than Merge Sort
by factor 2.4 for randomly distributed input data. For sorted data, heapsort is
eight to nine times slower than quicksort and two times slower than Merge
Sort.
4
Heap Sort Algorithm
Heapsort vs. Quicksort
As shown in the previous section, Quicksort is usually much faster than
heapsort.
Due to the O(n²) worst-case time complexity of Quicksort, Heapsort is
sometimes preferred to Quicksort in practice.
As shown in the article about Quicksort, if the pivot element is chosen
appropriately, the worst case is unlikely to occur. Nevertheless, there is a
certain risk that a potential attacker with sufficient knowledge of the
Quicksort implementation used can exploit this knowledge to crash or freeze
an application with appropriately prepared input data.
Heapsort vs. Merge Sort
Merge Sort is also usually faster than Heapsort. Besides, unlike Heapsort,
Merge Sort is stable.
Heapsort has an advantage over Merge Sort in that it does not require
additional memory, while Merge Sort requires additional memory in the
order of O(n).
Summary
Heapsort is an efficient, unstable sorting algorithm with an average, best-
case, and worst-case time complexity of O(n log n).
Heapsort is significantly slower than Quicksort and Merge Sort, so Heapsort
is less commonly encountered in practice.
You will find more sorting algorithms in the overview of all sorting
algorithms and their characteristics in the first part of the article series.
If you liked the article, feel free to share it using one of the share buttons at
the end. Would you like to be informed by email when I publish a new
article? Then use the following form to sign up for my newsletter.
5
Heap Sort Algorithm
Reference
https://www.happycoders.eu/algorithms/heapsort/
https://www.studytonight.com/data-structures/heap-sort
