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:

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=size1; 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]