Iterative Heap Sort

Pseudocode for heap sort:

Now that we know how heap sort works, we can easily figure out its algorithm

heapsort(Array, size)
{
    buildMaxheap(Array, size);
    for i = size - 1 downto 0
    {
       do swap(Array[0], Array[i]);
       J = 0;
       index;
       while J less than index
       {
         Index = 2 * J + 1;
         if(Array[index] less than Array[index+1] and index less (i - 1))
            index++;
         if(Array[j] less than Array[index] and index less i)
            do swap(Array[j], Array[index]);
         J = index;
       }
    }
}

Visual representation of Heapsort:

Code for Heap Sort in C++:

#include <bits/stdc++.h>
using namespace std;

/* 
    In this build heap max function, the value of every child 
    will be smaller than its parent
*/
void buildMaxHeap(int array[], int n)
{
         for (int i = 1; i < n; i++)
         {
         // If the current child is larger than its parent
         if (array[i] > array[(i - 1) / 2])
         {
              int j = i;

               /* 
               Swapping the parent with the child until
               parent becomes smaller
               */
               while (array[j] > array[(j - 1) / 2])
               {
                      swap(array[j], array[(j - 1) / 2]);
                      j = (j - 1) / 2;
               }
          }
          }
}

void heapSort(int array[], int n)
{
         buildMaxHeap(array, n);

         for (int i = n - 1; i > 0; i--)
         {

               /* Swapping the values of first index elements
                with the last index elements */
                swap(array[0], array[i]);
          
               // Heap property is maintained after each swap
               int j = 0, index;

               do
               {
                       index = (2 * j + 1);
                   /*  Swapping the values of first index elements with
                       the last index elements 
                   */
                       if (array[index] < array[index + 1] &&
                               index < (i - 1))
                       {
                              index++;
                       }
      
                    /* 
                       If the current parent is smaller than the child, 
                      swap the parent with the higher valued child 
                    */
                    if (array[j] < array[index] && index < i)
                   {
                            swap(array[j], array[index]);
                   }

                  j = index;

          } while (index < i);
     }
}


// main function code
int main()
{

      // Input array taken
int array[] = {10, 15, 21, 30, 18, 19};
    
      // n is the size of array taken
int n = sizeof(array) / sizeof(array[0]);
       
cout << "Given array: ";

      // Printing the initial array as it is
for (int i = 0; i < n; i++)
      {
cout << array[i] << " ";
      }

cout << endl;

      // Calling heap sort on the array
heapSort(array, n);

      // Printing the array after sorting with heap sort
cout << "Sorted array: ";
for (int i = 0; i < n; i++)
      {
cout << array[i] << " ";
      }

return 0;
}

You can also try this code with Online C++ Compiler

Run Code

Output:

Time Complexity analysis for heap sort:

                                                         Source: Giphy

Time complexity: O(N logN). 

As we remove the elements from the heap, the values become sorted (since maximum elements are always root only). Since the time complexity of both the insertion algorithm and deletion algorithm is O(logN) (where n is the number of items in a heap). 

The complexity of the heap sort algorithm is O(N log N). 

In a heap sort, we build the heap at first then remove the root elements one by one; the building heap takes O(N) time; after each extraction, we make the last element as root and then again run heapify on it, which takes O(logN). As we are doing this step for all n elements, the overall time complexity is O(N logN).

Space complexity: O(1)

As constant memory space is used in the operation. Therefore, the space complexity will be O(1)

Also Read - Selection Sort in C

Advantages of heap sort:

• The heap sort is very efficient. While other algorithms get slower in working with larger data sets as they grow exponentially, heap sort grows logarithmically, taking O(N logN ) in every aspect.
• It is space-efficient. Unlike merge sort, it doesn't take any extra space, maintaining its space complexity to O(1).

Frequently Asked Questions:

1. How does heapsort work?
   In heap sort, the max heap is prepared at first. Then repeatedly, the root values are swapped with the last element, decreasing the range of array elements considered in the heap formation and placing the new value to its root.
2. What is the worst-case time complexity of heap sort?
   Time required to perform heap sort in its worst case is O(N log N).
3. Why does heap sort contain the name heap in it?
   Because while performing heap sort, we are first preparing the heap. A heap is a data structure that looks like a pyramid, made up of different nodes of a tree in specific order.
4. Is heapsort better than bubble sort?
   Heapsort is far better than bubble sort because the time complexity for heap sort is O(N logN) but the bubble sort takes O(N ^ 2).
5. Can heapsort be used in place of merge sort?
   Yes, heapsort is better than merge sort in terms of space. Heapsort takes no extra space like merge sort.

Key Takeaways:

This article gives us an idea of what this heapsort is, how to implement it, and its complexity, but this is not just the end.

Keeping the theoretical knowledge at our fingertips helps us get about half the work done. To gain complete understanding, practice is a must. A variety of coding questions from interviews based on sorting are available here.

Recommended Problems - 

• Sort 0 1 2 
• Wiggle sort
• Find first and last position in sorted array

Apart from this, you can also check Coding Ninjas Studio, where you will find numerous questions to get a grip upon and many interview experiences of scholars in renowned product-based companies