学步园

算法系列之堆排序

时间复杂度：O(nlogn)

空间复杂度：O(1)

堆：一种完全二叉树，满足根节点比两个子节点都大(大根堆)或小(小根堆)，并且其左右子树也是堆

堆排序的基本思路：

1. 将输入数组从倒数第一个非叶子节点开始建堆

2. 将根与最后一个叶节点交换（即将最大值放到数组的最后一个），并将剩下的元素再整理成堆。

3. 重复第2步，直到剩下一个元素

图示：

说明：MakeHeap建堆时，前提是指定的堆根的左右子树都要是堆，所以建初始堆时，nRoot从最后一个非叶节点开始递减到二叉树的根。图中深色节点为当前要整理成堆的堆根。

说明：深色节点是当前将要与堆根节点交换的节点，未连线的节点表示已经确定顺序。堆排序时把当前堆的根与堆的最一个叶子交换，再把除最后个节点的树整理成堆。

/** @brief 用大根堆排序(升序)指定数组
 *
 * @param pData int* 待排序数组
 * @param nSize int 数组大小
 * @return void
 *
 */
void HeapSort( int *pData, int nSize )
{
    // 建初始堆, 从倒数第一个非叶节点开始建，直到根
    for ( int nRoot = nSize / 2 - 1; nRoot >= 0; --nRoot )
        MakeHeap( pData, nRoot, nSize );

    for ( int nLast = nSize - 1; nLast > 0; --nLast )
    {
        // 把当前堆根（堆中的最大值）与最后一个交换
        int nTmp = pData[0];
        pData[0] = pData[nLast];
        pData[nLast] = nTmp;

        // 再把剩下的nSize-1个元素的数组整理成堆，
        // 由于每次都把最一个元素移到最一个，所以循环结束后数组是升序的
        MakeHeap( pData, 0, nLast );
    }
}

/** @brief 将数组中以nRoot为根的二叉树整理成堆，前提是根节点的左右子树都已经是堆
 *  若数组从0开始索引，那么节点i的左子节点为2*i + 1, 右子节点为2*i + 2, 父节点为(i + 1)/2 - 1
 * @param pData int*
 * @param nRoot int 要整理堆的根
 * @param nSize int 数组的大小
 * @return void
 *
 */
void MakeHeap( int *pData, int nRoot, int nSize )
{
    int nLargest = nRoot; // 用于记录根，左子节点, 右子节点最大值索引
    int nLeft = 2 * nRoot + 1; // 左子节点的索引
    int nRight = 2 * nRoot + 2; // 右子节点的索引

    if ( nLeft < nSize && pData[nLargest] < pData[nLeft] )
        nLargest = nLeft; // 如果左子节点存在，并且比根大

    if ( nRight < nSize && pData[nLargest] < pData[nRight] )
        nLargest = nRight; // 如果右子节点存在，并且比根和左兄弟大

    if ( nLargest != nRoot )
    {
        // 如果以nRoot为根的数组不满足堆的条件
        // 交换根与最大值，并调整对应的子堆
        int nTmp = pData[nRoot];
        pData[nRoot] = pData[nLargest];
        pData[nLargest] = nTmp;
        MakeHeap( pData, nLargest, nSize );
    }
}