Algorithm
Heap Sort is a comparison-based sorting algorithm that uses a binary heap data structure to build a max-heap or min-heap. The heap data structure is a specialized tree-based structure that satisfies the heap property. In a max-heap, for every node i, the value of i is greater than or equal to the values of its children. In a min-heap, for every node i, the value of i is less than or equal to the values of its children.
The basic idea of Heap Sort involves two main steps:
-
Heapify: Build a max-heap (for sorting in ascending order) or min-heap (for sorting in descending order) from the input array. This is typically done by starting from the last non-leaf node in the heap and repeatedly heapifying the subtrees.
-
Sorting: Swap the root of the heap (which contains the maximum or minimum element) with the last element of the heap and then reduce the heap size by one. After each swap, heapify the remaining elements to maintain the heap property. Repeat this process until the entire array is sorted.
The time complexity of Heap Sort is O(nlogn) in the worst case, where n is the number of elements in the array. The space complexity is O(1) since the algorithm performs the sorting in place.
Code Examples
#1 Heap Sort implement in Python
Code -
Python Programming
def heapify(arr, n, i):
largest = i # Initialize largest as the root
left_child = 2 * i + 1
right_child = 2 * i + 2
# Check if the left child exists and is greater than the root
if left_child < n and arr[left_child] > arr[largest]:
largest = left_child
# Check if the right child exists and is greater than the root
if right_child < n and arr[right_child] > arr[largest]:
largest = right_child
# Change root if needed
if largest != i:
arr[i], arr[largest] = arr[largest], arr[i] # Swap
# Recursively heapify the affected sub-tree
heapify(arr, n, largest)
def heap_sort(arr):
n = len(arr)
# Build a max heap
for i in range(n // 2 - 1, -1, -1):
heapify(arr, n, i)
# Extract elements one by one
for i in range(n - 1, 0, -1):
arr[i], arr[0] = arr[0], arr[i] # Swap the root with the last element
heapify(arr, i, 0) # Heapify the reduced heap
# Example usage:
arr = [12, 11, 13, 5, 6, 7]
heap_sort(arr)
print("Sorted array:", arr)
#2 Heap Sort implement in Java
Code -
Java Programming
public class HeapSort {
public static void main(String[] args) {
int[] array = {4, 10, 3, 5, 1};
System.out.println("Original array:");
printArray(array);
heapSort(array);
System.out.println("\nSorted array:");
printArray(array);
}
public static void heapSort(int[] array) {
int n = array.length;
// Build max heap
for (int i = n / 2 - 1; i >= 0; i--) {
heapify(array, n, i);
}
// Extract elements from heap one by one
for (int i = n - 1; i > 0; i--) {
// Swap the root (maximum element) with the last element
int temp = array[0];
array[0] = array[i];
array[i] = temp;
// Call max heapify on the reduced heap
heapify(array, i, 0);
}
}
public static void heapify(int[] array, int n, int i) {
int largest = i;
int leftChild = 2 * i + 1;
int rightChild = 2 * i + 2;
// If left child is larger than root
if (leftChild < n && array[leftChild] > array[largest]) {
largest = leftChild;
}
// If right child is larger than largest so far
if (rightChild < n && array[rightChild] > array[largest]) {
largest = rightChild;
}
// If largest is not the root
if (largest != i) {
// Swap the root with the largest element
int swap = array[i];
array[i] = array[largest];
array[largest] = swap;
// Recursively heapify the affected sub-tree
heapify(array, n, largest);
}
}
public static void printArray(int[] array) {
for (int num : array) {
System.out.print(num + " ");
}
System.out.println();
}
}
#3 Heap Sort implement in C
Code -
C Programming
#include <stdio.h>
// Function to perform heapify on a subtree rooted at index i
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 the root with the largest element
int temp = arr[i];
arr[i] = arr[largest];
arr[largest] = temp;
// Recursively heapify the affected sub-tree
heapify(arr, n, largest);
}
}
// Main function to perform heap sort
void heapSort(int arr[], int n) {
// Build a max heap
for (int i = n / 2 - 1; i >= 0; i--)
heapify(arr, n, i);
// Extract elements one by one from the heap
for (int i = n - 1; i > 0; i--) {
// Swap the root (maximum element) with the last element
int temp = arr[0];
arr[0] = arr[i];
arr[i] = temp;
// Call heapify on the reduced heap
heapify(arr, i, 0);
}
}
// Function to print an array
void printArray(int arr[], int n) {
for (int i = 0; i < n; ++i)
printf("%d ", arr[i]);
printf("\n");
}
// Driver program
int main() {
int arr[] = {12, 11, 13, 5, 6, 7};
int n = sizeof(arr) / sizeof(arr[0]);
printf("Original array: \n");
printArray(arr, n);
heapSort(arr, n);
printf("Sorted array: \n");
printArray(arr, n);
return 0;
}
#4 Heap Sort implement in C++
Code -
C++ Programming
#include <iostream>
#include <vector>
void heapify(std::vector<int>& arr, int n, int i) {
int largest = i;
int left = 2 * i + 1;
int right = 2 * i + 2;
if (left < n && arr[left] > arr[largest])
largest = left;
if (right < n && arr[right] > arr[largest])
largest = right;
if (largest != i) {
std::swap(arr[i], arr[largest]);
heapify(arr, n, largest);
}
}
void heapSort(std::vector<int>& arr) {
int n = arr.size();
// Build max heap
for (int i = n / 2 - 1; i >= 0; i--)
heapify(arr, n, i);
// Extract elements from the heap one by one
for (int i = n - 1; i >= 0; i--) {
std::swap(arr[0], arr[i]);
heapify(arr, i, 0);
}
}
int main() {
std::vector<int> arr = {12, 11, 13, 5, 6, 7};
int n = arr.size();
std::cout << "Original array: ";
for (int i = 0; i < n; i++)
std::cout << arr[i] << " ";
std::cout << std::endl;
heapSort(arr);
std::cout << "Sorted array: ";
for (int i = 0; i < n; i++)
std::cout << arr[i] << " ";
std::cout << std::endl;
return 0;
}
Demonstration
Heap Sort Data Structure and Algorithm