Implementing HeapSort in C++
-
Given a random array of N numbers, convert it into a heap.
-
The null nodes are indicated by -1 and the null nodes are located at any place in the array. Make this into a heap.
-
Sort the heap using HeapSort
-
Display the array after the heap is converted from the array and after HeapSort.
Algorithm:
The algorithm for the given problem statement goes as follows: Note: The implemented heap is a Max Heap
- In the first step, the array is filtered and the null nodes are removed and stored in an array called heap[].
After that, the value property of heap is maintained, by using Floyd’s method for building a heap.
Start from the n/2nd element and compare the values of both its children
Case 1: When the parent value is greater than both its children, continue Case 2: When the parent is smaller than right (or) left child Case 3: When the parent is smaller than both its children
- After the cases, decrease n by 1 and continue till n = 1 Use a function check() and start from the first element upto the middle and check the value of all children of a given node.
For HeapSort,
- Swap the 1st element and the a[0]th element of the array Reduce the value of a[0] Call the check() function Repeat until a[0] is 1
The final array produced will be sorted in ascending order.