Heap Sort in Java

Introduction

This tutorial explains the Heap Sort algorithm with an example list of 7 numbers. It covers, in this order, what a heap is and how it is stored in an array, what Heap Sort is, how the heapify operation works, a step-by-step walkthrough of the sort, its Java implementation with an explanation of the code, how Java's PriorityQueue is related to it, and the Big Oh complexity of the algorithm.

What is a heap

A heap is a binary tree with two properties -
  • It is a complete binary tree, i.e. every level of the tree is full, except possibly the last level, which is filled from left to right.
  • In a max-heap every parent is greater than or equal to its children. The largest item is thus always at the top, or root, of the tree. (In a min-heap every parent is smaller than or equal to its children, and the smallest item is at the root.)
Because the tree is complete, it can be stored in an array without any gaps, level by level. No links between the items are needed, as the positions can be calculated. For the item at index i -
  • its left child is at index 2*i + 1
  • its right child is at index 2*i + 2
  • its parent is at index (i - 1) / 2
A max-heap shown as a tree and as an array - the root 10000 has the children 10 and 100, 10 has the children 1 and 5, and 100 has the children 50 and 25; stored level by level the array is 10000, 10, 100, 1, 5, 50, 25, and the children of the item at index i are at the indexes 2i+1 and 2i+2

What is Heap Sort

Heap Sort is an in-place sorting algorithm which uses a max-heap to find the largest item again and again. It works in two stages -
  1. Building the max-heap - the items of the list are rearranged, inside the list itself, so that they form a max-heap. The largest item is now the first item of the list.
  2. Sorting - the first item, i.e. the largest, is swapped with the last item of the heap. It is now in its correct sorted position, and the heap becomes smaller by one item. The item which came to the root is moved down until the remaining items form a max-heap again. This is repeated until the heap has just one item left.
Like in Selection SortClick to read: Selection Sort, the list consists of an unsorted part, which here is the heap, and a sorted sub-list which grows from the end of the list. The difference is that Selection Sort searches through all the unsorted items to find the next one, while the heap provides it at the root.

How heapify works

Both the stages of Heap Sort use the same operation, known as heapify (or sift-down). Heapify is given a parent whose two sub-trees are already heaps, but which may itself be smaller than its children. It works as follows -
  1. The parent is compared with its left child and its right child, and the largest of the three is found.
  2. If the parent is the largest, nothing needs to be done.
  3. Otherwise the parent is swapped with the larger child. The item which has moved down may again be smaller than its new children, so heapify is repeated from its new position.
Heapify moving the item 25 down from the root - 25 is compared with its children 10 and 100 and swapped with the larger one, 100; at its new position it is compared with its child 50 and swapped again; the tree with 100 at the root is a max-heap again

Heap Sort's working explained

Lets understand the working of Heap Sort using an example. Lets say the list to be sorted is [10, 5, 100, 1, 10000, 50, 25].

Stage 1 - Building the max-heap
The items in the second half of the list are the leaves of the tree. They have no children, so each of them is a heap already. Heapify is thus called only for the parents, starting from the last parent, which is at index 2, and going backwards to the root at index 0.

Heapify at index 2
The item at index 2 is 100. Its children are 50 and 25, both smaller than 100. Nothing changes.

Heapify at index 1
The item at index 1 is 5. Its children are 1 and 10000. The larger child, 10000, is swapped with 5. The list is now [10, 10000, 100, 1, 5, 50, 25].

Heapify at index 0
The item at index 0 is 10. Its children are 10000 and 100. The larger child, 10000, is swapped with 10. The item 10, now at index 1, is greater than its children 1 and 5, so it stays there. The list is now [10000, 10, 100, 1, 5, 50, 25], which is a max-heap.

Stage 2 - Sorting
First pass
The root, 10000, is swapped with the last item of the heap, 25. 10000 is now in its correct place at the end of the list, and the heap is one item smaller. Heapify moves 25 down from the root: it is swapped with 100, and then with 50. At the end of the pass the heap is [100, 10, 50, 1, 5, 25] and the sorted sub-list is [10000].

Second pass
The root, 100, is swapped with the last item of the heap, 25, and heapify moves 25 down again. At the end of the pass the heap is [50, 10, 25, 1, 5] and the sorted sub-list is [100, 10000].

Further passes
In this way, with every pass the largest item of the heap is moved to the head of the sorted sub-list and the heap is repaired. After exactly n-1 passes, i.e. 6 passes for this list, a single item remains in the heap, and the whole list is sorted.

The passes of heap sort on the list 10, 5, 100, 1, 10000, 50, 25 - after building the max-heap the list is 10000, 10, 100, 1, 5, 50, 25; with every pass the heap part on the left becomes one item smaller and the sorted part on the right one item larger, until the list is 1, 5, 10, 25, 50, 100, 10000

Heap Sort implemented in Java

Heap Sort Algorithm implemented in Java
package com.javabrahman.algorithms.sorts;
public class HeapSort {
  static int intArray[] = { 10, 5, 100, 1, 10000, 50, 25 };

  public static void doSort() {
    int size = intArray.length;
    //build the max-heap
    for (int parent = size / 2 - 1; parent >= 0; parent--) {
      heapify(size, parent);
    }
    //move the largest item to the end, and repair the heap
    for (int last = size - 1; last > 0; last--) {
      swap(0, last);
      heapify(last, 0);
    }
  }

  public static void heapify(int heapSize, int parent) {
    int largest = parent;
    int left = 2 * parent + 1;
    int right = 2 * parent + 2;
    if (left < heapSize && intArray[left] > intArray[largest]) {
      largest = left;
    }
    if (right < heapSize && intArray[right] > intArray[largest]) {
      largest = right;
    }
    if (largest != parent) {
      swap(parent, largest);
      heapify(heapSize, largest);
    }
  }

  public static void swap(int first, int second) {
    int temp = intArray[first];
    intArray[first] = intArray[second];
    intArray[second] = temp;
  }

  public static void printArray() {
    for (int i = 0; i < intArray.length; i++) {
      System.out.print(" " + intArray[i]);
    }
  }

  public static void main(String args[]) {
    System.out.print("Array Before Sorting->");
    printArray();
    doSort();
    System.out.print("\nArray After Sorting ->");
    printArray();
  }
}
 OUTPUT of the above code
Array Before Sorting-> 10 5 100 1 10000 50 25
Array After Sorting -> 1 5 10 25 50 100 10000

Explanation of the code

  • The doSort() method holds the two stages of the sorting logic.
  • The first loop builds the max-heap. Its counter parent starts from size / 2 - 1, which is the index of the last item that has a child, and goes backwards to 0, calling heapify() for every parent.
  • The second loop represents the passes. Its counter last is the index of the last item of the heap. In every pass the root at index 0 is swapped with the item at last, and heapify() is called for the root with the heap size reduced to last, so that the items already sorted are left untouched.
  • The heapify() method finds the largest among the parent, its left child and its right child. The conditions left < heapSize and right < heapSize take care of parents which have just one child or none. If a child is the largest, it is swapped with the parent, and heapify() calls itself recursively for the position the parent has moved to.
  • The main() method orchestrates the sorting.
  • The instance element intArray[] holds the list to be sorted.

Heap Sort's steps as printed by the program

To see the steps which were described in the walkthrough above, the next program prints the list after every call to heapify() while building the heap, and the heap and the sorted sub-list after every pass. The sorting logic is the same as before.
Heap Sort printing every step
package com.javabrahman.algorithms.sorts;
import java.util.Arrays;
public class HeapSortTrace {
  static int intArray[] = { 10, 5, 100, 1, 10000, 50, 25 };

  public static void doSort() {
    int size = intArray.length;
    for (int parent = size / 2 - 1; parent >= 0; parent--) {
      heapify(size, parent);
      System.out.println("Heapify at index " + parent + " -> " + Arrays.toString(intArray));
    }
    System.out.println("Max-heap is built   -> " + Arrays.toString(intArray));
    for (int last = size - 1; last > 0; last--) {
      swap(0, last);
      heapify(last, 0);
      System.out.println("Pass " + (size - last) + ": heap " + Arrays.toString(Arrays.copyOfRange(intArray, 0, last))
          + " sorted " + Arrays.toString(Arrays.copyOfRange(intArray, last, size)));
    }
  }

  public static void heapify(int heapSize, int parent) {
    int largest = parent;
    int left = 2 * parent + 1;
    int right = 2 * parent + 2;
    if (left < heapSize && intArray[left] > intArray[largest]) {
      largest = left;
    }
    if (right < heapSize && intArray[right] > intArray[largest]) {
      largest = right;
    }
    if (largest != parent) {
      swap(parent, largest);
      heapify(heapSize, largest);
    }
  }

  public static void swap(int first, int second) {
    int temp = intArray[first];
    intArray[first] = intArray[second];
    intArray[second] = temp;
  }

  public static void main(String args[]) {
    System.out.println("Array Before Sorting -> " + Arrays.toString(intArray));
    doSort();
    System.out.println("Array After Sorting  -> " + Arrays.toString(intArray));
  }
}
 OUTPUT of the above code
Array Before Sorting -> [10, 5, 100, 1, 10000, 50, 25]
Heapify at index 2 -> [10, 5, 100, 1, 10000, 50, 25]
Heapify at index 1 -> [10, 10000, 100, 1, 5, 50, 25]
Heapify at index 0 -> [10000, 10, 100, 1, 5, 50, 25]
Max-heap is built   -> [10000, 10, 100, 1, 5, 50, 25]
Pass 1: heap [100, 10, 50, 1, 5, 25] sorted [10000]
Pass 2: heap [50, 10, 25, 1, 5] sorted [100, 10000]
Pass 3: heap [25, 10, 5, 1] sorted [50, 100, 10000]
Pass 4: heap [10, 1, 5] sorted [25, 50, 100, 10000]
Pass 5: heap [5, 1] sorted [10, 25, 50, 100, 10000]
Pass 6: heap [1] sorted [5, 10, 25, 50, 100, 10000]
Array After Sorting  -> [1, 5, 10, 25, 50, 100, 10000]
The output shows the three calls of heapify which build the max-heap, followed by the 6 passes. In every pass the first item of the heap is the largest of the items which are still unsorted.

Heap Sort and Java's PriorityQueue

Java has a ready-made heap in the class java.util.PriorityQueue. It is a min-heap stored in an array, in the same way as described above: its add() method places a new item in the heap, and its poll() method removes the smallest item from the root and repairs the heap. Adding all the items of a list to a PriorityQueue and removing them one by one thus gives them in sorted order.
Sorting with java.util.PriorityQueue
package com.javabrahman.algorithms.sorts;
import java.util.PriorityQueue;
public class HeapSortWithPriorityQueue {
  public static void main(String args[]) {
    int intArray[] = { 10, 5, 100, 1, 10000, 50, 25 };
    PriorityQueue<Integer> heap = new PriorityQueue<>();
    for (int item : intArray) {
      heap.add(item);
    }
    System.out.println("Head of the queue -> " + heap.peek());
    System.out.print("Items as removed  ->");
    while (!heap.isEmpty()) {
      System.out.print(" " + heap.poll());
    }
  }
}
 OUTPUT of the above code
Head of the queue -> 1
Items as removed  -> 1 5 10 25 50 100 10000

Explanation of the PriorityQueue code

  • The peek() method returns the item at the root of the heap without removing it. As it is a min-heap, this is the smallest item, 1.
  • Every call to poll() removes the smallest of the remaining items, so the items come out in ascending order.
  • This way of sorting is not in-place. The PriorityQueue holds a copy of all the items in its own array. Heap Sort avoids the extra space by building the heap inside the list which is being sorted.

Big Oh Complexity of Heap Sort Algorithm

The number of levels in a heap of n items is about log n. Heapify moves an item down by one level at a time, so one call to heapify takes at the most O(log n) time.
  • Building the max-heap calls heapify for n/2 parents. Most of these parents are near the bottom of the tree and can move down by only one or two levels, and the whole stage takes O(n) time.
  • Sorting has n-1 passes, each with one call to heapify from the root, which takes O(n log n) time.
  • The complexity of Heap Sort is thus O(n log n). Unlike Quick SortClick to read tutorial: Quick Sort in Java, this holds for the best, the average and the worst case, as it does not depend on the order of the items in the list.
  • Space - Heap Sort is in-place and does not need a second list. The recursive heapify() shown here uses O(log n) space on the call stack, which can be avoided by writing it as a loop.
  • Stability - Heap Sort is not a stable sort. Two items with equal values may not remain in their original order, as items are swapped between the root and the end of the heap.
Even though its worst case is better, Heap Sort is usually slower than Quick Sort in practice, as it moves items between positions that are far apart in the list.

Summary

In this tutorial on Heap Sort algorithm in Java we understood what a max-heap is and how it is stored in an array, how the heapify operation repairs a heap, went through a step-by-step walkthrough of building the heap and sorting a 7-number list, saw the Java code for Heap Sort along with its explanation, saw how Java's PriorityQueue is a heap as well, and finally looked at the Big Oh complexity of the algorithm.