Heap Sort Algorithm in Java

[5092 views]

Heap as a tree:

An array can be visualized as a nearly complete binary tree.

Properties of this tree:

Root of the tree : First element of the array
Parent of element at index i : element at index i/2
left child of element at index i : element at index 2*i
Right child of element at index i : element at index 2*i+1

Max heap:

In max heap, the parent's value is higher than both of its children.

Heap Operations:

Build_max_heap: Produces a max heap from an unordered array
max_heapify: Correct a single violation of the heap property in a subtree's root

Heap Sort algorithm steps:

Build max-heap from unordered array
Find max element in Array A, A[n]
Swap this element A[n] from A[1], now max element is at the end of array
Now discard the node 'n' from the heap by decrementing heap size
New root may violate the max heap property, but children are max heaps, so run max heapify to fix

Heap Sort Pseudocode Implementation in Java:

public class HeapSort { private static int N; public static void sort(int arr[]){ heapify(arr); for (int i = N; i > 0; i--){ swap(arr,0, i); N = N-1; maxheap(arr, 0); } } public static void heapify(int arr[]){ N = arr.length-1; for (int i = N/2; i >= 0; i--) maxheap(arr, i); } public static void maxheap(int arr[], int i){ int left = 2*i ; int right = 2*i + 1; int max = i; if (left <= N && arr[left] > arr[i]) max = left; if (right <= N && arr[right] > arr[max]) max = right; if (max != i){ swap(arr, i, max); maxheap(arr, max); } } public static void swap(int arr[], int i, int j){ int tmp = arr[i]; arr[i] = arr[j]; arr[j] = tmp; } public static void main(String[] args){ int n, i; System.out.println("Enter number of integer elements"); n = 10; int arr[] = {16, 14, 10, 8, 7, 9, 3, 2, 4, 1}; System.out.println("\nElements before sorting "); for (i = 0; i < n; i++) System.out.print(arr[i]+" "); System.out.println(); sort(arr); System.out.println("\nElements after sorting "); for (i = 0; i < n; i++) System.out.print(arr[i]+" "); System.out.println(); } }

Output:

Heap Sort Algorithm Time Complexity:

Build_max_heap takes O(logn) time
Swapping elements in the array takes O(1) time, but running it for n elements makes it O(n)
We're building max_heap for every element, so its time complexity becomes O(nlogn)