Heap Sort C++

As we know that the C language has a lot of sorting algorithms for sorting array-like structures. One of those sorting techniques is the Heap sort. It is quite popular among C developers because it is considered to be the most efficient when it comes to its working. It is a little different from other sorting techniques because it requires the information of data structure trees along with the concept of arrays. If you have heard and learned about binary trees, then learning Heap sort will be no more a problem for you.

Within heap sort, two types of heaps can be generated, i.e., min-heap and max-heap. The max-heap will sort the binary tree in descending order, while the min-heap will sort the binary tree in ascending order. In other words, the heap will be “max” when the parent node of a child is greater in value and vice versa. So, we have decided to write this article for all those naïve users of C who have no prior knowledge about sorting, especially the heap sort.

Let’s start our today’s tutorial with the Ubuntu 20.04 login to get access to the Linux system. After the login, make use of the shortcut “Ctrl Alt T” or the activity area to open its console application named “Terminal.” We have to utilize the console for making a file for implementation. The command for the creation is a simple one-word “touch” instruction following the new name for a file to be created. We have been naming our c file as “heap.cc”. After the file creation, you need to start implementing the codes in it. For that, you have to open it first through some Linux editors. There are three built-in editors of Linux that can be used for this purpose, i.e., nano, vim, and text. We are using the “Gnu Nano” editor.

<img alt="" data-lazy- data-lazy-src="https://kirelos.com/wp-content/uploads/2022/04/echo/image2-16.png" data-lazy- height="36" src="data:image/svg xml,” width=”351″>

Example # 01:

We will be explaining a simple and quite clear program for heap sort so that our users can understand and learn it well. Use the C namespace and library for input-output at the start of this code. The heapify() function will be called by a “sort()” function for both of its loops. The first “for” loop will call pass it array “A,” n=6, and root=2,1,0 (concerning each iteration) to build a reduced heap.

Using the root value each time, we will get the “largest” variable value is 2,1,0. Then, we will calculate the left “l” and right “r” nodes of the tree using the “root” value. If the left node is greater than “root,” the first “if” will assign “l” to the largest. If the right node is greater than the root, the second “if” will assign “r” to the largest. If “largest” is not equal to the “root” value, the third “if” will swap the “largest” variable value with “root” and call the heapify() function within it, i.e., recursive call. The above-explained whole process will also be used for the max heap when the second “for” loop will be iterated within the sort function.

<img alt="" data-lazy- data-lazy-src="https://kirelos.com/wp-content/uploads/2022/04/echo/image4-14.png" data-lazy- height="271" src="data:image/svg xml,” width=”578″>

The shown-below “sort()” function will be called to sort the values of array “A” in ascending order. The first “for” loop is here; build a heap, or you can say re-arrange array. For this, the value of “I” will be calculated by “n/2-1” and decremented each time after the heapify() function call. If you have a total of 6 values, It will become 2. A total of 3 iterations will be performed, and the heapify function will be called 3 times. The next “for” loop is here to move the current root to the end of an array and call the heapify function 6 times. The swap function will take the value to the current iteration index “A[i]” of an array with the first index value “A[0]” of an array. The heap() function will be called to generate the maximum heap on the already generated reduced heap, i.e., “2,1,0” at first “for” loop.

<img alt="" data-lazy- data-lazy-src="https://kirelos.com/wp-content/uploads/2022/04/echo/image3-15.png" data-lazy- height="125" src="data:image/svg xml,” width=”666″>

Here comes our “Display()” function for this program that has been taking an array and the number of elements from the main() driver code. The “display()” function will be called twice, i.e., before sorting to display the random array and after sorting to show the sorted array. It is started with the “for” loop that will use the variable “n” for the last iteration number and starts from the index 0 of an array. The C object “cout” is used to display each value of array “A” on every iteration while the loop continues. After all, the values for array “A” will be displayed on the shell one after another, separated from each other by a space. At last, the line break will be inserted using the object “cout” once again.

<img alt="" data-lazy- data-lazy-src="https://kirelos.com/wp-content/uploads/2022/04/echo/image6-13.png" data-lazy- height="87" src="data:image/svg xml,” width=”420″>

This program will start from the main() function as C always tends to execute from it. At the very start of our main() function, the integer array “A” was initialized with a total of 6 values. All the values are stored in a random order within array A. We have taken the size of array “A” and the size of the first index value “0” of array A to calculate the total number of elements in an array. That calculated value will be stored in a new variable “n” of integer type. The C standard output can be displayed with the help of an object “cout.”

So, we are utilizing the same “cout” object to display the simple message “Original Array” on the shell to let our users know that the unsorted original array is going to be displayed. Now, we have a user-defined “Display” function in this program that will be called here to display the original array “A” on the shell. We have passed it our original array and the variable “n” in the parameters. After displaying the original array, we are utilizing the Sort() function here to organize and re-arrange our original array into ascending order using the heap sort.

The original array and the variable “n” is passed to it in the parameters. The very next “cout” statement is used to display the message “Sorted Array” after the use of a “Sort” function to sort the array “A.” The function call to the “Display” function is again used. This is to display the sorted array on the shell.

<img alt="" data-lazy- data-lazy-src="https://kirelos.com/wp-content/uploads/2022/04/echo/image5-14.png" data-lazy- height="159" src="data:image/svg xml,” width=”408″>

After the program is complete, we have to make it error-free by using the “g ” compiler on the console. The file name will be used with the “g ” compiler instruction. The code will be specified as error-free if it throws no output. After this, the “./a.out” command can be cast-off to execute the error-free code file. The original array and the sorted array have been displayed.

<img alt="" data-lazy- data-lazy-src="https://kirelos.com/wp-content/uploads/2022/04/echo/image1-18.png" data-lazy- height="72" src="data:image/svg xml,” width=”332″>

Conclusion:

This is all about the working of a heap sort and a way to use the heap sort in C program code to perform sorting. We have elaborated the concept of max heap and min heap for heap sort in this article and also discussed the use of trees for this purpose. We have explained the heap sort in the most simple possible way for our new C users that are using the Linux system.