AntInLoop

Heap Sort Algorithm Code Implementations

Complete Heap Sort Algorithm code implementations in C++, Python, Java, and JavaScript with time and space complexity analysis on AntInLoop.

Read Heap Sort Algorithm Guide ยท Launch Interactive Visualizer

C++ Implementation

// Heap Sort Implementation in C++
#include <iostream>
#include <vector>
#include <algorithm>

class HeapSort {
public:
    static std::vector<int> heapSort(const std::vector<int>& arr) {
        if (arr.size() <= 1) {
            return arr;
        }
        
        std::vector<int> sortedArray = arr;
        int n = sortedArray.size();
        
        // Build max heap (rearrange array)
        for (int i = n / 2 - 1; i >= 0; i--) {
            heapify(sortedArray, n, i);
        }
        
        // Extract elements from heap one by one
        for (int i = n - 1; i > 0; i--) {
            // Move current root to end
            std::swap(sortedArray[0], sortedArray[i]);
            
            // Call heapify on the reduced heap
            heapify(sortedArray, i, 0);
        }
        
        return sortedArray;
    }
    
private:
    static void heapify(std::vector<int>& arr, int n, int i) {
        int largest = i; // Initialize largest as root
        int left = 2 * i + 1; // Left child
        int right = 2 * i + 2; // Right child
        
        // If left child is larger than root
        if (left < n && arr[left] > arr[largest]) {
            largest = left;
        }
        
        // If right child is larger than largest so far
        if (right < n && arr[right] > arr[largest]) {
            largest = right;
        }
        
        // If largest is not root
        if (largest != i) {
            std::swap(arr[i], arr[largest]);
            
            // Recursively heapify the affected sub-tree
            heapify(arr, n, largest);
        }
    }
    
public:
    // Min Heap implementation (for ascending order)
    static std::vector<int> heapSortMin(const std::vector<int>& arr) {
        if (arr.size() <= 1) {
            return arr;
        }
        
        std::vector<int> sortedArray = arr;
        int n = sortedArray.size();
        
        // Build min heap
        for (int i = n / 2 - 1; i >= 0; i--) {
            heapifyMin(sortedArray, n, i);
        }
        
        // Extract elements from heap one by one
        for (int i = n - 1; i > 0; i--) {
            std::swap(sortedArray[0], sortedArray[i]);
            heapifyMin(sortedArray, i, 0);
        }
        
        return sortedArray;
    }
    
private:
    static void heapifyMin(std::vector<int>& arr, int n, int i) {
        int smallest = i;
        int left = 2 * i + 1;
        int right = 2 * i + 2;
        
        if (left < n && arr[left] < arr[smallest]) {
            smallest = left;
        }
        
        if (right < n && arr[right] < arr[smallest]) {
            smallest = right;
        }
        
        if (smallest != i) {
            std::swap(arr[i], arr[smallest]);
            heapifyMin(arr, n, smallest);
        }
    }
};

JAVA Implementation

// Heap Sort Implementation in Java
public class HeapSort {
    public static int[] heapSort(int[] arr) {
        if (arr == null || arr.length <= 1) {
            return arr.clone();
        }
        
        int[] sortedArray = arr.clone();
        int n = sortedArray.length;
        
        // Build max heap (rearrange array)
        for (int i = n / 2 - 1; i >= 0; i--) {
            heapify(sortedArray, n, i);
        }
        
        // Extract elements from heap one by one
        for (int i = n - 1; i > 0; i--) {
            // Move current root to end
            swap(sortedArray, 0, i);
            
            // Call heapify on the reduced heap
            heapify(sortedArray, i, 0);
        }
        
        return sortedArray;
    }
    
    private static void heapify(int[] arr, int n, int i) {
        int largest = i; // Initialize largest as root
        int left = 2 * i + 1; // Left child
        int right = 2 * i + 2; // Right child
        
        // If left child is larger than root
        if (left < n && arr[left] > arr[largest]) {
            largest = left;
        }
        
        // If right child is larger than largest so far
        if (right < n && arr[right] > arr[largest]) {
            largest = right;
        }
        
        // If largest is not root
        if (largest != i) {
            swap(arr, i, largest);
            
            // Recursively heapify the affected sub-tree
            heapify(arr, n, largest);
        }
    }
    
    private static void swap(int[] arr, int i, int j) {
        int temp = arr[i];
        arr[i] = arr[j];
        arr[j] = temp;
    }
    
    // Min Heap implementation (for ascending order)
    public static int[] heapSortMin(int[] arr) {
        if (arr == null || arr.length <= 1) {
            return arr.clone();
        }
        
        int[] sortedArray = arr.clone();
        int n = sortedArray.length;
        
        // Build min heap
        for (int i = n / 2 - 1; i >= 0; i--) {
            heapifyMin(sortedArray, n, i);
        }
        
        // Extract elements from heap one by one
        for (int i = n - 1; i > 0; i--) {
            swap(sortedArray, 0, i);
            heapifyMin(sortedArray, i, 0);
        }
        
        return sortedArray;
    }
    
    private static void heapifyMin(int[] arr, int n, int i) {
        int smallest = i;
        int left = 2 * i + 1;
        int right = 2 * i + 2;
        
        if (left < n && arr[left] < arr[smallest]) {
            smallest = left;
        }
        
        if (right < n && arr[right] < arr[smallest]) {
            smallest = right;
        }
        
        if (smallest != i) {
            swap(arr, i, smallest);
            heapifyMin(arr, n, smallest);
        }
    }
}

JAVASCRIPT Implementation

// Heap Sort Implementation in JavaScript
function heapSort(arr) {
  const n = arr.length;
  const sortedArray = [...arr]; // Create a copy to avoid mutating original
  
  // Build max heap (rearrange array)
  for (let i = Math.floor(n / 2) - 1; i >= 0; i--) {
    heapify(sortedArray, n, i);
  }
  
  // Extract elements from heap one by one
  for (let i = n - 1; i > 0; i--) {
    // Move current root to end
    [sortedArray[0], sortedArray[i]] = [sortedArray[i], sortedArray[0]];
    
    // Call heapify on the reduced heap
    heapify(sortedArray, i, 0);
  }
  
  return sortedArray;
}

function heapify(arr, n, i) {
  let largest = i; // Initialize largest as root
  const left = 2 * i + 1; // Left child
  const right = 2 * i + 2; // Right child
  
  // If left child is larger than root
  if (left < n && arr[left] > arr[largest]) {
    largest = left;
  }
  
  // If right child is larger than largest so far
  if (right < n && arr[right] > arr[largest]) {
    largest = right;
  }
  
  // If largest is not root
  if (largest !== i) {
    [arr[i], arr[largest]] = [arr[largest], arr[i]];
    
    // Recursively heapify the affected sub-tree
    heapify(arr, n, largest);
  }
}

// Min Heap implementation (for ascending order)
function heapSortMin(arr) {
  const n = arr.length;
  const sortedArray = [...arr];
  
  // Build min heap
  for (let i = Math.floor(n / 2) - 1; i >= 0; i--) {
    heapifyMin(sortedArray, n, i);
  }
  
  // Extract elements from heap one by one
  for (let i = n - 1; i > 0; i--) {
    [sortedArray[0], sortedArray[i]] = [sortedArray[i], sortedArray[0]];
    heapifyMin(sortedArray, i, 0);
  }
  
  return sortedArray;
}

function heapifyMin(arr, n, i) {
  let smallest = i;
  const left = 2 * i + 1;
  const right = 2 * i + 2;
  
  if (left < n && arr[left] < arr[smallest]) {
    smallest = left;
  }
  
  if (right < n && arr[right] < arr[smallest]) {
    smallest = right;
  }
  
  if (smallest !== i) {
    [arr[i], arr[smallest]] = [arr[smallest], arr[i]];
    heapifyMin(arr, n, smallest);
  }
}

PYTHON Implementation

# Heap Sort Implementation in Python
def heap_sort(arr):
    n = len(arr)
    sorted_array = arr.copy()
    
    # Build max heap (rearrange array)
    for i in range(n // 2 - 1, -1, -1):
        heapify(sorted_array, n, i)
    
    # Extract elements from heap one by one
    for i in range(n - 1, 0, -1):
        # Move current root to end
        sorted_array[0], sorted_array[i] = sorted_array[i], sorted_array[0]
        
        # Call heapify on the reduced heap
        heapify(sorted_array, i, 0)
    
    return sorted_array

def heapify(arr, n, i):
    largest = i  # Initialize largest as root
    left = 2 * i + 1  # Left child
    right = 2 * i + 2  # Right child
    
    # If left child is larger than root
    if left < n and arr[left] > arr[largest]:
        largest = left
    
    # If right child is larger than largest so far
    if right < n and arr[right] > arr[largest]:
        largest = right
    
    # If largest is not root
    if largest != i:
        arr[i], arr[largest] = arr[largest], arr[i]
        
        # Recursively heapify the affected sub-tree
        heapify(arr, n, largest)

# Min Heap implementation (for ascending order)
def heap_sort_min(arr):
    n = len(arr)
    sorted_array = arr.copy()
    
    # Build min heap
    for i in range(n // 2 - 1, -1, -1):
        heapify_min(sorted_array, n, i)
    
    # Extract elements from heap one by one
    for i in range(n - 1, 0, -1):
        sorted_array[0], sorted_array[i] = sorted_array[i], sorted_array[0]
        heapify_min(sorted_array, i, 0)
    
    return sorted_array

def heapify_min(arr, n, i):
    smallest = i
    left = 2 * i + 1
    right = 2 * i + 2
    
    if left < n and arr[left] < arr[smallest]:
        smallest = left
    
    if right < n and arr[right] < arr[smallest]:
        smallest = right
    
    if smallest != i:
        arr[i], arr[smallest] = arr[smallest], arr[i]
        heapify_min(arr, n, smallest)