What is HeapSort Algorithm Example and Implementation

In this article we will discuss about HeapShort algorithm, Heap sort is a Heap data structure based comparison sorting technique where we first find the maximum element and place the maximum element at the end. We repeat the same process for remaining elements.

A Binary Heap is a Complete Binary Treewhere items are stored in an order such that the value of each parent node is either greater or smaller than the values of its two children nodes. The former is called as max heap and the latter is called min heap. The heap can be represented by binary tree or array.

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.

As Binary Heap is a Complete Binary Tree, it can be easily represented as an array. If the parent node is stored at index "i", the left child can be calculated by 2 * i + 1 and right child by 2 * i + 2.

The algorithm has two parts, one is to heapify the array and second part is to take last element as sorted and repeat heapify for remaining array. In heapify we starts from the last non-leaf node (calculated by n/2 -1) and check if the heap satisfies (maxHeap or minHeap) properties if not we keep on swapping elements until the targeted part of array (heap) is heapified, we do it recursively.

package com.cd.array.sort;

import java.util.Arrays;
import java.util.stream.Collectors;

public class HeapSort {

	private static int[] arr1 = {4, 10, 3, 5, 1};
	private static int[] arr2 = {12, 11, 13, 5, 6, 7};

	private static void sort(int[] arr, int n) {
		while (n > 0) {
			int lastNonLeaf = (n / 2) - 1;
			for (int i = lastNonLeaf; i >= 0; i--)
				maxHeapify(arr, i, n);
			swap(0, n - 1, arr);
			n--;
		}
	}

	private static void maxHeapify(int[] arr, int elementIndex, int n) {

		if (elementIndex > n - 1)
			return;

		int leftIndex = (elementIndex * 2) + 1;
		int rightIndex = (elementIndex * 2) + 2;

		if (leftIndex < n && arr[leftIndex] > arr[elementIndex]) {
			swap(elementIndex, leftIndex, arr);
			maxHeapify(arr, leftIndex, n);
		}

		if (rightIndex < n && arr[rightIndex] > arr[elementIndex]) {
			swap(elementIndex, rightIndex, arr);
			maxHeapify(arr, rightIndex, n);
		}
	}

	private static void swap(int i, int j, int arr[]) {
		int tmp = arr[i];
		arr[i] = arr[j];
		arr[j] = tmp;
	}

	private static String print(int[] arr) {
		return Arrays.stream(arr).mapToObj(Integer::toString)
				.collect(Collectors.joining(", "));
	}

	public static void main(String[] args) {
		System.out.println("Unsoretd array: " + print(arr1));
		sort(arr1, arr1.length);
		System.out.println("Unsoretd array: " + print(arr1));

		System.out.println();

		System.out.println("Unsoretd array: " + print(arr2));
		sort(arr2, arr2.length);
		System.out.println("Unsoretd array: " + print(arr2));

	}
}
Output: Output of above code will be something like this:


Unsoretd array: 4, 10, 3, 5, 1
Unsoretd array: 1, 3, 4, 5, 10

Unsoretd array: 12, 11, 13, 5, 6, 7
Unsoretd array: 5, 6, 7, 11, 12, 13


Heap sort is an in-place, not stable sorting algorithm having a time complexity is O(nLogn), although there are ways to make heap sort stable.