This article will explain the Heap Sort Algorithm. Heap sort accomplishes this by creating a min-heap or max-heap using the elements from the provided array. The min-heap or max-heap reveals the organization of the array, and the item at the very top indicates whether it’s the smallest or largest in the array. Before finding out more about the heap sort, let’s first see a brief description of Heap.

What is a Heap?

A heap resembles a unique tree known as a complete binary tree. In this tree type, each node can have at most two children. In a complete binary tree, every level, except the last one (which has the leaf nodes), has a complete set of nodes. And all the nodes are arranged from left to right.

The heap sort algorithm follows two main operations in this procedure −

• Builds a heap H from the input data using the heapify (explained further into the chapter) method, based on the way of sorting – ascending order or descending order.
• Delete the root element, and then continue repeating this process until you’ve processed all the input elements.

Heap Sort Algorithm

Heap Sort stands out as an efficient and widely respected sorting algorithm. Basically it is known for its capability to systematically transfer elements from the heap portion of the list to the sorted section. This process involves repeatedly selecting the maximum. (for a max-heap) or minimum (for a min-heap) element from the unsorted region and inserting it into the sorted region. Heap Sort employs a specialized tree structure called a “heap” to swiftly and efficiently complete the task. The heap sort algorithm heavily depends upon the heapify method of the binary tree. So what is this heapify method?

Heapify Method – The heapify method in a binary tree transforms the tree into a heap data structure. This method employs a recursive approach to heapify all the nodes of the binary tree.

Please note that the binary tree must always be a complete binary tree, ensuring that it consistently has two children nodes.

Algorithm

HeapSort(arr)  
BuildMaxHeap(arr)  
for i = length(arr) to 2  
    swap arr[1] with arr[i]  
        heap_size[arr] = heap_size[arr] ? 1  
        MaxHeapify(arr,1)  
End

This part of the Heap Sort algorithm is responsible for repeatedly moving the largest element to the end of the array and then adjusting the heap structure to maintain the max-heap property. This process continues until the algorithm sorts the entire array in ascending order.

Working of Heap Sort Algorithm

Heap sort comprises two main phases in the process of sorting elements. When utilizing the heap sort algorithm, we can describe these phases as follows:

The Heap Creation Phase: In this initial step, we construct a heap by adjusting the elements within the array.

Sorting Phase: After establishing the heap structure, the algorithm proceeds to repeatedly extract the root element of the heap, shift it to the end of the array, and then maintain the heap structure with the remaining elements.

Let’s now examine the inner workings of the heap sort method in greater detail, using a practical example. To enhance our comprehension, we will take an unsorted array and employ heap sort to arrange its elements. This practical demonstration will provide a clearer and more accessible explanation.

First, we have to construct a heap from the given array and convert it into max heap.

 

 

After converting the given heap into max heap, the array elements are –

Next, we have to delete the root element (89) from the max heap. To delete this node, we have to swap it with the last node, i.e. (11). After deleting the root element, we again have to heapify it to convert it into max heap.

After swapping the array element 89 with 11, and converting the heap into max-heap, the elements of array are –

In the next step, again, we have to delete the root element (81) from the max heap. To delete this node, we have to swap it with the last node, i.e. (54). After deleting the root element, we again have to heapify it to convert it into max heap.

After swapping the array element 81 with 54 and converting the heap into max-heap, the elements of array are –

In the next step, we have to delete the root element (76) from the max heap again. To delete this node, we have to swap it with the last node, i.e. (9). After deleting the root element, we again have to heapify it to convert it into max heap.

After swapping the array element 76 with 9 and converting the heap into max-heap, the elements of array are –

In the next step, again we have to delete the root element (54) from the max heap. To delete this node, we have to swap it with the last node, i.e. (14). After deleting the root element, we again have to heapify it to convert it into max heap.

After swapping the array element 54 with 14 and converting the heap into max-heap, the elements of array are –

In the next step, again we have to delete the root element (22) from the max heap. To delete this node, we have to swap it with the last node, i.e. (11). After deleting the root element, we again have to heapify it to convert it into max heap.

After swapping the array element 22 with 11 and converting the heap into max-heap, the elements of array are –

In the next step, again we have to delete the root element (14) from the max heap. To delete this node, we have to swap it with the last node, i.e. (9). After deleting the root element, we again have to heapify it to convert it into max heap.

After swapping the array element 14 with 9 and converting the heap into max-heap, the elements of array are –

In the next step, again we have to delete the root element (11) from the max heap. To delete this node, we have to swap it with the last node, i.e. (9). After deleting the root element, we again have to heapify it to convert it into max heap.

After swapping the array element 11 with 9, the elements of array are –

Now, heap has only one element left. After deleting it, heap will be empty.

After completion of sorting, the array elements are –

Now, the array is completely sorted.

Java Program Using Heap Sort Algorithm

public class HeapSort {
public static void heapSort(int arr[]) {
int n = arr.length;
// Build a 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--) {
// Move the current root to the end
int temp = arr[0];
arr[0] = arr[i];
arr[i] = temp;
// Call heapify on the reduced heap
heapify(arr, i, 0);
}  }
private static void heapify(int arr[], int n, int i) {
int largest = i; // Initialize largest as root
int leftChild = 2 * i + 1; // Left child position
int rightChild = 2 * i + 2; // Right child position
// If the left child is larger than the root
if (leftChild < n && arr[leftChild] > arr[largest]) {
largest = leftChild;
}
// If the right child is larger than the largest so far
if (rightChild < n && arr[rightChild] > arr[largest]) {
largest = rightChild;
}
// If the largest is not the 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);
}  }
public static void printArray(int arr[]) {
int n = arr.length;
for (int i = 0; i < n; ++i) {
System.out.print(arr[i] + " ");
}
System.out.println();
}
public static void main(String args[]) {
int arr[] = { 12, 11, 13, 5, 6, 7 };
int n = arr.length;
System.out.println("Original array:");
printArray(arr);
heapSort(arr);
System.out.println("Sorted array:");
printArray(arr);
} }

This program defines a HeapSort class with methods for performing the heap sort algorithm. In the main method, an example array is sorted using the heapSort method, and the sorted result is printed. Heap Sort is an efficient comparison-based sorting algorithm that uses a binary heap data structure to sort elements in ascending or descending order.

Python Program Using Heap Sort Algorithm

def heapify(arr, n, i):
largest = i # Initialize largest as the root
left_child = 2 * i + 1 # Left child position
right_child = 2 * i + 2 # Right child position
# If the left child is larger than the root
if left_child < n and arr[left_child] > arr[largest]:
largest = left_child
# If the right child is larger than the largest so far
if right_child < n and arr[right_child] > arr[largest]:
largest = right_child
# If the largest is not the root
if largest != i:
arr[i], arr[largest] = arr[largest], arr[i] # Swap the root and largest
heapify(arr, n, largest) # Recursively heapify the affected sub-tree
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 from the heap one by one
for i in range(n - 1, 0, -1):
arr[i], arr[0] = arr[0], arr[i] # Swap the current root with the last element
heapify(arr, i, 0) # Call heapify on the reduced heap
# Example usage
arr = [12, 11, 13, 5, 6, 7]
print("Original array:", arr)
heap_sort(arr)
print("Sorted array:", arr)

This Python program defines the heapify function to maintain the max-heap property and the heap_sort function to perform the heap sort algorithm. It then demonstrates the heap sort algorithm by sorting an example array and printing the sorted result. Heap sort is an efficient comparison-based sorting algorithm that uses a binary heap data structure to sort elements in ascending or descending order.

Javascript Program Using Heap Sort Algorithm

function heapify(arr, n, i) {
let largest = i; // Initialize largest as root
const leftChild = 2 * i + 1; // Left child position
const rightChild = 2 * i + 2; // Right child position
// If the left child is larger than the root
if (leftChild < n && arr[leftChild] > arr[largest]) {
largest = leftChild;
}
// If the right child is larger than the largest so far
if (rightChild < n && arr[rightChild] > arr[largest]) {
largest = rightChild;
}
// If the largest is not the root
if (largest !== i) {
[arr[i], arr[largest]] = [arr[largest], arr[i]]; // Swap the root and largest
heapify(arr, n, largest); // Recursively heapify the affected sub-tree
}  }
function heapSort(arr) {
const n = arr.length;
// Build a max heap
for (let i = Math.floor(n / 2) - 1; i >= 0; i--) {
heapify(arr, n, i);
}
// Extract elements from the heap one by one
for (let i = n - 1; i > 0; i--) {
[arr[0], arr[i]] = [arr[i], arr[0]]; // Swap the current root with the last element
heapify(arr, i, 0); // Call heapify on the reduced heap
} }
// Example usage
const arr = [12, 11, 13, 5, 6, 7];
console.log("Original array:", arr);
heapSort(arr);
console.log("Sorted array:", arr);

This JavaScript program defines the heapify function to maintain the max-heap property and the heapSort function to perform the heap sort algorithm. It then demonstrates the heap sort algorithm by sorting an example array and printing the sorted result. Heap sort is an efficient comparison-based sorting algorithm that uses a binary heap data structure to sort elements in ascending or descending order.

Refrences

• https://www.javatpoint.com/heap-sort
• https://www.tutorialspoint.com/design_and_analysis_of_algorithms

Suggested Reads!

• AP Algorithm Basics
• What is Algorithm | Introduction to Algorithm