In this article, we will be discussing Heap Sort program in C, C++ and Java with examples. Heap sort algorithm implementation, Heap sort pseudocode, time complexity, etc are also discussed in this article.
Prerequisites: Merge Sort, Insertion Sort
Before we get into Heap sort, let’s understand what a Heap data structure is.
Heap is a special kind of binary tree in which elements are stored in a hierarchical manner. Heap has some additional rules it must always have a heap structure, where all the levels of the binary tree are filled up from left to right. Second, it must either be ordered as a max heap or a min-heap.
In Heap sort, we will be dealing with Max heap. Using max heaps, we can sort an unsorted array of elements. In simple, this is how it works
Lets see how sorting takes place with the help of heap.Consider an array arr[] = {4, 3, 7, 1, 8, 5}
1) Firstly, lets convert the given array to a binary tree.The representation of a binary tree for the given array looks as shown below.
2) Next, build max-heap from the above tree. A max tree is where all the parent nodes are of higher value than the children nodes.
3) Now, swap the root node with the last element of the heap node. This means largest value has moved to its correct position. So, remove the largest value from the tree. After removing, the tree looks as shown below.
4) Repeat step 3 until no elements are left in the heap
Here is the implementation of Heap sort in various languages.
@@coding::1@@
To calculate the time complexity of heap sort, let us first try to break down & understand the time-complexities of individual functions.
Since Heap sort runs in linearithmic time, the combination of these two-time complexities is O(n logn) and hence the time complexity of Heap sort is O(n logn).
Check out more Data Structure Questions