# Heap Sort a Sorting Algorithm

## 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:

1. Build a max-heap or min-heap from the list.
2. Swap the root element (which is the maximum or minimum element in a heap) with the last element in the heap.
3. Remove the last element from the heap and re-heapify the remaining elements to maintain the heap property.
4. 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, 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, 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 = nums, 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;
nums = 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, nums[i]] = [nums[i], nums];  // 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, \$nums[\$i]) = array(\$nums[\$i], \$nums);  // 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.

Bubble Sort Algorithm

Insertion sort: a Sorting Algorithm

Selection sort Algorithm

Quick Sort Algorithms

Merge Sort Algorithm

List of Sorting Algorithms

https://messagehimessage.com