Heap sort algorithm in C++

The heap sort algorithm is based on the binary heap data structure which is similar to the selection sort, as firstly we find the maximum element and place the maximum element at the end and repeat the same process.

The steps of how the algorithm works

1. Create a heap data structure which can be Max-heap or min-heap
2. Once the heap is built, we put the first element of the heap in the array, which can either be the largest or smallest
3. Use the remaining elements to repeatedly pick the first element of the heap and put it into the array
4. Repeat the same process until we have the complete sorted list in the array

Visualization of the algorithm

We can build a heap by working through the unordered array in a linear fashion

After the heap has been built, we can now sort the values

Code implementation in C++

#include <iostream>

using namespace std;

void heapsort(int[], int);
void buildheap(int [], int);
void satisfyheap(int [], int, int);

int main()
{
int a[10];
int i, size;

cout << "Enter in the size of the list\n";
cin >> size;

cout << " Enter " << size << " elements ";

// Go through the values
for(int i = 0; i < size; i++)
{
cin >> a[i];
}

heapsort(a, size);

}

void heapsort(int a[], int length)
{
buildheap(a, length);
int heapsize, i, temp;
heapsize = length - 1;
for( i=heapsize; i >= 0; i--)
{
temp = a[0];
a[0] = a[heapsize];
a[heapsize] = temp;
heapsize--;
satisfyheap(a, 0, heapsize);
}
for( i=0; i < length; i++)
{
cout << "\t" << a[i];
}
}

void buildheap(int a[], int length)
{
int i, heapsize;
heapsize = length - 1;
for( i=(length/2); i >= 0; i--)
{
satisfyheap(a, i, heapsize);
}
}

void satisfyheap(int a[], int i, int heapsize)
{
int l, r, largest, temp;
l = 2*i;
r = 2*i + 1;

if(l <= heapsize && a[l] > a[i])
{
largest = l;
}
else
{
largest = i;
}
if( r <= heapsize && a[r] > a[largest])
{
largest = r;
}
if(largest != i)
{
temp = a[i];
a[i] = a[largest];
a[largest] = temp;
satisfyheap(a, largest, heapsize);
}
}