Heap sort in java

In this post, we will see how to implement heap sort in java.
I will divide heap sort in multiple parts to make it more understandable.

What is heap?

A heap is a tree with some special properties, so value of node should be greater than or equal to(less than or equal to in case of min heap) children of the node and tree should be complete binary tree.

Binary heaps

Binary heaps are those heaps which can have up to 2 children. We will use binary heaps in our next few sections.

Understanding complete binary tree

Complete binary tree is a binary tree whose leaves are at h or h-1 level where h is height of the tree.
Index of left child= 2*(index of its parent)+1
Index of right child= 2*(index of its parent)+2

Complete Binary tree

Types of heaps

There are two types of heap.
  • Max heap
  • Min heap

Max heap : It is binary heap where value of node is greater than left and right child of the node.

Min heap : It is binary heap where value of node is lesser than left and right child of the node.

Heapifying an element:

Once we create a heap , it may not satisfy heap property. In order to make it heap again, we need to adjust locations of the heap and this process is known as heapifying the elements.
In order to create a max heap, we will compare current element with its children and find the maximum, if current element is not maximum then exchange it with maximum of left or right child.

Heapifying elements

Java code for heapifying element at location i :

Steps for heap sort

  • Represent array as complete binary tree.
    • Left child will be at 2*i+1 th location
    • Right child will be at 2*i+2 th location.
  • Build a heap.
    • All the leaf nodes already satisfy heap property, so we don’t need to heapify them.
    • Last leaf node will be present at (n-1)th location, so parent of it will be at (n-1)/2 th location, hence (n-1)/2 will be location of last non leaf node.
    • Iterate over non leaf nodes and heapify the elements.
  • After building a heap, max element will be at root of the heap. We will exchange it with (n-1)th location, so largest element will be at proper place and remove it from the heap by reducing size of n.
  • When you exchange largest element, it may disturb max heap property, so you need to again heapify it.
  • Once you do above steps until no elements left in heap, you will get sorted array in the end.

Java code for heap sort

When you run above program, you will get below output:

Before Heap Sort :
[1, 10, 16, 19, 3, 5] =====================
After Heap Sort :
[1, 3, 5, 10, 16, 19]

Time and space complexity

Time Complexity:
Best case : O(nlogn)
Average case : O(nlogn)
Worst case : O(nlogn)

space complexity:
Since heap sort is inplace sorting algorithm, space complexity is o(1). You don’t need any extra space except swapping variable in heap sort.

Related Posts

  • 04 November

    Topological Sort in java

    Table of ContentsTopological Sort exampleTopological Sort AlgorithmWhy it works?Java program to implement topological sortingTime Complexity In this post, we will see about Topological Sorting in the graph. Topological Sorting is ordering of vertices or nodes such if there is an edge between (u,v) then u should come before v in topological sorting. Topological sort is […]

  • 23 August

    Sort array in java

    Table of ContentsJava Sort ArraySort Array of numbersSort Array of StringsSort array of custom objects In this post, we will see how to sort an array in java. There are various ways to sort array in java. You can implement different sorting algorithms to sort an array. You can use Arrays.sort method to sort array […]

  • 12 October

    Selection sort in java

    Table of ContentsSelection sort algorithmSelection sort algorithmTime complexity If you want to practice data structure and algorithm programs, you can go through data structure and algorithm interview programs. Selection sort is an in place comparison sorting algorithm. It is very simple to implement but it does not go well with large number of inputs. Selection sort […]

  • 12 October

    Shell sort in java

    Shell sort is in place comparison based sorting algorithm. It is generalization of insertion sort. It was invented by Donald shell. It allows to sort elements which are far apart. In case of insertion sort, comparison happens between only adjacent elements but in shell sort, it avoid comparing adjacent elements until last steps. Last step of shell […]

  • 12 October

    Quick Sort in java

    Table of ContentsQuick sort AlgorithmQuick Sort implementationTime complexity If you want to practice data structure and algorithm programs, you can go through data structure and algorithm interview questions. Quick sort or partition-exchange sort, is a sorting algorithm, which is using divide and conquer algorithm. In quick sort, we first choose a pivot and divide into two sublists,one […]

  • 12 October

    Counting Sort in java

    Table of ContentsSteps for Counting Sort:Java program for counting sort: Counting sort is special sorting technique used to sort elements between specific range. Lets say elements belong to range 1 to K , then Counting sort can be used to sort elements in O(N) times. Basic idea of counting sort to find number of elements […]

Comments

Leave a Reply

Your email address will not be published. Required fields are marked *

Subscribe to our newletter

Get quality tutorials to your inbox. Subscribe now.