|
| 1 | +# Heap Sort |
| 2 | + |
| 3 | +#### Problem Statement |
| 4 | + |
| 5 | +Given an unsorted array of n elements, write a function to sort the array |
| 6 | + |
| 7 | +#### Approach |
| 8 | + |
| 9 | +- Build a max heap from the input data. |
| 10 | +- 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. |
| 11 | +- Repeat above steps while size of heap is greater than 1. |
| 12 | + |
| 13 | +#### Time Complexity |
| 14 | + |
| 15 | +O(n log n) Worst case performance |
| 16 | + |
| 17 | +O(n log n) (distinct keys) |
| 18 | +or O(n) (equal keys) Best-case performance |
| 19 | + |
| 20 | +O(n log n) Average performance |
| 21 | + |
| 22 | +#### Space Complexity |
| 23 | + |
| 24 | +O(1) Worst case auxiliary |
| 25 | + |
| 26 | + |
| 27 | +#### Example |
| 28 | + ``` |
| 29 | +Input data: 4, 10, 3, 5, 1 |
| 30 | + 4(0) |
| 31 | + / \ |
| 32 | + 10(1) 3(2) |
| 33 | + / \ |
| 34 | + 5(3) 1(4) |
| 35 | +
|
| 36 | +The numbers in bracket represent the indices in the array |
| 37 | +representation of data. |
| 38 | +
|
| 39 | +Applying heapify procedure to index 1: |
| 40 | + 4(0) |
| 41 | + / \ |
| 42 | + 10(1) 3(2) |
| 43 | + / \ |
| 44 | +5(3) 1(4) |
| 45 | +
|
| 46 | +Applying heapify procedure to index 0: |
| 47 | + 10(0) |
| 48 | + / \ |
| 49 | + 5(1) 3(2) |
| 50 | + / \ |
| 51 | + 4(3) 1(4) |
| 52 | +The heapify procedure calls itself recursively to build heap |
| 53 | + in top down manner. |
| 54 | + ``` |
| 55 | + |
| 56 | + |
| 57 | + |
| 58 | +#### Code Implementation Links |
| 59 | + |
| 60 | +- [Java](https://github.com/TheAlgorithms/Java/blob/master/Sorts/HeapSort.java) |
| 61 | +- [C++](https://github.com/TheAlgorithms/C-Plus-Plus/blob/master/Sorting/Heap%20Sort%20.cpp) |
| 62 | +- [Python](https://github.com/TheAlgorithms/Python/blob/master/sorts/heap_sort.py) |
| 63 | +- [Go](https://github.com/TheAlgorithms/Go/blob/master/sorts/Heapsort.go) |
| 64 | +- [Ruby](https://github.com/TheAlgorithms/Ruby/blob/master/Sorting/heap_sort.rb) |
| 65 | +- [C-sharp](https://github.com/TheAlgorithms/C-Sharp/blob/master/sorts/heap_sort.cs) |
| 66 | +- [C](https://github.com/TheAlgorithms/C/blob/master/sorting/HeapSort.c) |
| 67 | +- [Javascript](https://github.com/TheAlgorithms/Javascript/blob/master/Sorts/heapSort.js) |
| 68 | + |
| 69 | + |
| 70 | +#### Video Explanation |
| 71 | + |
| 72 | +[A video explaining the Selection Sort Algorithm](https://www.youtube.com/watch?v=MtQL_ll5KhQ) |
0 commit comments