Heap Sort

/*
Heapsort(A as array)
    BuildHeap(A)
    for i = n to 1
        swap(A[1], A[i])
        n = n - 1
        Heapify(A, 1)

BuildHeap(A as array)
    n = elements_in(A)
    for i = floor(n/2) to 1
        Heapify(A,i)

Heapify(A as array, i as int)
    left = 2i
    right = 2i+1

    if (left <= n) and (A[left] > A[i])
        max = left
    else
        max = i

    if (right<=n) and (A[right] > A[max])
        max = right

    if (max != i)
        swap(A[i], A[max])
        Heapify(A, max)
[edit]
*/
#include <iostream>
#include <stdio.h>
using namespace std;

void heapify(int *a, int root, int bottom)
{
    int done, max, temp;

    done = 0;
    while ((root*2 <= bottom) && (!done))
    {
        if (root*2 == bottom)
            max = root * 2;
        else if (a[root * 2] > a[root * 2 + 1])
            max = root * 2;
        else
            max = root * 2 + 1;

        if (a[root] < a[max])
        {
            temp = a[root];
            a[root] = a[max];
            a[max] = temp;
            root = max;
        }
        else
            done = 1;
    }
}

void heapsort(int *a, int size)
{
    int i, temp;

    for (i = (size / 2)-1; i >= 0; i--)
        heapify(a, i, size - 1);

    for (i = size-1; i >= 1; i--)
    {
        temp = a[0];
        a[0] = a[i];
        a[i] = temp;
        heapify(a, 0, i-1);
    }
}

int main()
{
    int a[10]={12,48,67,34,25,85,93,55,10,77};
    for(int k=0; k<10; k++)
    {
    cout<< a[k] << " ";
    }
    cout << "\n\n";
    heapsort(a, 10);
    for(int k=0; k<10; k++)
    {
    cout<< a[k] << " " << endl;
    }
    system("pause");
}