王道数据结构 排序算法 堆排序 ★★★★★

如果结点总数n，则

非终端结点：i <= ⌊n/2⌋
终端结点： i > ⌊n/2⌋

如果非终端结点编号为j，则：

左孩子编号：2j

右孩子编号：2j+1

父节点编号：⌊j/2⌋

大根堆：根 >= 左、右
小根堆：根 <= 左、右
二叉排序树（BST）：左 <= 根 <= 右

堆排序：

每一趟将堆顶元素加入有序子序列（与待排序序列中的最后一个元素交换），并将待排序序列元素再次调整为大根堆（小元素不断"下沉"）

• 基于大根堆的堆排序得到递增序列
• 基于小根堆的堆排序得到递减序列

• 稳定性：不稳定
• 时间复杂度：O(nlog₂n)
• 空间复杂度：O(1)

// 建立大根堆
void BuildMaxHeap(int A[], int len) {
    for (int i = len / 2; i > 0; i--) {
        HeadAdjust(A, i, len);
    }
}

// 将以k为根的子树调整为大根堆
void HeadAdjust(int A[], int k, int len) {
    A[0] = A[k];                             // A[0]暂存子树的根结点
    for (int i = 2 * k; i <= len; i *= 2) {  // 沿key较大的子结点向下筛选
        if (i < len && A[i] < A[i + 1]) {
            i++;  // 取key子结点较大者的下标
        }
        if (A[0] >= A[i]) {
            break;  // 根key比子结点下标都大，无须调整
        } else {
            A[k] = A[i];  // 将A[i]调整到双亲结点上
            k = i;        // 修改k值，以便继续向下筛选
        }
    }
    A[k] = A[0];  // 被筛选结点的值放入最终位置
}


void HeapSort(int A[], int len) {
    BuildMaxHeap(A, len);            // 初始建堆
    for (int i = len; i > 1; i--) {  // n-1趟交换和建堆过程
        swap(A[i], A[1]);            // 将堆顶元素和堆底元素交换
        HeadAdjust(A, 1, i - 1);     // 把剩余的待排序元素整理成堆
    }
}