/**
 * @brief al[0 ~ num-1]为大顶堆，将al[num]插入堆中并保持堆性质
 *
 * */
int adjustHeap(int * al, int num)
{
    if (NULL == al || 0 > num) return -1;
    if (0 == num) return 0;
    int i = num - 1;
    int p = (i-1)/2;
    while (i != 0) {
        if (al[i] > al[p]) {
            swap(al, i, p);
            i = p;
            p = i / 2;
            continue;
        } else {
            break;
        }
    }
    return 0;
}

/**
 * @brief 对长度为num的无序整数数组al建立为大顶堆
 *
 * */
int createHeap(int * al, int num)
{
    if (NULL == al || 0 > num) return -1;
    if (2 > num) return 0;
    for (int i=1; i<num; ++i)
    {
        adjustHeap(al, i + 1);
    }
    dumpList(al, num, "heap: ");
    return 0;
}
/**
 * @brief 对al[0, num-1]的堆调整，调整前al[0]不符合规则
 */
int adjustHeap2(int * al, int num) 
{
    int i = 0;
    int lc = i * 2 + 1;
    while (lc < num) {
        int rc = lc + 1;
        int maxc = lc;
        if (rc < num && al[rc] > al[lc]) {
                maxc = rc;
        }
        if (al[i] < al[maxc]) {
            swap(al, i, maxc);
            i = maxc;
            lc = i * 2 + 1;
        } else {
            break;
        }
    }
    return 0;
}

/**
 * @breif 对长度为num的al整数数组进行堆排序，排序后的结果覆盖在al数组上
 *
 * */
int heapSort(int * al, int num)
{
    if (NULL == al || 0 > num) return -1;
    if (2 > num) return 0;
    createHeap(al, num);
    for (int i=num-1; i>0; --i) {
        swap(al, i, 0);
        adjustHeap2(al, i);
    }
    return 0;
}