Heap Sort in Java3 min read

In this tutorial, we will learn how to implement Heap Sort in java. First, we will start by understanding the Heap Sort algorithm.

Heap Sort Algorithm

Heap is a tree in heap sorting that possesses some specific properties whose value should be greater than or equal to that of the children node.

Heapsort 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
Binary heap

Types of heaps:

  • Min heap
  • Max heap

Min heap and max heap are the binary heaps that represent 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.

A 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.

A 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.

Before we begin, you need to have an idea of the following:

Time Complexity of Heap Sort:

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

Java Program to implement heap sort

The output of Heap sorting in Java:


MORE

String Pattern Programs in C

In this tutorial, we will write various C pattern programs for String. Before that, you may go through the following topics in C. for loop …
Read More

Java Program to Find pair of Integers in Array whose sum is given Number

In this tutorial, we will write a program to find a pair of elements from an array whose sum equals a given number in java …
Read More

Program to Print Diamond Alphabet Patterns in C

In this tutorial, we will learn to write a C program to print Diamond patterns using alphabets/characters. However, in this tutorial, we will create a …
Read More

Half Diamond Pattern in C using Alphabets

In this tutorial, we will learn and code the half diamond alphabet patterns in C programming language. However, in this tutorial, we will create a …
Read More

Half Pyramid of Alphabets in C

In this tutorial, we will learn and code alphabet patterns in C programming language specifically the Half pyramid of alphabets in C programming. However, in …
Read More

Inverted Half Pyramid Pattern of Alphabets in C

In this tutorial, we will write a C program to print half Pyramid using alphabets/characters. Before that, you may go through the following topic in …
Read More