堆排序算法

1. 堆排序

1.1 堆的定义

堆是一棵二叉树，树中节点包含键，满足下面两个条件:

• 树的形状为完全二叉树
• 父母的优势：每个节点的键都要大于或等于它子女的键

1.2 自底向上堆构造算法

按照自下而上，从右至左的顺序（最后的父母节点开始，到根为止）检查父母优势条件。如果不满足则调换父子结点的位置。

1.3 删除堆中最大的键（即根节点）

步骤如下：

• 把待删除结点与堆中最后一个键 K 对调。
• 执行删除操作并把堆的大小减一。
• 对删除后的堆进行调整直到满足堆的约束条件。