Heap Sort in Java3 min read

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 a 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:

Also, learn,
Bubble Sort
Heap Sort
Insertion Sort
Quick Sort
Merge Sort
shell Sort