Search Tutorials

Tuesday, 24 February 2015

Heap Sort Using C++ 


A sorting algorithm that works by first organizing the data to be sorted into a special type of binary tree called a heap. The heap itself has, by definition, the largest value at the top of the tree, so the heap sort algorithm must also reverse the order.
It does this with the following steps:







1. Remove the topmost item (the largest) and replace it with the rightmost leaf. The topmost item is stored in an array. 







 2. Re-establish the heap.







 3. Repeat steps 1 and 2 until there are no more items left in the heap.

The sorted elements are now stored in an array.


 


/* C++ Program to implement Heap Sort */ 


 


#include <iostream>
using namespace std;

void MAX_HEAPIFY(int a[], int i, int n)
{
    int l,r,largest,loc;
    l=2*i;
    r=(2*i+1);
    if((l<=n)&&a[l]>a[i])
       largest=l;
    else
       largest=i;
    if((r<=n)&&(a[r]>a[largest]))
       largest=r;
    if(largest!=i)
    {
         loc=a[i];
         a[i]=a[largest];
         a[largest]=loc;
         MAX_HEAPIFY(a, largest,n);
    }
}
void BUILD_MAX_HEAP(int a[], int n)
{
    for(int k = n/2; k >= 1; k--)
    {
        MAX_HEAPIFY(a, k, n);
    }
}
void HEAPSORT(int a[], int n)
{

    BUILD_MAX_HEAP(a,n);
    int i, temp;
    for (i = n; i >= 2; i--)
    {
        temp = a[i];
        a[i] = a[1];
        a[1] = temp;
        MAX_HEAPIFY(a, 1, i - 1);
    }
}

int main()
{
    int n;
    cout<<"Enter the size of the array"<<endl;
    cin>>n;
    int a[n];
    cout<<"Enter the elements in the array"<<endl;
    for (int i = 1; i <= n; i++)
    {
        cin>>a[i];
    }
    HEAPSORT(a, n);
    cout<<":::::::SORTED FORM::::::"<<endl;
    for (int i = 1; i <= n; i++)
    {
        cout<<a[i]<<endl;
    }
}


 


//Output of above program








Heap Sort Using C++


Heap Sort Using C++




 



Related Programs:-












★ Merge Sort using C++

★ Quick Sort algorithm using C 

★ Binomial Heap Tree using C

★ Fibonacci Heap Tree using C

★ Insert, delete and display elements from stack using C 













Posted by



at








Edit












Labels:
,














5 comments:








  1. Jamet2:28 am
    You wrote:
    int a[n];
    ...
    for (int i = 1; i <= n; i++)
        {
            cin>>a[i];
        }
    and your program works despite the indexation error ?
    ReplyDelete
    Replies
    1. Unknown1:18 pm
      please upload the error free code then...!
      Delete
  2. Anonymous8:13 am
    This comment has been removed by the author.
    ReplyDelete
  3. Unknown7:49 am
    My method: 
    void Output(int a[], int n)
    {
       for(int i=0;i<n;i++)
        {
            printf("\n%d",a[i]); 
         }
    }
    I want combined my method with your method:HeapSort.
    How to use?
    Thanks you!
    ReplyDelete
  4. Anonymous12:01 am
    // with correct indexing
    #include 

    void maxHeapify(int a[], int i, int n)
    {   
        int l, r, largest;
        l=2*i;
        r=1+l;
        if(la[i])
            largest = l;
        else
            largest = i;
        if( r < n && a[r] > a[largest] )
            largest = r;

        if(largest != i)
        {
            int loc = std::move(a[i]);
            a[i] = std::move(a[largest]);
            a[largest] = std::move(loc);
            maxHeapify(a, largest, n);
        }
    }

    void buildMaxHeap(int a[], int n)
    {   
        for(int k = n/2 - 1; k >= 0; k--)
        {
            maxHeapify(a, k, n);
        }
    }

    void heapsort(int a[], int n)
    {   
        buildMaxHeap(a,n);
        int i;
        
        for(i = n - 1; i >=1; i--)
        {   
            int temp = std::move(a[i]);
            a[i] = std::move(a[0]);
            a[0] = std::move(temp);
            
            maxHeapify(a, 0, i-1);
        }
    }

    int main()
    {
        int n;
        std::cout << "Enter the size of the array" << std::endl;
        std::cin >> n;

        if(n < 0)
            return 1;

        int a[n];
        for(int i = 0; i < n; ++i)
        {
            std::cout << "Enter the element " << 1 + i << std::endl;
            std::cin >> a[i];
        }

        heapsort(a, n);
        std::cout << "SORTED" << std::endl;
        for(int i = 0; i < n; ++i)
            std::cout << a[i] << std::endl;

        return 0;
    }
    ReplyDelete




























        

      







































































Back to Top