# Heap Sort

HeapSort, is a comparison based sorting technique based on Binary Heap data structure. It is similar to selection sort where we first find the maximum element and place the maximum element at the end. We repeat the same process for remaining element.

### Heap Sort Algorithm for sorting in increasing order:

- Build a max heap from the input data.
- At this point, the largest item is stored at the root of the heap. Replace it with the last item of the heap followed by reducing the size of heap by 1. Finally, heapify the root of tree.
- Repeat above steps while size of heap is greater than 1.

if `i`

is the index of the current node, then

1 2 3 4 |
Parent(i) = floor((i-1) / 2) where floor functions map a real number to the smallest leading integer. LeftChild(i) = 2*i + 1 RightChild(i) = 2*i + 2 |

The `buildheap()`

operation is run once, and is`O(n)`

in performance. The heapify() function is `O(log n)`

, and is called n times. Therefore, the performance of this algorithm is `O(n + n log n) = O(n log n)`

.

## Code

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 |
public class HeapSort { public void sort(int[] arr) { buildheap(arr); for(int i=arr.length-1;i>=0;i--) { int temp = arr[0]; arr[0] = arr[i]; arr[i] = temp; heapify(arr,i,0); } } public void buildheap(int[] arr) { int n = arr.length; for(int i=(n/2 -1);i>=0;i--) { heapify(arr, n, i); } } public void heapify(int[] arr, int n, int i) { int largest = i; int left = i * 2 + 1 ;//left child int right = i * 2 + 2 ;//right child if(left<n&&arr[left]>arr[largest]) { largest = left; } if(right<n&&arr[right]>arr[largest]) { largest = right; } //swap if(largest!=i) { int temp = arr[i]; arr[i] = arr[largest]; arr[largest] = temp; heapify(arr, n, largest); } } |