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++

Heapsort is one of the comparison-based sorting techniques and is part of the selection sort. The heapsort technique uses a comparison mechanism based on the Binary Heap data structure. In this technique, first, choose a maximum element and place the maximum element at the end. The same process is repeated for the remaining elements.

There are many different techniques involved in sorting each having their respective efficiency in the time taken to sort the given data and requirement of space in memory. They are bubble sort, insertion sort, selection sort, quick sort, merge sort and heap sort.

Start Your Free Software Development Course

Web development, programming languages, Software testing & others

What is Heap Sort?

Heapsort is a sorting approach based on the binary heap data structure similar to selection sort where we first obtain the maximal piece of data set and place it at the end and continue for the rest of the elements.

Heapsort as the name itself suggests. It first builds the heap of data elements from the given unsorted array, and then checks for the largest item and places it at the end of the partly sorted array. It again rebuilds the heap, searches for the next largest piece of record and places it in the next empty slot from the end of the half sorted arrangement of records. This process is repeated until no items left in the heap. This technique requires two arrays one for storing the heap and the other for a sorted array.

Algorithm of Heap Sort in C++

  • Firstly choose root as an elevated element from the given information set of elements to create a maximal heap.
  • Reconstruct the heap by placing or interchanging the root with the last element.
  • The heap size will now shrink by 1.
  • Then we again make the heap with remaining elements and continue until the heap size is reduced to 1.

Example of Heap Sort in C++

This technique uses binary heap which is constructed using a complete binary tree where the root node is greater than its two children nodes.

Consider the given array of data sets.

Heap Sort in C++ 1.1

Let us go according to the algorithm. It says to select the highest element as the root and construct the maximal heap.

Popular Course in this category
C++ Training (4 Courses, 5 Projects, 4 Quizzes)4 Online Courses | 5 Hands-on Projects | 37+ Hours | Verifiable Certificate of Completion | Lifetime Access | 4 Quizzes with Solutions
4.5 (4,890 ratings)
Course Price

View Course

Related Courses
Java Training (40 Courses, 29 Projects, 4 Quizzes)C Programming Training (3 Courses, 5 Project)

1. First Iteration

Iteration 1

Now the array will be of the form:

Swapping

Now the sorted array will be of the form:

Heap Sort in C++ -3

The heap size will be reduced by 1, now 6-1 = 5.

2. Second Iteration

So now the heap looks like:

Heap Sort in C++ -4

The array is of the form:

Array Swaping

The sorted array will be:

Heap Sort in C++ -6

The heap size will be reduced by 1, now 5-1 = 4.

3. Third Iteration

The new heap looks like:

Heap Sort in C++ -7

The array is of the form:

Heap Sort in C++ -8

The sorted array will be:

Heap Sort in C++ -9

The heap size will be reduced by 1, now 4-1 = 3.

4. Fourth Iteration

The new heap looks like:

 Heap Sort in C++ -10

The array is of the form:

Heap Sort in C++ -11

The sorted array will be:

Heap Sort in C++ -12 
The heap size will be reduced by 1, now 3-1 = 2.

5. Fifth Iteration

The new heap looks like:

Heap Sort in C++ -13

The array is of the form:

Heap Sort in C++ -14

The sorted array will be:

Sorted Array

The heap size will be reduced by 1, now 2-1 = 1.

6. Last Iteration

The new heap looks like:

Heap Sort in C++ -16

The array has:

4 

From the algorithm, we have carried out all the steps until the heap size is 1. So we now have the sorted array:

Heap Sort in C++ -17 
Therefore the sorted array of the maximal heap is in ascending order. If we need the array sorted in descending order then follow the above steps with a minimal heap.

C++ program for heap sort is as given below:

#include <iostream>
using namespace std;
void heapify(int arr[], int n, int i)
{
int largest = i;
int l = 2 * i + 1;
int r = 2 * i + 2;
if (l < n && arr[l] > arr[largest])
largest = l;
if (r < n && arr[r] > arr[largest])
largest = r;
if (largest != i) {
swap(arr[i], arr[largest]);
heapify(arr, n, largest);
}
}
void heapSort(int arr[], int n)
{
for (int i = n / 2 - 1; i >= 0; i--)
heapify(arr, n, i);
for (int i = n - 1; i >= 0; i--)
{
swap(arr[0], arr[i]);
heapify(arr, i, 0);
}
}
void printArray(int arr[], int n)
{
for (int i = 0; i < n; ++i)
cout << arr[i] << " ";
cout << "\n";
}
int main()
{
int arr[] = { 5,18,4,13,10,7};
int n = sizeof(arr) / sizeof(arr[0]);
heapSort(arr, n);
cout << "Sorted array is \n";
printArray(arr, n);
}

Output:

Output

Conclusion

Heapsort is the comparison based technique which is the enhancement of selection sorting. Heap sort makes use of selecting the highest or lowest element in the given array to sort in ascending or descending order respectively with the maximal or minimal heap. Carry out this process until we get one as heap size. This sorting technique is also used to find the greatest and lowest element in the array. The heap sort technique is more efficient and faster than the selection sort technique.

Recommended Articles

This is a guide to Heap Sort in C++. Here we discuss what is heap sort in c++, working with its algorithm and Example. You may also look at the following articles to learn more-

  1. Heap Sort in C
  2. Heap Sort In Java
  3. Overloading in C++
  4. Pointers in C++

C++ Training (4 Courses, 3 Projects, 4 Quizzes)

4 Online Courses

5 Hands-on Projects

37+ Hours

Verifiable Certificate of Completion

Lifetime Access

4 Quizzes with Solutions

Learn More

1 Shares
Share
Tweet
Share
Primary Sidebar
C plus plus Programming Tutorial
  • Sorting
    • Sorting in C++ 
    • Heap Sort in C++
    • C++ Vector Sort
    • Insertion Sort in C++
    • Selection Sort in C++
  • Basic
    • Introduction To C++
    • What is C++
    • Features of C++
    • Applications of C++
    • Best C++ Compiler
    • C++ Data Types
    • C++ Double
    • C++ unsigned int
    • User Defined Data Types in C++
    • Variables in C++
    • C++ Keywords
    • Pointers in C++
    • C++ Void Pointer
    • Function Pointer in C++
    • Iterator in C++
    • C++ Commands
    • Object in C++
    • C++ Literals
    • C++ Reference
    • C++ Undefined Reference
    • String in C++
    • C++ Programming Language (Basics)
    • C++ Identifiers
    • C++ Header Files
    • Type Casting in C++
    • C++ Formatter
  • Operators
    • C++ Operators
    • Arithmetic Operators in C++
    • Assignment Operators in C++
    • Bitwise Operators in C++
    • Relational Operators in C++
    • Boolean Operators in C++
    • Unary Operators in C++
    • C++ Operator[]
    • Operator Precedence in C++
    • C++ operator=()
  • Control Statements
    • Control Statement in C++
    • if else Statement in C++
    • Else If in C++
    • Nested if in C++
    • Continue Statement in C++
    • Break Statement in C++
    • Switch Statement in C++
    • goto Statement in C++
    • C++ Struct
    • Loops in C++
    • Do While Loop in C++
    • Nested Loop in C++
  • Functions
    • C++ String Functions
    • Math Functions in C++
    • Friend Function in C++
    • Recursive Function in C++
    • Virtual Functions in C++
    • strcat() in C++
    • swap() in C++
    • strcmp() in C++
    • ceil function in C++
    • C++ begin()
    • size() in C++
    • C++ test()
    • C++ any()
    • C++ Bitset
    • C++ find()
    • C++?Aggregation
    • C++?String append
    • C++ String Copy
    • C++ end()
    • C++ endl
    • C++ push_back
    • C++ shuffle()
    • malloc() in C++
    • C++ reserve()
    • C++ unique()
    • C++ sort()
    • C++ find_if()
    • Reflection in C++
    • C++ replace()
    • C++ search()
    • C++ Memset
    • C++ size_t
    • C++ Substring
    • C++ Max
    • C++ absolute value
    • C++ memcpy
    • C++ wchar_t
    • C++ free()
    • C++ sizeof()
    • C++ Move Semantics
  • Array
    • Arrays in C++
    • 2D Arrays in C++
    • 3D Arrays in C++
    • Multi-Dimensional Arrays in C++
    • C++ Array Functions
    • String Array in C++
    • C++ Length of Array
    • C++ arraylist
  • Constuctor and Destructor
    • Constructor and Destructor in C++
    • Constructor in C++
    • Destructor in C++
    • Copy Constructor in C++
    • Parameterized Constructor in C++
  • Overloading and overriding
    • Overloading and Overriding in C++
    • Overloading in C++
    • Overriding in C++
    • Function Overloading in C++
    • Function Overriding in C++
    • Method Overloading in C++
  • Inhertiance
    • Types of Inheritance in C++
    • Single Inheritance in C++
    • Multiple Inheritance in C++
    • Hierarchical Inheritance in C++
    • Multilevel Inheritance in C++
    • Hybrid Inheritance in C++
  • Advanced
    • C++ namespace
    • Encapsulation in C++
    • Access Modifiers in C++
    • Abstract Class in C++
    • C++ Class and Object
    • What is Template Class in C++?
    • C++ Algorithm
    • Data Structures and Algorithms C++
    • C++ Garbage Collection
    • Virtual Keyword in C++
    • Access Specifiers in C++
    • Storage Class in C++
    • Call by Value in C++
    • Multimap in C++
    • C++ Multiset
    • C++ Lambda Expressions
    • Stack in C++
    • C++ Static
    • C++ static_cast
    • Deque in C++
    • C++ Vector Functions
    • C++ 2D Vector
    • C++ List
    • C++ Mutable
    • Enum in C++
    • Abstraction in C++
    • Signal in C++
    • C++ Queue
    • Priority Queue in C++
    • Regular Expressions in C++
    • C++ Hash Table
    • File Handling in C++
    • C++ Stream
    • ifstream in C++
    • C++ ofstream
    • C++ fstream
    • C++ Read File
    • C++ iomanip
    • Macros in C++
    • Templates in C++
    • C++ setprecision
    • C++ Int to String
    • C++ thread( )
    • C++ Thread Pool
    • C++ thread_local
  • Programs
    • Patterns in C++
    • Star Patterns In c++
    • Swapping in C++
    • Reverse Number in C++
    • Palindrome Program in C++
    • Palindrome in C++
    • Factorial Program in C++
    • Fibonacci Series in C++
    • Square Root in C++
    • Random Number Generator in C++
    • Prime Number in C++
    • Leap Year Program in C++
    • Anagram in C++
    • Armstrong Number in C++
    • Reverse String in C++
    • Socket Programming in C++
    • Matrix Multiplication in C++
    • C++ using vs typedef
    • C++ vector vs list
    • C++ vector vs array
  • Interview question
    • C++ Interview Questions
    • Multithreading Interview Questions C++

Related Courses

C++ Training Course

Java Training Course

C Programming 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++ Training (4 Courses, 3 Projects, 4 Quizzes) Learn More