# Heap Sort Algorithm

7 September 2023This 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!**

Hey there, I’m Anshul Pal, a tech blogger and Computer Science graduate. I’m passionate about exploring tech-related topics and sharing the knowledge I’ve acquired. With two years of industry expertise in blogging and content writing, I’m also the co-founder of HVM Smart Solution. Thanks for reading my blog – Happy Learning!