Heap Sort
Heap Sort :
Author(s) : J. W. J. Williams Date : 1964Heap sort is a sorting algorithm that utilizes a heap data structure for efficient element arrangement. It follows a divide-and-conquer approach, initially building a max-heap (where the root has the largest value) from the input array. This process involves repeatedly swapping elements to ensure the heap property holds (parent element greater than or equal to children). Once the max-heap is constructed, the largest element (root) is extracted and placed at the end of the sorted array. The heap is then rearranged by swapping the root with the last element and restoring the heap property. This process of extraction, rearrangement, and swapping continues until the entire array is sorted in descending order. For ascending order, a min-heap (root has the smallest value) would be used.
Time Complexity | O(n log n) |
Best Case | O(n log n) |
Worst Case | O(n log n) |
Space Complexity | O(1) |
Stable | No |
Code Integration:
* the code might contain some bugs or may not work correctly
def heapify(arr, n, i):
largest = i # Initialize largest as root
lf = 2 * i + 1 # left = 2*i + 1
right = 2 * i + 2 # right = 2*i + 2
# See if left child is larger than root
if lf < n and arr[i] < arr[lf]:
largest = lf
# See if right child is larger
if right < n and arr[largest] < arr[right]:
largest = right
# Swap if largest is not root
if largest != i:
arr[i], arr[largest] = arr[largest], arr[i]
heapify(arr, n, largest)
def heap_sort(arr):
n = len(arr)
# Build a maxheap.
for i in range(n // 2 - 1, -1, -1):
heapify(arr, n, i)
# One by one extract an element from heap
for i in range(n - 1, 0, -1):
arr[i], arr[0] = arr[0], arr[i] # swap
heapify(arr, i, 0) # reduce heap size and maintain heap property
# Test array
arr = [12, 11, 13, 5, 6, 7]
heap_sort(arr)
print('Sorted array is:', arr)
function heapify(arr, n, i) {
let largest = i; // Initialize largest as root
let left = 2 * i + 1; // left = 2*i + 1
let right = 2 * i + 2; // right = 2*i + 2
// See if left child is larger than root
if (left < n && arr[i] < arr[left]) {
largest = left;
}
// See if right child is larger
if (right < n && arr[largest] < arr[right]) {
largest = right;
}
// Swap if largest is not root
if (largest !== i) {
let temp = arr[i];
arr[i] = arr[largest];
arr[largest] = temp;
heapify(arr, n, largest);
}
}
function heapSort(arr) {
let n = arr.length;
// Build a maxheap.
for (let i = Math.floor(n / 2) - 1; i >= 0; i--) {
heapify(arr, n, i);
}
// One by one extract an element from heap
for (let i = n - 1; i > 0; i--) {
// Move current root to end
let temp = arr[0];
arr[0] = arr[i];
arr[i] = temp;
heapify(arr, i, 0);
}
}
// Test array
let arr = [12, 11, 13, 5, 6, 7];
heapSort(arr);
console.log('Sorted array is:', arr);
public class HeapSort {
public static void heapify(int arr[], int n, int i) {
int largest = i; // Initialize largest as root
int left = 2 * i + 1; // left = 2*i + 1
int right = 2 * i + 2; // right = 2*i + 2
// See if left child is larger than root
if (left < n && arr[i] < arr[left]) {
largest = left;
}
// See if right child is larger
if (right < n && arr[largest] < arr[right]) {
largest = right;
}
// Swap if largest is not root
if (largest != i) {
int temp = arr[i];
arr[i] = arr[largest];
arr[largest] = temp;
heapify(arr, n, largest);
}
}
public static void heapSort(int arr[]) {
int n = arr.length;
// Build a maxheap.
for (int i = n / 2 - 1; i >= 0; i--) {
heapify(arr, n, i);
}
// One by one extract an element from heap
for (int i = n - 1; i > 0; i--) {
// Move current root to end
int temp = arr[0];
arr[0] = arr[i];
arr[i] = temp;
heapify(arr, i, 0);
}
}
public static void main(String args[]) {
int arr[] = {12, 11, 13, 5, 6, 7};
heapSort(arr);
System.out.println("Sorted array is: ");
for (int i = 0; i < arr.length; ++i) {
System.out.print(arr[i] + " ");
}
}
}
package main
import (
"fmt"
)
func heapify(arr []int, n int, i int) {
largest := i // Initialize largest as root
left := 2*i + 1 // left = 2*i + 1
right := 2*i + 2 // right = 2*i + 2
// See if left child is larger than root
if left < n && arr[i] < arr[left] {
largest = left
}
// See if right child is larger
if right < n && arr[largest] < arr[right] {
largest = right
}
// Swap if largest is not root
if largest != i {
arr[i], arr[largest] = arr[largest], arr[i]
heapify(arr, n, largest)
}
}
func heapSort(arr []int) {
n := len(arr)
// Build a maxheap.
for i := n/2 - 1; i >= 0; i-- {
heapify(arr, n, i)
}
// One by one extract an element from heap
for i := n - 1; i > 0; i-- {
// Move current root to end
arr[0], arr[i] = arr[i], arr[0]
heapify(arr, i, 0)
}
}
func main() {
arr := []int{12, 11, 13, 5, 6, 7}
heapSort(arr)
fmt.Println("Sorted array is: ", arr)
}
#include <stdio.h>
void swap(int *a, int *b) {
int temp = *a;
*a = *b;
*b = temp;
}
void heapify(int arr[], int n, int i) {
int largest = i; // Initialize largest as root
int left = 2 * i + 1; // left = 2*i + 1
int right = 2 * i + 2; // right = 2*i + 2
// See if left child is larger than root
if (left < n && arr[i] < arr[left]) {
largest = left;
}
// See if right child is larger
if (right < n && arr[largest] < arr[right]) {
largest = right;
}
// Swap if largest is not root
if (largest != i) {
swap(&arr[i], &arr[largest]);
heapify(arr, n, largest);
}
}
void heapSort(int arr[], int n) {
// Build a maxheap.
for (int i = n / 2 - 1; i >= 0; i--) {
heapify(arr, n, i);
}
// One by one extract an element from heap
for (int i = n - 1; i > 0; i--) {
// Move current root to end
swap(&arr[0], &arr[i]);
heapify(arr, i, 0);
}
}
int main() {
int arr[] = {12, 11, 13, 5, 6, 7};
int n = sizeof(arr) / sizeof(arr[0]);
heapSort(arr, n);
printf("Sorted array is: ");
for (int i = 0; i < n; ++i) {
printf("%d ", arr[i]);
};
return 0;
}