Write a Program for Heap Sort Algorithm in C++

Heapsort is a sorting algorithm in which an array of elements is arranged into a special binary tree called a heap. The key features of a heap are that the largest element is always at the top of the heap and the values of the children of any node in the binary tree are always less than or equal to that node's value. A heap arranged in this manner is often called a maxheap. Heapsort is discussed in detail in computer science courses called "Data Structures" and "Algorithms." Here is the Source code of this problem which help you in better understanding.

Source Code

#include <iostream>
#include <algorithm>
#include <vector>
#include <iterator>
using namespace std;
/*
*/

int main()
{
 cout<<"\n\n\n ************** HEAPSORT ALGORITHM ******************** \n\n\n";
 const int Length = 10;
 int a[ Length ] = { 3, 100, 52, 77, 22, 31, 1, 98, 13, 40 };
 std::vector< int > v( a, a + Length ); // copy of a
 std::vector< int > v2;
 std::ostream_iterator< int > output( cout , " " );
 cout << "Vector v before make_heap:\n";
 std::copy( v.begin(), v.end(), output );
 std::make_heap( v.begin(), v.end() );      // create heap from vector v
 cout << "\nVector v after make_heap:\n";
 std::copy( v.begin(), v.end(), output );
 std::sort_heap( v.begin(), v.end() );      // sort elements with sort_heap
 cout << "\nVector v after sort_heap:\n";
 std::copy( v.begin(), v.end(), output );
               // perform the heapsort with push_heap and pop_heap
 cout << "\n\nArray a contains: ";
 std::copy( a, a + Length, output );       // display array a
 cout << endl;
               // place elements of array a into v2 and
               // maintain elements of v2 in heap
 for ( int i = 0; i < Length; i++ )
 {
 v2.push_back( a[ i ] );
 std::push_heap( v2.begin(), v2.end() );
 cout << "\nv2 after push_heap(a[" << i << "]): ";
 std::copy( v2.begin(), v2.end(), output );
 } // end for
 cout << endl; 
 cout << endl;
return 0;
}

Output of the Program

About Asad

Asad Niazi is Software Engineer , Programmer, Web Developer and a young mentor of BloggersTown and PProgramming. Asad Love to writes about Technology, Programming, Blogging and make money online.