# Heap Sort Algorithm

July 03, 2019

This is another very useful sorting algorithm based on Heap data structure. Read more about Heap Data Structure

In this algorithn, we first prepare heap which satisfies max-heap property. Once we get out max heap ready. We get maximum element at the top. We swap this element with the last index element. And, reduce heapsize by one. Now, since we have put a newer element on top. We will just run max_heapify() algorithm on this array with new heapsize.

Finally we get the sorted array.

## Heap Sort Algorithm

• Build a max heap (using max_heapify())
• In a loop starting from last index
• swap 0-index value with current index value (which is the last index in our heap)
• reduce heap size by one. Means, largest element is done. Lets work on remaining array.
• Run max_heapify() on 0-index

See the code here:

``````public class HeapSort {
private int[] arr;
private int heapsize;

public HeapSort(int[] arr) {
this.arr = arr;
this.heapsize = this.arr.length;
}

private int getLeftChild(int index) {
return (index * 2) + 1;
}
private int getRightChild(int index) {
return (index * 2) + 2;
}

private void max_heapify(int index) {
int l = this.getLeftChild(index);
int r = this.getRightChild(index);

int indexOfLargest = index;
if (l < this.heapsize && this.arr[l] > this.arr[index]) {
indexOfLargest = l;
}

if (r < this.heapsize && this.arr[r] > this.arr[indexOfLargest]) {
indexOfLargest = r;
}

if (indexOfLargest != index) {
ArrayUtils.swap(this.arr, index, indexOfLargest);
this.max_heapify(indexOfLargest);
}
}

private void buildMaxHeap() {
for (int i=this.heapsize/2; i>=0; i--) {
this.max_heapify(i);
}
}

public void doHeapSort() {
this.buildMaxHeap();
int l = this.arr.length;
for (int i=l-1; i>0; i--){
ArrayUtils.swap(this.arr, 0, i);
this.heapsize--;

this.max_heapify(0);
}
}
}``````

## Key Points

• This is an in-place algorithm.
• Uses Heap data structure
• Performance is very good. its complexity is O(n log n)

## Runtime complexity

The algorithm runs on O(n log n) in worst/average case.

## Similar Posts

### Three Sum Closest - Leet Code Solution

Problem Statement Given an array nums of n integers and an integer target, find…

### Find if Array contains Duplicate Number - Leet Code Solution

Problem Statement Given an array of integers, find if the array contains any…

### How to prepare for your next Coding Interview

Here are some tips while preparing for your coding interviews. 1. Do study or…

### Leetcode - Rearrange Spaces Between Words

Problem Statement You are given a string text of words that are placed among…

### Find the maximum sum of any continuous subarray of size K

Introduction You are given an array of integers with size N, and a number K…

## Latest Posts

### Python SMTP Email Code - How to Send HTML Email from Python Code with Authentication at SMTP Server

Introduction This post has the complete code to send email through smtp server…

### Python SMTP Email Code - Sender Address Rejected - Not Owned By User

Introduction In a normal email sending code from python, I’m getting following…

### Nodejs with MongoDB - Number of Opened Connections Keep on Increasing with Mongoose Library

Introduction In one of my app, I was using to talk to . I have used some event…

### Django Python - How to Build Docker Image and Run Web-service on Apache with Python 3.9

Introduction So you have a Django project, and want to run it using docker image…

### Python - How to Maintain Quality Build Process Using Pylint and Unittest Coverage With Minimum Threshold Values

Introduction It is very important to introduce few process so that your code and…

### Example Jenkin Groovy Pipeline Script for Building Python Projects with Git Events and Push to Artifactory

Introduction In this post, we will see a sample Jenkin Pipeline Groovy script…