Heap Sort: Algorithm, Time & Space Complexity

Ever thought about how to sort data without using the extra space and still keep the performance solid? What if we told you there is a method that always gives you O(n log n) time, no matter what the input looks like? Understand Heap Sort, a powerful algorithm that turns your array into a heap and keeps pulling out the biggest elements.

In this article, we will learn heap sort in detail.

Table of Contents:

• What is Heap?
• What is Heapify?
• What is Heap Sort?
• Algorithm of Heap Sort
• Inserting an Element into Heap
• Removing the Smallest Element from Heap
• Removing the Largest Element from Heap
• Time and Space Complexity of Heap Sort
• Advantages of Heap Sort
• Disadvantages of Heap Sort
• Real World Applications of Heap Sort
• Conclusion

What is Heap?

A Heap is a type of binary tree that is mainly used to store data in a specific order so that we can access the largest or smallest element. It is like a priority queue where the highest or lowest priority element always stays at the top, which can be removed or used first.

• A heap is always a complete binary tree, i.e., all levels are completely filled except the last one, which is filled from left to right.
• There are 2 types of Heaps,
  • Max-Heap: The largest element is present at the root, i.e., every parent node is greater than or equal to its children.
  • Min-Heap: The smallest element is present at the root, i.e., every parent node is less than or equal to its children.

What is Heapify?

Heaps are usually implemented using arrays, which makes it easier to manage the tree in memory and apply operations like insert or delete efficiently. Whenever we insert or remove an element from the Heap, the heap rearranges itself to maintain the heap property. This process is called heapify. Insertions in the Heap are performed at the end of the tree, i.e., at the last level, in the order from left to right.

What is Heap Sort?

Heap Sort is a sorting technique that uses the heap data structure, particularly a max-heap or min-heap. A max-heap ensures that the largest element is always present at the root, which is used for sorting in ascending order, and vice versa.

Heap Sort is an

• In-place sorting technique that uses a constant space, with no need for extra arrays.
• Unstable sorting technique, i.e., equal elements do not retain their original order.

Algorithm of Heap Sort

heapSort(arr):
    n = length(arr)

    // Step 1: Build Max-Heap
    for i from (n / 2) - 1 downto 0:
        heapify(arr, n, i)

    // Step 2: Extract elements one by one from heap
    for i from n - 1 downto 1:
        swap(arr[0], arr[i])         // Move current root to end
        heapify(arr, i, 0)           // Heapify the reduced heap

heapify(arr, heapSize, i):
    largest = i
    left = 2 * i + 1
    right = 2 * i + 2

    if left < heapSize and arr[left] > arr[largest]:
        largest = left

    if right < heapSize and arr[right] > arr[largest]:
        largest = right

    if largest != i:
        swap(arr[i], arr[largest])
        heapify(arr, heapSize, largest)

Dry-Run of the Heap Sort Algorithm

Now, let us discuss the above algorithm with the help of an example.

Let the Array and its tree representation be

Step 1: Build a Max-Heap

Start heapifying from the last non-leaf node at index 1, then move to the root.

Heapify at index 1:

Compare 10, 5, and 1. The heap property is already satisfied, hence, no change is needed.

Heapify at index 0:

Compare the elements 4, 10, and 3. Then swap the elements 4 and 10.

Tree:

  10
 /  \
 5   3
/ \
4 1

Array: [10, 5, 3, 4, 1]

Step 2: Extract Maximum & Heapify

Iteration 1: Swap the root element (10) with the last element (1)

Array = [1, 5, 3, 4, 10]

Compare elements 1, 5, and 3, then swap elements 1 and 5. Then compare 1, 4, swap 1 and 4

Tree:

  5
 / \
 4  3
/
1

Array: [5, 4, 3, 1, 10]

Iteration 2: Swap root (5) with index 3 (1)

Array = [1, 4, 3, 5, 10]

Compare elements 1, 4, and 3, then swap 1 and 4

 4
/ \
1 3

Array: [4, 1, 3, 5, 10]

Iteration 3: Swap root (4) with index 2 (3)

Array = [3, 1, 4, 5, 10]

Compare elements 3 and 1, as the heap property is already satisfied; hence, no change is needed.

  3
 /
1

Array: [3, 1, 4, 5, 10]

Iteration 4: Swap root (3) with index 1 (1)

After swapping the elements, the array will become

Array = [1, 3, 4, 5, 10]

Since only one element is left, hence, no further heapifying is required

As all the elements of the array are in sorted order, no further swapping is needed; hence, we achieved our goal.

Above is the final sorted array, and its tree representation.

Heap Sort Code in Java

Output:

Explanation:

In the above Java code, the heapSortjava() method sorts the array using the Heap Sort algorithm. It first builds a Max-Heap and then finds the largest element to sort the array. The heapifyjava() method makes sure that a part of the array is in the Max-Heap property by comparing a node with its children and swapping them when needed. The printArrayjava() method prints the elements of the array in one line, which is used before and after the sorting is done.

Heap Sort Code in C++

Output:

Explanation:

In the above C++ code, the heapSortcpp() method sorts the array using the Heap Sort algorithm. It first builds a Max-Heap and then finds the largest element to sort the array. The heapifycpp() method makes sure that a part of the array is in the Max-Heap property by comparing a node with its children and swapping them when needed. The printArraycpp() method prints the elements of the array in one line, which is used before and after the sorting is done.

Heap Sort Code in Python

Output:

Explanation:

In the above Python code, the heap_sort_python() is the main sorting method. It first turns the array into a Max-Heap, then swaps the largest element with the last item. The heapify_python() method ensures that a subtree rooted at index i satisfies the Max-Heap property by comparing it with its children and swapping. The print_array_python() method prints the array elements.

Inserting an Element in Heap

When you insert a new element into the Heap, you want to maintain the heap property of the tree. The heap uses the following steps to maintain the order. A Max-Heap or a Min-Heap does not guarantee the structure of the tree in a sorted way, it only guarantees that the largest or the smallest element will be present at the root, not that the entire array is in order.

A Max-Heap guarantees that the parent node is always greater than or equal to its child nodes. A Min-Heap guarantees that each parent node is less than or equal to its children.

Steps to Insert a New Item in a Heap

Step 1: Add the New Element at the End, then place the new item at the next available position in the heap tree, which maintains the structure of the complete binary tree.

Step 2: Heapify up, then compare the inserted element in the tree with its parent. If the new element is larger than its parent in the Max-Heap, swap the elements. And continue this process until the heap property is followed or the element reaches the root.

Now, let us discuss the code for the Insertion of the element in the Heap Sort.

Insertion Code of Heap Sort in Java

Output:

Explanation:

Before the Insertion of the element:

   50
  / \
 30  40
 / \
10  20

After insertion of the element 60, the tree will look like this,

     60
   /   \
  30     50
 /  \    /
10  20  40

Insertion Code of Heap Sort in C++

Output:

Explanation:

Before the Insertion of the element:

  50
 /  \
 30  40
 / \
10 20

After insertion of the element 60, the tree will look like this,

     60
   /   \
  30     50
 /  \    /
10  20  40

Insertion Code of Heap Sort in Python

Output:

Explanation:

Before the Insertion of the element:

    50
   /  \
  30  40
 / \
10 20

After insertion of the element 60, the tree will look like this,

     60
   /   \
  30     50
 /  \    /
10  20  40

Removing the Smallest Element from Heap

A Min-Heap is a binary tree where each parent node is less than or equal to its child node. And the smallest element is always present at the root, i.e., at index 0. The min-heap is typically stored as an array for efficiency. The smallest element in the heap can be removed using the Min-heap.

A Min-Heap guarantees that the smallest element is always at the root, i.e., at index 0. Each parent node present in the heap is less than or equal to its children, but the rest of the array is not ordered.

Steps to Remove the Smallest Item from a Min-Heap

Consider an array arr, and then follow the steps below.

Step 1: Replace Root with Last Element: First, replace the last element present in the heap with the root element, i.e., at index 0. Then reduce the heap size by 1 and remove the last element.

Step 2: Heapify Down: Then start with the root element and compare it with its child nodes. If the root element is greater than any child element, then swap it with the smaller child, and repeat this process until the Min-Heap property is satisfied.

Now, let us discuss the code for the deletion of the smallest element in the Heap Sort.

Java Code to Delete Smallest Element from Heap

Output:

Explanation:

Before the Deletion of the element:

    1
   /  \
  3    5
 /  \   \
10 20    40

After deletion of element 1, the tree will look like this,

    3
   /  \
  10   5
 / \
40  20

C++ Code to Delete Smallest Element from Heap

Output:

Explanation:

Before the Deletion of the element:

    1
   /  \
  3    5
 /  \   \
10  20   40

After deletion of element 1, the tree will look like this,

   3
  /  \
 10   5
 / \
40  20

Python Code to Delete Smallest Element from Heap

Output:

Explanation:

Before the Deletion of the element:

    1
   /  \
  3    5
 /  \   \
10  20   40

After deletion of element 1, the tree will look like this,

   3
  /  \
 10   5
 / \
40  20

Removing the Largest Element from Heap

A Max-Heap is a complete binary tree where every parent node is greater than or equal to its child nodes. The maximum element is always present at the root, i.e., at index 0. It’s implemented using an array for efficiency.

Steps to Remove the Maximum Element

Step 1: Replace the Root with the Last Element. Move the last element to the root of the tree, this removes the maximum value present from the heap and reduces the size of the heap by 1.

Step 2: Heapify Down. From the root of the tree, compare its children. If the root element is smaller than any child element, then swap it with the larger child, and repeat this process downwards until the Max-Heap property is achieved

Now, let us discuss the code for the deletion of the largest element in the Heap Sort.

Java Code to Delete Largest Element from Heap

Output:

Explanation:

Before the deletion of the maximum value from the tree.

   40
  /  \
 30   20
 / \
10  5

After the deletion of the maximum value from the tree.

   30
  /  \
 10  20
 /
5

C++ Code to Delete Largest Element from Heap

Output:

Explanation:

Before the deletion of the maximum value from the tree.

   40
  /  \
 30   20
 / \
10  5

After the deletion of the maximum value from the tree.

  30
 /  \
 10  20
 /
5

Python Code to Delete Largest Element from Heap

Output:

Explanation:

Before the deletion of the maximum value from the tree.

   40
  /  \
 30   20
 / \
10  5

After the deletion of the maximum value from the tree.

  30
 /  \
 10  20
 /
5

Time and Space Complexity of Heap Sort

First, an array is converted into a max heap. This includes the heapifying of the nodes, and it does not take O(n log n) because most nodes are at the bottom and require fewer swaps. An efficient heap construction by using the bottom-up method takes O(n) time.

After placing the max element at the end, we follow the process of heapifying the root again. It takes O(log n) time because the height of a binary heap is log n. Then, the max root is extracted n times. Each extraction is followed by a heapify call of O(log n). Hence,

Total time: n * O(log n) = O(n log n)

Advantages of Heap Sort

• Consistent Time Complexity: Heap Sort always takes the time of O(n log n), whether the array is sorted or not, or what the input is. It does not get slow for already sorted or reverse-sorted data like QuickSort does.
• In-Place Sorting: Heap Sort does not take extra memory space, i.e., it sorts the elements in the same array, so its space complexity is O(1), which makes it memory-efficient.
• Not Recursive: You can write the heap sort using loops, unlike Merge Sort or Quick Sort, which are dependent on recursion.
• Good for Priority Queues: Heap sort is based on the heap data structure, which is good for applications like priority scheduling, where the highest priority item must be handled first.

Disadvantages of Heap Sort

• Not a Stable Sort: If two elements in an array have the same value, the heap sort can change their original order, hence it does not preserve the order of equal elements, which can be a problem in some applications, like sorting records by multiple fields.
• Slower in Practice: Even though Heap Sort has good time complexity, it is usually slower than QuickSort or Merge Sort in the real world because it does not take the full advantage of the CPU due to how the elements are accessed in a limited memory.
• Complex Heapify Logic: The process of heapify is more complex than using the simple loops used in Bubble Sort or Selection Sort, due to which it takes more time to learn and write the code correctly.
• Not Adaptive: Heap Sort does not take advantage of already sorted data. Whether the array is sorted or random, it does the same amount of work.

Real World Applications of Heap Sort

• Priority Queues in Operating Systems: Operating systems use priority queues to manage which tasks or processes will run first. For example, the CPU picks the process with the highest priority, which has to be executed first.
• K Largest or Smallest Elements in Big Data: When dealing with large sets of data, if the user wants only the top 10 scores, top 5 prices, etc., instead of sorting everything, a heap of size k can track just the top k elements using heap operations.
• Dijkstra’s Shortest Path Algorithm: In graph algorithms like Dijkstra’s, a Min-Heap is used to select the node with the smallest distance. The heap data structure solve the problem of Dijkstra’s algorithm, with the core heap operations from it.
• Load Balancing: When distributing the multiple tasks to multiple servers, the one with the least load is picked. A Min-Heap can quickly find the least loaded server.

Conclusion

Heap Sort uses a binary heap to sort elements in O(n log n) time. It does not need extra space and also works well for tasks like priority scheduling, finding top-k elements, and more. Though it’s not stable and slower in practice than some other sorting techniques, it is a great choice when performance and memory efficiency matter. Learning Heap Sort also helps you understand heaps better, which are used in many real-world problems.

Heap Sort – FAQs