Heap Sort in Java

Heap sort in Java uses the data structure binary heap, min-heap, or max heap to do the sorting of elements. Since min-heap always gives the minimum element first, heap sort becomes similar to the selection sort where min-heap is used to sort the array. When max heap is used for sorting purposes, the heap sort resembles bubble sort, as max heap gives the maximum element first.

In this section, we have discussed the max-heap for sorting the elements.

Max Heap Algorithm

Step 1: Build max heap for the given input array using the method heapify().

Step 2: swap the root with the last element of the array. Reduce the size of the heap by 1.

Step 3: Call the heapify() method again to maintain the property of max heap on remaining elements.

Step 4: Repeat steps 3 & 4 till the whole array gets sorted.

Pseudo Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
 
 // Perform the operation heapify-down or down-heap for getting a max-heap
 // arr: an array representing the heap, indexing starting from 0
 // j: represents the index from where heapifying down begins
 Heapify(arr, j):
     leftChild ? 2 * j
     rightChild ? 2 * j + 1
     highest ? j
     if leftChild < size(arr) and arr[leftChild] > A[highest] then:
         highest ? leftChild
     if rightChild < size(arr) and A[rightChild] > A[highest] then:
         highest ? rightChild
     if highest ? j then:
         swap arr[j] and arr[highest]
         Heapify(arr, highest) 
 

Java Program

The following Java program implements the heap sort using the pseudo-code explained above.

FileName: HeapSortExample.java

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
 
 // Java program that uses max heap to do the sorting
 public class HeapSortExample
 {
 public static void maxHeapSort(int a[])
 {
                int size = a.length;
                // rearranging array elements so that it
                // resembles max heap
                for (int j = size / 2 - 1; j >= 0; j--)
                                heapify(a, size, j);
                // One by one extract the top element, which is
                // also the maximum element from the heap
                for (int j = size - 1; j >= 0; j--)
                {
                                // Moving the maximum element of the current heap to the end
                                int tmp = a[0];
                                a[0] = a[j];
                                a[j] = tmp;
                                // invoking method heapify on the reduced heap
                                heapify(a, j, 0);
                }
 }
 // The heapfiy() method does the rearrangement of elements of
 // the given input array to resemble it like a max heap
 // Element present at the index j resembles the root of the max heap
 // length gives the size of the max heap
 static void  heapify(int a[], int length, int j)
 {
                int highest = j; // assign highest as root
                int left = 2 * j + 1; // leftChild = 2 * j + 1
                int right = 2 * j + 2; // rightChild = 2 * j + 2
                // If the root element is smaller the left child
                if (left < length && a[left] > a[highest])
                                highest = left;
                // If the root element so fat is smaller the right child
                if (right < length && a[right] > a[highest])
                                highest = right;
                // If root is not the highest
                if (highest != j)
                {
                                int change = a[j];
                                a[j] = 

Java Tutorial Index

Java Loops

Java Programs

Java Sorting

Java OOPs Concepts

Java Strings

Java Exceptions

Garbage Collection

Multithreading

Java IO

Serialization

Networking

AWT

Swing

Java Collections

Java Generics

Java Annotations

Java JDBC

Java Differences

How to

Java 8 Features

Java 9 Features

Java 12

Java 13

Java 14

Java 15

Java 16

Java 17

Java Math Methods

Java String Methods

Java Conversion

Java Keywords

Java Questions

Misc

Heap Sort in Java

Heap Sort in Java