Heap Sort Analysis

5 February 26, 2023

Hi everyone, inside this article we will see the concept about Heap Sort Analysis.

Heap Sort is a comparison-based sorting algorithm that uses a heap data structure to sort elements in ascending or descending order. It was invented by J.W.J. Williams in 1964 and is known for its efficiency and simplicity.

In a heap, the elements are arranged in a specific way such that the value of each parent node is larger (or smaller) than the values of its children. This is known as the heap property. In a max-heap, the root node contains the largest value in the heap, while in a min-heap, the root node contains the smallest value.

How Algorithm of Heap Sort works?

The Heap Sort algorithm involves the following steps:

Build a max-heap from the input array.
Swap the root node with the last element in the heap.
Remove the last element from the heap (which is now in its correct position).
Restore the heap property by performing a heapify operation on the root node.
Repeat steps 2-4 until all elements are sorted.

Here is the detailed algorithm for Heap Sort. Heap sort algorithm consists of two main steps:

Building a heap:
- Convert the array of elements into a max-heap, a complete binary tree where the value of each node is greater than or equal to the values of its children nodes (if any).
- The max-heap is built by starting from the last non-leaf node and recursively heapifying the subtrees downwards.
Extracting elements from the heap:
- Swap the root (the largest element) with the last element of the heap and reduce the size of the heap by one.
- Heapify the reduced heap to maintain the max-heap property.
- Repeat until the heap is empty.

The following is the pseudo-code for the Heap sort algorithm:

void heapSort(int arr[], int n) {
    // Build max heap
    for (int i = n / 2 - 1; i >= 0; i--)
        heapify(arr, n, i);
    // Extract elements from heap
    for (int i = n - 1; i > 0; i--) {
        swap(arr[0], arr[i]);
        heapify(arr, i, 0);
    }
}

void heapify(int arr[], int n, int i) {
    int largest = i; // Initialize largest as root
    int l = 2 * i + 1; // Left child
    int r = 2 * i + 2; // Right child

    // 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]);
        // Recursively heapify the affected sub-tree
        heapify(arr, n, largest);
    }
}

The heapSort function first builds a max heap by calling the heapify function for each non-leaf node in the array. Then, it extracts the maximum element (the root) from the heap and swaps it with the last element in the heap, reducing the size of the heap by one. Finally, it heapifies the reduced heap to maintain the max-heap property and repeats until the heap is empty. The heapify function takes an array arr, its size n, and an index i and recursively heapifies the sub-tree rooted at i in arr of size n.

What is meant by Heapify?

Heapify is a process of creating a heap from an array or a tree data structure. In the context of heap sort algorithm, heapify is used to build a max-heap or min-heap from an array of elements.

A max-heap is a binary tree where the value of each node is greater than or equal to the values of its children nodes. Similarly, a min-heap is a binary tree where the value of each node is less than or equal to the values of its children nodes.

Algorithm for Heapify

The algorithm for heapify is as follows:

Check if the current node has left and right children.
If it has left child and the value of the left child is greater (for max-heap) or smaller (for min-heap) than the value of the current node, set the largest (or smallest) to the index of the left child.
If it has right child and the value of the right child is greater (for max-heap) or smaller (for min-heap) than the value of the current node and the value of the right child is greater (for max-heap) or smaller (for min-heap) than the value of the left child, set the largest (or smallest) to the index of the right child.
If the largest (or smallest) is not the index of the current node, swap the values of the current node and the child node with the largest (or smallest) index.
Recursively call the heapify function on the child node with the largest (or smallest) index.

A Basic Example of Heap Sort with Steps

Consider the following unsorted array of integers:

[5, 3, 8, 4, 2]

Step 1:

Build a max-heap from the array. Start with the last non-leaf node of the binary tree and heapify it. The last non-leaf node of a binary tree is always at index (n/2)-1, where n is the total number of nodes.

After heapifying, we get:

Step 2:

Swap the root node with the last node of the array and remove the last node from the heap.

      8
     / \
    4   5
   / 
  3   
 /   
2     

Swap 8 and 2

      2
     / \
    4   5
   / 
  3   
 /   
8

Step 3:

Re-heapify the remaining nodes.

Step 4:

Repeat steps 2 and 3 until the heap is empty.

The resulting sorted array is [2, 3, 4, 5, 8].

Note that this example uses a max-heap to sort the array in ascending order. To sort the array in descending order, a min-heap should be used instead.

Example Code

// C++ program for implementation of Heap Sort

#include <iostream>
using namespace std;

// 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)
{

  // Initialize largest as root
  int largest = i;

  // left = 2*i + 1
  int l = 2 * i + 1;

  // right = 2*i + 2
  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]);

    // Recursively heapify the affected
    // sub-tree
    heapify(arr, N, largest);
  }
}

// Main function to do heap sort
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);
  }
}

// A utility 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";
}

// Driver's code
int main()
{
  int arr[] = {12, 11, 13, 5, 6, 7};
  int N = sizeof(arr) / sizeof(arr[0]);

  // Function call
  heapSort(arr, N);

  cout << "Sorted array is \n";
  printArray(arr, N);
}

The above program will output:

Sorted array is 
5 6 7 11 12 13

Complexity Analysis of Heap Sort

The time complexity of Heap Sort can be analyzed as follows:

Building a heap from an array of n elements requires O(n) time complexity, since we need to perform n/2 operations for heapify on average for each level of the heap.

Sorting the array requires n iterations of the following steps:

Swap the root (which is the largest element in a max-heap or the smallest in a min-heap) with the last element in the heap.
Decrement the heap size by 1.
Heapify the root to restore the heap property.

Since heapify takes O(log n) time complexity for each node, the time complexity of sorting step is O(n log n).

Therefore, the total time complexity of Heap Sort is O(n log n).

The space complexity of Heap Sort is O(1), since the sorting is performed in-place without requiring any additional memory.

Where is the Heap sort algorithm used?

Heap Sort is often used in embedded systems or other memory-constrained environments where additional memory usage is not desirable. It is also used in situations where stable sorting is not required and quick sort cannot be used due to its worst-case time complexity.

It is also used in implementing priority queues and other data structures that require efficient access to the largest or smallest element.

Advantages of Heap Sort:

Heap Sort has a worst-case time complexity of O(nlogn) which is faster than many other popular sorting algorithms like Bubble Sort and Insertion Sort.
Heap Sort has a space complexity of O(1), meaning that it sorts the array in-place and does not require any extra memory.
Heap Sort is stable and can be used to sort objects based on multiple keys.

Disadvantages of Heap Sort:

Heap Sort is not a stable sorting algorithm, meaning that the relative order of equal elements may not be preserved.
Heap Sort is slower than some other efficient sorting algorithms like Quick Sort and Merge Sort in most cases.
Heap Sort has a large constant factor, meaning that it may not be the best choice for small arrays or data sets.

We hope this article helped you to understand Heap Sort Analysis in a very detailed way.

Online Web Tutor invites you to try Skillshike! Learn CakePHP, Laravel, CodeIgniter, Node Js, MySQL, Authentication, RESTful Web Services, etc into a depth level. Master the Coding Skills to Become an Expert in PHP Web Development. So, Search your favourite course and enroll now.

If you liked this article, then please subscribe to our YouTube Channel for PHP & it’s framework, WordPress, Node Js video tutorials. You can also find us on Twitter and Facebook.