Skip to main content

Heap Sort

Level - Medium

Statement​

Given an array of size N.Perform inplace sorting using Heap Data Structure.

Example​

Input:

N = 5
arr[] = {4,1,3,9,7}

Output:

1 3 4 7 9

Algorithm​

Build Heap:​

In build heap function we have to convert the input array into max heap.

  1. At each node we have to check that its children node should have less value.
  2. Calculate the index of the last node in heap last_node_index = n - 1.
  3. Calculate the index of the parent node of the last node as :
    • parent_node_index = (last_node_index-1)/2.
  4. Perform the heapify operation on each parent node and moving up to the root of the heap. This step ensures that the max heap property is maintained.

Heapify:​

  1. The heapify method is used to maintain the max heap property at a given node with the given index.
  2. Calculate the indices of the left and right child nodes of the current node:
    • left_child_index = 2 * index + 1
    • right_child_index = 2 * index + 2
  3. Initialize largest_index to the current node's index.
  4. Compare the values of the current node, left child node, and right child node (if they exist), and update largest_index to the index of the largest value among these nodes.
  5. If among all three nodes current node, left child node, and right child node current node is larger then:
    • heapify process is done
    • otherwise recursively call heapify function with index of the largest child node.

Heap Sort:​

  1. First, convert the input array into a max heap by calling buildHeap(arr, n).
  2. Then, repeatedly remove the maximum element (root of the max heap) by swapping it with the last element in the heap and reducing the heap size.
  3. After each swap, call heapify to maintain the max heap property from the root to the last node in the heap.
  4. Continue this process until all elements have been removed and placed in their correct positions within the sorted array.
  5. The result is a sorted array in ascending order.

Visual Walkthrough for Build heap step (To convert Input array into Max Heap Array)​

Visual Walkthrough for removing element from max heap​

Implementation​

class Solution {
    //Function to build a Heap from array.
    void buildHeap(int arr[], int n)
    {
        int last_node_index = n-1;
        int parent_node_index = (last_node_index-1)/2;
        // perform heapify operation
        for(int i=parent_node_index;i>=0;i--)heapify(arr,n,i);
    }
 
    //Heapify function to maintain heap property.
    void heapify(int arr[],int n,int index) {
        int right_child_index = 2 * index + 1;
        int left_child_index = 2 * index + 2;
        int largest_index = index;
        // select who is largest among current node , left child node and right child node
        if (left_child_index < n && arr[left_child_index] > arr[largest_index]) largest_index = left_child_index;
        if (right_child_index < n && arr[right_child_index] > arr[largest_index]) largest_index = right_child_index;
        // if current element is smaller so swap current with larger child and move in that direction
        if (largest_index != index) {
          swap(arr,index, largest_index);
          heapify(arr,n,largest_index);
        }
   }
    
    //Function to sort an array using Heap Sort.
    public void heapSort(int arr[], int n)
    {
        // first convert input array in max heap
        buildHeap(arr,n);
        // remove all the elements from heap
        for(int i=n-1;i>=0;i--){
            swap(arr,0,i); // swap root and last element in heap
            heapify(arr,i,0); // heapify from root to last node in heap       
        }
    }
    
    public void swap(int[] arr,int i,int j){
        int t = arr[i];
        arr[i] = arr[j];
        arr[j] = t;
    }
}

Complexity​

Time Complexity:

O(NlogN)

Space Complexity:

O(1)