Heap.h

//
// Created by vienna on 4/4/2016.
//

/* heap data structure implementation */

/* start with index 0, then it need +1 and +2
 * to locate left and right child */
inline int left(int i)
{
    return i * 2 + 1;
}

inline int right(int i)
{
    return i * 2 + 2;
}

void _heapify(int H[], int size, int i)
{
    int l = left(i);
    int r = right(i);

    int max;
    max = (l < size && H[l] > H[i]) ? l : i;
    max = (r < size && H[r] > H[max]) ? r : max;

    if (i != max)
    {
        int t = H[i];
        H[i] = H[max];
        H[max] = t;

        _heapify(H, size, max);
    }
}

void build_heap(int H[], int size)
{
    int n = (size - 2) / 2;
    for (int i = n; i >= 0; i--)
        _heapify(H, size, i);
}

void heap_sort(int H[], int size)
{
    build_heap(H, size);

    while (size >= 2)
    {
        /* swap first and last, then size-- */
        int t = H[0];
        H[0] = H[size - 1];
        H[size - 1] = t;

        size--;
        _heapify(H, size, 0);
    }
}