Table of Contents
Heap Sort
Heap sort is a comparison-based sorting algorithm that uses a binary heap data structure to sort a list of numbers in ascending or descending order.
A binary heap is a complete binary tree (that is, a tree in which every level is completely filled except possibly the last level, and the last level is filled from left to right) in which the value of each node is greater than or equal to the values of its children. In a max-heap, the value of each node is greater than or equal to the values of its children, while in a min-heap, the value of each node is less than or equal to the values of its children.
To sort a list using heap sort:
- Build a max-heap or min-heap from the list.
- Swap the root element (which is the maximum or minimum element in a heap) with the last element in the heap.
- Remove the last element from the heap and re-heapify the remaining elements to maintain the heap property.
- Repeat steps 2 and 3 until the heap is empty.
CT The time complexity of heap sort is O(n log n), making it more efficient than bubble sort, insertion sort, and selection sort, but slightly less efficient than merge sort and quick sort. However, heap sort has the advantage of being a stable sort, meaning that the order of elements with equal values is preserved.
function heap_sort(A)
build_max_heap(A)
for i = length(A) down to 2
swap(A[1], A[i])
heap_size = heap_size - 1
max_heapify(A, 1)
end for
end function
function build_max_heap(A)
heap_size = length(A)
for i = floor(length(A) / 2) down to 1
max_heapify(A, i)
end for
end function
function max_heapify(A, i)
left = left(i)
right = right(i)
if left <= heap_size and A[left] > A[i]
largest = left
else
largest = i
end if
if right <= heap_size and A[right] > A[largest]
largest = right
end if
if largest != i
swap(A[i], A[largest])
max_heapify(A, largest)
end if
end function
Heap sort in different languages
C++
#include <iostream>
#include <vector>
void heapify(std::vector<int> &nums, 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
// If left child is larger than root
if (left < n && nums[left] > nums[largest])
largest = left;
// If right child is larger than largest so far
if (right < n && nums[right] > nums[largest])
largest = right;
// If largest is not root
if (largest != i) {
std::swap(nums[i], nums[largest]);
// Recursively heapify the affected sub-tree
heapify(nums, n, largest);
}
}
void heap_sort(std::vector<int> &nums) {
int n = nums.size();
// Build heap (rearrange array)
for (int i = n / 2 - 1; i >= 0; i--)
heapify(nums, n, i);
// One by one extract an element from heap
for (int i=n-1; i>=0; i--) {
// Move current root to end
std::swap(nums[0], nums[i]);
// call max heapify on the reduced heap
heapify(nums, i, 0);
}
}
int main() {
std::vector<int> nums = {4, 10, 3, 5, 1};
heap_sort(nums);
for (int num : nums) {
std::cout << num << " ";
}
std::cout << std::endl;
return 0;
}
Python
def heapify(nums, n, i):
largest = i # Initialize largest as root
left = 2*i + 1 # left = 2*i + 1
right = 2*i + 2 # right = 2*i + 2
# If left child is larger than root
if left < n and nums[left] > nums[largest]:
largest = left
# If right child is larger than largest so far
if right < n and nums[right] > nums[largest]:
largest = right
# If largest is not root
if largest != i:
nums[i], nums[largest] = nums[largest], nums[i] # swap
# Recursively heapify the affected sub-tree
heapify(nums, n, largest)
def heap_sort(nums):
n = len(nums)
# Build heap (rearrange array)
for i in range(n//2 - 1, -1, -1):
heapify(nums, n, i)
# One by one extract an element from heap
for i in range(n-1, 0, -1):
nums[i], nums[0] = nums[0], nums[i] # Move current root to end
heapify(nums, i, 0)
nums = [4, 10, 3, 5, 1]
heap_sort(nums)
print(nums)
Java
import java.util.Arrays;
public class HeapSort {
public static void heapify(int[] nums, 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
// If left child is larger than root
if (left < n && nums[left] > nums[largest])
largest = left;
// If right child is larger than largest so far
if (right < n && nums[right] > nums[largest])
largest = right;
// If largest is not root
if (largest != i) {
// swap
int temp = nums[i];
nums[i] = nums[largest];
nums[largest] = temp;
// Recursively heapify the affected sub-tree
heapify(nums, n, largest);
}
}
public static void heapSort(int[] nums) {
int n = nums.length;
// Build heap (rearrange array)
for (int i = n / 2 - 1; i >= 0; i--)
heapify(nums, 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 = nums[0];
nums[0] = nums[i];
nums[i] = temp;
// call max heapify on the reduced heap
heapify(nums, i, 0);
}
}
public static void main(String[] args) {
int[] nums = {4, 10, 3, 5, 1};
heapSort(nums);
System.out.println(Arrays.toString(nums));
}
}
JavaScript
function heapify(nums, 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
// If left child is larger than root
if (left < n && nums[left] > nums[largest]) {
largest = left;
}
// If right child is larger than largest so far
if (right < n && nums[right] > nums[largest]) {
largest = right;
}
// If largest is not root
if (largest !== i) {
[nums[i], nums[largest]] = [nums[largest], nums[i]]; // swap
// Recursively heapify the affected sub-tree
heapify(nums, n, largest);
}
}
function heapSort(nums) {
let n = nums.length;
// Build heap (rearrange array)
for (let i = Math.floor(n/2) - 1; i >= 0; i--) {
heapify(nums, n, i);
}
// One by one extract an element from heap
for (let i = n - 1; i >= 0; i--) {
[nums[0], nums[i]] = [nums[i], nums[0]]; // Move current root to end
heapify(nums, i, 0);
}
}
let nums = [4, 10, 3, 5, 1];
heapSort(nums);
console.log(nums);
PHP
function heapify(&$nums, $n, $i) {
$largest = $i; // Initialize largest as root
$left = 2*$i + 1; // left = 2*i + 1
$right = 2*$i + 2; // right = 2*i + 2
// If left child is larger than root
if ($left < $n && $nums[$left] > $nums[$largest]) {
$largest = $left;
}
// If right child is larger than largest so far
if ($right < $n && $nums[$right] > $nums[$largest]) {
$largest = $right;
}
// If largest is not root
if ($largest != $i) {
list($nums[$i], $nums[$largest]) = array($nums[$largest], $nums[$i]); // swap
// Recursively heapify the affected sub-tree
heapify($nums, $n, $largest);
}
}
function heapSort(&$nums) {
$n = count($nums);
// Build heap (rearrange array)
for ($i = floor($n/2) - 1; $i >= 0; $i--) {
heapify($nums, $n, $i);
}
// One by one extract an element from heap
for ($i = $n - 1; $i >= 0; $i--) {
list($nums[0], $nums[$i]) = array($nums[$i], $nums[0]); // Move current root to end
heapify($nums, $i, 0);
}
}
$nums = array(4, 10, 3, 5, 1);
heapSort($nums);
print_r($nums);
Heap sort Explanation
In this example, heapSort takes a single argument, nums, which is an array of integers that will be sorted. The function first calls heapify to build the initial heap.
heapify takes three arguments: the array to be heapified, the size of the array, and the current index.
After the heap is built, the function then repeatedly extracts the maximum element from the heap and places it at the end of the array, reducing the size of the heap by one.
Each time an element is extracted heapify is called again to maintain the heap property.
The standard JavaScript arrays are zero-indexed, so the left and right children of a node at index i are at indexes 2i + 1 and 2i + 2, respectively.
Cheers.