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)