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++ |
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
You wrote:
ReplyDeleteint a[n];
...
for (int i = 1; i <= n; i++)
{
cin>>a[i];
}
and your program works despite the indexation error ?
please upload the error free code then...!
DeleteThis comment has been removed by the author.
ReplyDeleteMy method:
ReplyDeletevoid 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!
// with correct indexing
ReplyDelete#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;
}