# 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

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

### 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 …

### 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 …

### 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 …

### 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 …

### 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 …

### 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 …