EDUCBA

EDUCBA

MENUMENU
  • Free Tutorials
  • Free Courses
  • Certification Courses
  • 600+ Courses All in One Bundle
  • Login

Heap Sort in C

Home » Software Development » Software Development Tutorials » C Programming Tutorial » Heap Sort in C

Heap Sort in C

Introduction to Heap Sort in C

Sorting is a technique that is all about the ordering of elements based on different properties. (Properties like arranging data in ascending, descending or alphabetical orders). One major example of sorting that we can think of here is the ordering of items during online shopping. We can relate to prices, popularity, latest and so on. So there are many techniques for this positioning of elements through sorting. In this topic, we are going to learn about Heap Sort in C.

Here we are going to learn one of the most common sorting techniques, Heap Sort, through C programming language.

Start Your Free Software Development Course

Web development, programming languages, Software testing & others

The logic for Heap Sort

How actually can we perform heap sort? Let’s check out below.

Firstly, the heap is one of the tree-based data structure. The tree involved here is always a Complete Binary Tree. And, there are two kinds of heap

  • Min – Heap: Generally arranged in ascending order, that is if the parent node element is having a value less than that of child node elements.
  • Max – Heap: Generally arranged in descending order, that is if the parent node element is having value more than that of child node elements.

Steps for Heap Sort

  • Once an unsorted list data is obtained, elements are organized in the heap data structure either based on creating a min-heap or a max-heap.
  • The first element from the above list is added into our array
  • Again forming the head data structure technique same as the first step is followed and again either the highest element or the least element is picked up and added into our array.
  • Repeated steps help us getting the array with the sorted list.

Program for Heap Sort in C

#include <stdio.h>
int main()
{
int h[20],num,i,j,root,t,x;
printf("Enter number of elements :");
scanf("%d", &num);
printf("\nEnter the elements : ");
for (i = 0; i < num; i++)
scanf("%d", &h[i]);
// build max heap
for(i=0;i<num;i++)
{
x=i;
do
{
root = (x - 1) / 2;
if (h[root] < h[x])
{
t = h[root];
h[root] = h[x];
h[x] = t;
}
x = root;
} while (x != 0);
}
printf("Heap array formed is: ");
for (i = 0; i < num; i++)
printf("%d\t ", h[i]);
for (j = num - 1; j >= 0; j--)
{
t = h[0];
h[0] = h[j];
h[j] = t;
root = 0;
do
{
x = 2 * root + 1;
if ((h[x] < h[x + 1]) && x < j-1)
x++;
if (h[root]<h[x] && x<j)
{
t = h[root];
h[root] = h[x];
h[x] = t;
}
root = x;
} while (x < j);
}
printf("\nThe sorted array is : ");
for (i = 0; i < num; i++)
printf("\t %d", h[i]);
}

First, we are asking the user to input the number of elements that are taken for sorting and then the user is allowed to enter different elements that are to be sorted.

Popular Course in this category
C Programming Training (3 Courses, 5 Project)3 Online Courses | 5 Hands-on Projects | 34+ Hours | Verifiable Certificate of Completion | Lifetime Access
4.5 (5,570 ratings)
Course Price

View Course

Related Courses
C++ Training (4 Courses, 5 Projects, 4 Quizzes)Java Training (40 Courses, 29 Projects, 4 Quizzes)

Steps Followed

  • The next which we are focusing on is to create a heap array, in this case, max-heap array.
  • The main condition for getting a max – heap array is to check that no parent node value is less than its child node value. We are going to swap until we achieve that condition.
  • The main advantage in this complete binary tree is, the left and right child nodes of a parent node can be accessed with values 2(i) + 1 and 2*(i) + 2 values respectively. Where i is the parent node.
  • So, through that way here, we are placing our root node which contains the maximum value in the rightmost leaf node place. And then again following the same procedure such that the next maximum number now becomes the root node.
  • We are going to follow the same procedure until only one node is left in the heap array.
  • And then, we are arranging our heap array to form a perfect sorted array in increasing order.
  • Finally, we are printing the sorted array in the output.

Output:

The output is attached below.

Let me show you the pictorial representation of the happenings:

  • The data entered is first represented in the form of a single-dimensional array as follows.

Heap Sort in C 1

  • The pictorial representation of the binary tree formed is as follows:

Output 1

  • Now, we are going to convert to the max heap by making sure that all the parent nodes are always greater than child nodes. As mentioned in the output under heap sorted array, the pictorial representation would be:

Output 2

  • After this, we are going to swap the root node with the extreme leaf node and then delete it from the tree. The leaf node would be the root now and again same process e followed to again get the highest element in the root

Output 3

  • So, in this case, 77 digits are being deleted from this tree and placed into our sorted array and the process is repeated.

The above we have seen it for forming max heap array. The same process is dealt with with the min-heap array formation also. As discussed above, the only difference is with the relationship between parent and child node elements.

As an exercise, can you try forming the heap sort in the descending order?

Conclusion

Though there are many sorting techniques, heap sort is considered one of the better sorting technique due to its time and space complexity. The time complexity for all best, average and worst case is O(nlogn), where worst-case complexity is better than worst-case complexity of Quicksort and space complexity is O(1).

Recommended Articles

This is a guide to Heap Sort in C. Here we discuss the logic and the Steps for Heap Sort with the sample code and output along with pictorial representations. You may also have a look at the following articles to learn more –

  1. Heap Sort In Java
  2. Selection Sort in Java
  3. Heap Sort in C++
  4. Heap Sort in Python

C Programming Training (3 Courses, 5 Project)

3 Online Courses

5 Hands-on Projects

34+ Hours

Verifiable Certificate of Completion

Lifetime Access

Learn More

0 Shares
Share
Tweet
Share
Primary Sidebar
C Programming Tutorial
  • Sorting
    • Sorting in C
    • Heap Sort in C
  • Basic
    • Introduction to C
    • What is C
    • Career in C Programming
    • Advantages of C
    • How to Install C
    • Best C Compilers
    • Data Types in C
    • Variables in C
    • C Keywords
    • C Command
    • Command Line Arguments in C
    • C Literals
    • Constants in C
    • Unsigned Int in C
    • String in C
  • Pointers
    • Pointers in C
    • Null pointer in C
    • Function Pointer in C
    • Double Pointer in C
    • Void Pointer in C
    • Const Pointer in C
    • Dangling Pointers in C
    • Pointer Arithmetic in C
  • Operators
    • C Operators
    • Arithmetic Operators in C
    • Relational Operators in C
    • Assignment Operators in C
    • Logical Operators in C
    • Conditional Operator in C
    • Modulus Operator in C
    • Ternary Operator in C
    • Address Operator in C
    • Unary Operator in C
    • Operators Precedence in C
    • Left Shift Operator in C
  • Control Statement
    • Control Statements in C
    • If Statement in C
    • If-else Statement in C
    • Else if Statement in C
    • Nested if Statement in C
    • #else in C
    • Structure Padding in C
    • Nested Structure in C
    • Continue Statement in C
    • Break Statement in C
    • Switch Statement in C
    • Goto Statement in C
  • Loops
    • Loops in C
    • For Loop in C
    • While Loop in C
    • Do While Loop in C
    • Nested Loop in C
    • Infinite Loop in C 
  • Function
    • Math Functions in C
    • Hashing Function in C
    • Recursive Function in C
    • Power Function in C
    • fputs in C
    • C puts() Function
    • fprintf() in C
    • fseek() in C
    • Stderr in C
    • ASCII Value in C
    • strcat() in C
    • Inline Function in C
    • sizeof() in C
    • Function Prototype in C
    • C ftell()
  • Array
    • Arrays in C Programming
    • 2-D Arrays in C
    • 3D Arrays in C
    • Multidimensional Array in C
    • Array Functions in C
    • Strings Array in C
  • Advanced
    • Constructor in C
    • Encapsulation in C
    • C Storage Classes
    • Static Keyword in C
    • File Handling in C
    • Queue in C
    • Hexadecimal in C 
    • typedef in C
    • Memory Allocation in C
    • Linked List in C
    • Volatile in C
    • Tokens in C
    • Expression in C
    • Regular Expression in C
    • Error Handling in C
    • Types of Errors in C
    • Preprocessor in C
    • Preprocessor Directives in C
    • fscanf() in C
    • #Pragma in C
    • #ifndef in C
    • #undef in C
    • Macros in C
  • C programs
    • Patterns in C Programming
    • Star Patterns in C
    • Number Patterns in C
    • Swapping in C
    • Reverse Number in C
    • Palindrome in C Program
    • Factorial in C
    • Fibonacci Series in C
    • Square Root in C
    • Random Number Generator in C
    • Prime Numbers in C
    • Escape Sequence in C
    • Reverse String in C
    • Leap Year Program in C
    • Anagram Program in C
    • Strong Number in C
    • String Concatenation in C
    • C Programming Matrix Multiplication
    • Decimal to Octal in C
    • Expression Evaluation in C
    • Decimal to Hexadecimal in C
  • Interview question
    • C Programming Interview Questions

Related Courses

C Programming Training Course

C++ Training Course

Java Training Course

Footer
About Us
  • Blog
  • Who is EDUCBA?
  • Sign Up
  • Corporate Training
  • Certificate from Top Institutions
  • Contact Us
  • Verifiable Certificate
  • Reviews
  • Terms and Conditions
  • Privacy Policy
  •  
Apps
  • iPhone & iPad
  • Android
Resources
  • Free Courses
  • Java Tutorials
  • Python Tutorials
  • All Tutorials
Certification Courses
  • All Courses
  • Software Development Course - All in One Bundle
  • Become a Python Developer
  • Java Course
  • Become a Selenium Automation Tester
  • Become an IoT Developer
  • ASP.NET Course
  • VB.NET Course
  • PHP Course

© 2020 - EDUCBA. ALL RIGHTS RESERVED. THE CERTIFICATION NAMES ARE THE TRADEMARKS OF THEIR RESPECTIVE OWNERS.

EDUCBA
Free Software Development Course

Web development, programming languages, Software testing & others

*Please provide your correct email id. Login details for this Free course will be emailed to you
Book Your One Instructor : One Learner Free Class

Let’s Get Started

This website or its third-party tools use cookies, which are necessary to its functioning and required to achieve the purposes illustrated in the cookie policy. By closing this banner, scrolling this page, clicking a link or continuing to browse otherwise, you agree to our Privacy Policy

EDUCBA

*Please provide your correct email id. Login details for this Free course will be emailed to you
EDUCBA Login

Forgot Password?

EDUCBA
Free Software Development Course

Web development, programming languages, Software testing & others

*Please provide your correct email id. Login details for this Free course will be emailed to you

Special Offer - C Programming Training (3 Courses, 5 Project) Learn More