1. 将无序序列构建成一个堆，根据升序降序需求选择大顶堆或小顶堆;
2. 将堆顶元素与末尾元素交换，将最大元素"沉"到数组末端;（即将堆顶元素移出堆，末尾元素顶替到堆顶）
3. 重新调整结构，使其满足堆定义，然后继续交换堆顶元素与当前末尾元素，反复执行调整+交换步骤，直到整个序列有序。

• 时间复杂度：$O(n\log_2n)$

空间复杂度：$O(1)$

1. 无序序列创建堆

一句话：自下而上逐步调整为大顶堆/小顶堆。

从最后一个非叶节点为根的子树开始调整（第 $\lfloor n/2 \rfloor$ 个结点为根的子树）

调整：最大元素作根结点

自下而上继续调整上一个非叶节点为根的子树，直到根结点

调整过程可能会破坏下一级的堆，要继续采用上述方法再调整下一级的堆

• 时间复杂度：$O(n)$
• illustrate

建立大顶堆代码：

void HeadAdjust(ElemType A[], int k, int len) {
	A[0] = A[k];
	for (i = 2*k; i<= len; i*=2) { // 遍历结点k的子结点
		if (i < len && A[i]<A[i+1]) i++; // 找子结点中较大的
		if (A[0] >= A[i]) break; // 比较 较大的子结点i 与 当前根结点k 谁大，如果k大，则已经满足大顶堆
		else { // 否则，交换两者，使堆调整为大顶堆
			A[k] = A[i];
			k = i; // 可能破坏了下层堆的特性，所以继续向下调整结点i的子树，保持大顶堆的特性
		}
	}
	A[k] = A[0]; // 最终根结点被调整到合适的位置
}
void BuildMaxHeap(ElemType A[], int len) {
	// 从最后一个非叶结点开始，调整堆
	for (int i = len/2; i > 0; i--) HeadAdjust(A, i, len);
}

2. 删除堆顶元素后，调整堆

删除堆顶元素，即用最后一个元素A覆盖堆顶元素

此时堆的特性被破坏，将A自上而下不断交换调整，将A沉到堆的底部，使整个堆再次满足大顶堆/小顶堆

• illustrate