 # Heap sort algorithm

In this tutorial, we will learn about the Heap sort algorithm.

Sorting is one of the fundamental operations in computer science, and there are numerous sorting algorithms available. Merge sort is one such algorithm, which is efficient and widely used in programming languages. In this article, we will discuss the merge sort algorithm and its implementation in C++, Java, and Python.

Heap Sort is a comparison-based sorting algorithm that uses a binary heap data structure to sort an array in ascending or descending order. Heap Sort has a time complexity of O(n*log n), which makes it an efficient sorting algorithm for large datasets. In this article, we will explore the implementation of Heap Sort in C++, Java, and Python, along with an explanation of each pass of the algorithm.

Contents

## C++ Implementation of Heap Sort:

```void heapify(int arr[], int n, int i) {
int largest = i;
int l = 2*i + 1;
int r = 2*i + 2;

if (l < n && arr[l] > arr[largest])
largest = l;

if (r < n && arr[r] > arr[largest])
largest = r;

if (largest != i) {
swap(arr[i], arr[largest]);
heapify(arr, n, largest);
}
}

void heapSort(int arr[], int n) {
for (int i = n / 2 - 1; i >= 0; i--)
heapify(arr, n, i);

for (int i = n - 1; i >= 0; i--) {
swap(arr, arr[i]);
heapify(arr, i, 0);
}
}

int main() {
int arr[] = {12, 11, 13, 5, 6, 7};
int n = sizeof(arr)/sizeof(arr);

heapSort(arr, n);

cout << "Sorted array is: \n";
for (int i = 0; i < n; ++i)
cout << arr[i] << " ";
}

```

In the C++ implementation, the `heapify()` function is used to create a heap from an array, and the `heapSort()` function is used to sort the array using the heap data structure. In the `main()` function, we create an array, call the `heapSort()` function, and print the sorted array.

In the first pass of the algorithm, the `heapify()` function is called on each non-leaf node of the binary tree, starting from the bottom of the tree and working up to the root. The `heapify()` function compares the parent node with its left and right child nodes, and swaps the parent node with the largest child node if necessary. This creates a heap structure, where the largest element is at the root of the tree.

In the second pass of the algorithm, the `heapSort()` function repeatedly extracts the largest element from the root of the heap and places it at the end of the array. The heap is then reconstructed by calling `heapify()` on the remaining elements of the heap. This process continues until the entire array is sorted.

Java Implementation of Heap Sort:

## Java Implementation of Heap Sort:

```public class HeapSort {
public void sort(int arr[]) {
int n = arr.length;

// Build heap (rearrange array)
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;
arr = arr[i];
arr[i] = temp;

// call max heapify on the reduced heap
heapify(arr, i, 0);
}
}

void heapify(int arr[], int n, int i) {
int largest = i; // Initialize largest as root
int l = 2 * i + 1; // left = 2*i + 1
int r = 2 * i + 2; // right = 2*i + 2

// If left child is larger than root
if (l < n && arr[l] > arr[largest])
largest = l;

// If right child is larger than largest so far
if (r < n && arr[r] > arr[largest])
largest = r;

// If largest is not root
if (largest != i) {
int swap = arr[i];
arr[i] = arr[largest];
arr[largest] = swap;

// Recursively heapify the affected sub-tree
heapify(arr, n, largest);
}
}
}

```

In the Java implementation, the `HeapSort` class has a `sort()` method that takes an array as input and sorts it using the heap sort algorithm. The `heapify()` method is used to create a heap from an array, and the `sort()` method calls the `heapify()` method on each non-leaf node of the binary tree to create a heap structure. The largest element is then repeatedly extracted from the root of the heap and placed at the end of the array, and the heap is reconstructed by calling `heapify()` on the remaining elements of the heap.

## Python Implementation of Heap Sort:

```def heapify(arr, n, i):
largest = i
l = 2 * i + 1
r = 2 * i + 2

if l < n and arr[i] < arr[l]:
largest = l

if r < n and arr[largest] < arr[r]:
largest = r

if largest != i:
arr[i], arr[largest] = arr[largest], arr[i]
heapify(arr, n, largest)

def heapSort(arr):
n = len(arr)

for i in range(n // 2 - 1, -1, -1):
heapify(arr, n, i)

for i in range(n - 1, 0, -1):
arr, arr[i] = arr[i], arr
heapify(arr, i, 0)

arr = [12, 11, 13, 5, 6, 7]
heapSort(arr)
print("Sorted array is:")
for i in range(len(arr)):
print("%d" % arr[i])

```

The Python implementation of Heap Sort is similar to the C++ and Java implementations, with the `heapify()` function used to create a heap from an array, and the `heapSort()` function used to sort the array using the heap data structure. In the first pass of the algorithm, the `heapify()` function is called on each non-leaf node of the binary tree to create a heap structure. In the second pass of the algorithm, the largest element is repeatedly extracted from the root of the heap and placed at the end of the array, and the heap is reconstructed by calling `heapify()` on the remaining elements of the heap.

Each pass of the Heap Sort algorithm involves creating a heap from an array and then sorting the array using the heap data structure. In the first pass, the `heapify()` function is called on each non-leaf node of the binary tree to create a heap structure. In the second pass, the largest element is repeatedly extracted from the root of the heap and placed at the end of the array, and the heap is reconstructed by calling `heapify()` on the remaining elements of the heap.