# Heap Sort Algorithm in Java

[2061 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:

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

#### Heap Sort algorithm steps:

1. Build max-heap from unordered array
2. Find max element in Array A, A[n]
3. Swap this element A[n] from A, now max element is at the end of array
4. Now discard the node 'n' from the heap by decrementing heap size
5. 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)

## Struggling to Understand Algorithm and Flowchart? Try our Notes

#### Want to Test Your Knowledge on Algorithm and Flowchart?

##### Play 2048 Game Online and Relax. 