Heap Sort in Java

In this post, we will learn how to implement Heap Sort in java.
Sorting Algorithm in java.

Heap Sort Algorithm

Heap is a tree in heap sorting possess some specific properties whose value should be greater than or equal to that of the children node.
Heap sort is a comparison-based sorting algorithm and is also considered as the improved Selection sort. It is based on Binary Heap data structure so to understand we must know two types of data structure:
Arrays and trees

What is Binary heap?

Complete Binary tree:
A complete binary tree is a binary tree in which every level, except possibly the last, is completely filled, and all nodes are as far left as possible.

Binary Heap:
A binary heap is a complete binary tree where the parent node is greater than its two children node.

Representation of Binary tree:
Considering the height of a tree be “h“, then:

  • Index of left child = 2*(index of its parent)+1
  • Index of right child = 2*(index of its parent)+2

Types of heaps:

  • Min heap
  • Max heap

Min heap and max heap are the binary heap which represents the ordering of an array.

Min heap: In this binary heap, the value of the parent node is always greater than its child node.

Max heap: In this binary heap, the value of the parent node is always less than its child node.

Heap sorting algorithm for increasing order:

  • First, create a max Heap from the input array.
  • Replace the root element (which has the largest element) with the last element in the array. Then heapify the root of the tree.
  • Now repeat the steps until all elements are sorted in an array.

Heap sorting algorithm for decreasing order.

  • First, create a min Heap from the input array.
  • Replace the root element (which has the smallest element) with the last element in the array. Then heapify the root of the tree.
  • Now repeat the steps until all elements are sorted in an array.

Time Complexity of Heap Sort:

Best case:  0(nlogn)
Average case:  0(nlogn)
Worst case:  0(nlogn)

Java code for heap sort

The output of Heap sorting in Java:

Heap sorting in Java

Also, learn,
Bubble Sort in Java