# Heap Sort – Java Implementation

What is Heap Sort??

• Heap sort is comparison based sorting algorithm.
• Heap sort is considered as improved selection sort, it divides the input into sorted and unsorted region.
• The improvement from selection sort is to use Heap Data Structure instead of using linear search algorithm to reduce of the time complexity.

Pre-requisite:

Binary Heap (min and max heap)

What is Binary Heap??

Heap is a tree based data structure which satisfies the two properties

Shape Property: Heap data structure is always a Complete Binary Tree. The Complete Binary tree is a binary tree which is completely filled (means all the nodes has 2 children) except the last level which might not be completely full.

Heap Property: All nodes are either greater than equal to (Max-Heap) or less than equal to (Min-Heap) to each of its child nodes. This is called heap property.

How Heap Sort Algorithm works???

• Sorting in ascending order:
1. Create a max Heap from the given input array.
2. Extract the root (it will be the maximum value in array) and replace it with the last element in the array.
3. Heapify the root of the heap.
4. Repeat the steps b and c till entire array is sorted.
• Sorting in descending order
1. Create a min Heap from the given input array.
2. Extract the root (it will be the minimum value in array) and replace it with the last element in the array.
3. Heapify the root of the heap.
4. Repeat the steps b and c till entire array is sorted.

Time Complexity: O(nLogn)

See the video below for more understanding

Complete Java Code for Heap Sort:

This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.

 import java.util.Arrays; public class HeapSort { public void sort(int arrA[]) { int size = arrA.length; // Build heap for (int i = size / 2 – 1; i >= 0; i—) heapify(arrA, size, i); // One by one extract (Max) an element from heap and // replace it with the last element in the array for (int i=size–1; i>=0; i—) { //arrA[0] is a root of the heap and is the max element in heap int x = arrA[0]; arrA[0] = arrA[i]; arrA[i] = x; // call max heapify on the reduced heap heapify(arrA, i, 0); } } // To heapify a subtree with node i void heapify(int arrA[], int heapSize, int i) { int largest = i; // Initialize largest as root int leftChildIdx = 2*i + 1; // left = 2*i + 1 int rightChildIdx = 2*i + 2; // right = 2*i + 2 // If left child is larger than root if (leftChildIdx < heapSize && arrA[leftChildIdx ] > arrA[largest]) largest = leftChildIdx ; // If right child is larger than largest so far if (rightChildIdx < heapSize && arrA[rightChildIdx ] > arrA[largest]) largest = rightChildIdx ; // If largest is not root if (largest != i) { int swap = arrA[i]; arrA[i] = arrA[largest]; arrA[largest] = swap; // Recursive call to heapify the sub-tree heapify(arrA, heapSize, largest); } } public static void main(String args[]) { int arrA[] = {9, 10, 5, 3, 1, 2, 6}; System.out.println("Original array is: " + Arrays.toString(arrA)); HeapSort heapSort = new HeapSort(); heapSort.sort(arrA); System.out.println("Sorted array is (Heap Sort): " + Arrays.toString(arrA)); } }

view raw

HeapSort.java

hosted with ❤ by GitHub

Output:

```Original array is: [9, 10, 5, 3, 1, 2, 6]
Sorted array is (Heap Sort): [1, 2, 3, 5, 6, 9, 10]
```

This site uses Akismet to reduce spam. Learn how your comment data is processed.