Heapsort

heapsort.cpp

void swap(int *a, int i, int j)
{
    int t = a[i];
    a[i] = a[j];
    a[j] = t;
}

void siftup(int* a, int n)
{
    for (int c = n; a[c/2] < a[c] && c/2 > 0; c /= 2) {
        swap(a, c/2, c);
    }
}

void siftdown(int *a, int n)
{
    for (int p = 1, c; (c = 2*p) <= n; p = c) {
        if (c+1 <= n && a[c+1] > a[c])
            c++;
        if (a[c] <= a[p])
            break;
        swap(a, c, p);
    }
}

int main(int argc, char *argv[])
{
    const int n = 11;
    int a[n]{-1, 1, 9, 8, 7, 6, 5, 4, 3, 2, 10};
    
    for (int i = 1; i < n; i++) {
        siftup(a, i);
    }
    
    for (int i = n-1; i > 0; i--) {
        swap(a, i, 1);
        siftdown(a, i-1);
    }
    
    return 0;
}