> For the complete documentation index, see [llms.txt](https://kerasnoone.gitbook.io/garnet/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://kerasnoone.gitbook.io/garnet/suan-fa/dui/dui-pai-xu.md).

# 堆排序

## 堆

堆排序是利用堆这种数据结构而设计的一种排序算法, 是一种[选择排序](https://www.runoob.com/w3cnote/selection-sort.html), 它的最坏, 最好, 平均时间复杂度均为$$O(n \log n)$$.

堆是具有以下性质的完全二叉树: 每个结点的值都大于或等于其左右孩子结点的值, 称为大顶堆; 或者每个结点的值都小于或等于其左右孩子结点的值, 称为小顶堆.

![](https://1942165044-files.gitbook.io/~/files/v0/b/gitbook-legacy-files/o/assets%2F-MI7KRyeBH5dlW-CkUtn%2Fsync%2F29dfa5721550017e8eb28c3183577dc548a5988e.png?generation=1614002737667962\&alt=media)

同时, 堆是用**数组**实现的, 上图中大顶堆对应的数组为:

![](https://1942165044-files.gitbook.io/~/files/v0/b/gitbook-legacy-files/o/assets%2F-MI7KRyeBH5dlW-CkUtn%2Fsync%2F69924e646ae406a3861f8a3623821dd3cef89f42.png?generation=1614002737662696\&alt=media)

并不是完全顺序的.

最大堆/最小堆用公式表示为:

* 最大堆: $$\text{arr}\[i] \ge \text{arr}\[2i+1], \quad \text{arr}\[i] \ge \text{arr}\[2i+2]$$
* 最小堆: $$\text{arr}\[i] \le \text{arr}\[2i+1], \quad \text{arr}\[i] \le \text{arr}\[2i+2]$$

## 堆排序

堆排序(**升序**)的基本思想是: 将待排序序列构造成一个**大顶堆**, 整个序列的最大值就是堆顶的**根节点**. 将其与**末尾元素**进行交换, **此时末尾就为最大值**. 然后剩余的$$n-1$$个元素重新构造成一个堆, 重复一次得到所有数字中第二大的值. 如此反复执行, 便能得到一个有序序列了.

完整的堆排序具体来说分为几个步骤.

### 构造初始堆

将给定无序序列构造成一个大顶堆(升序采用大顶堆, 降序采用小顶堆). 假设给定无序序列结构如下:

![](https://1942165044-files.gitbook.io/~/files/v0/b/gitbook-legacy-files/o/assets%2F-MI7KRyeBH5dlW-CkUtn%2Fsync%2Fe994bc69c06d5d892e2f4c5c2deb156ceb99f432.png?generation=1614002738276070\&alt=media)

从**最后一个非叶子节点**开始(最后一个非叶子节点对应的索引为$$\lfloor n / 2 \rfloor - 1$$), 从左至右, 从下至上进行调整:

![](https://1942165044-files.gitbook.io/~/files/v0/b/gitbook-legacy-files/o/assets%2F-MI7KRyeBH5dlW-CkUtn%2Fsync%2F7763b310963dbd9763b4db5f10acd0d57e093079.png?generation=1614002738330680\&alt=media)

![](https://1942165044-files.gitbook.io/~/files/v0/b/gitbook-legacy-files/o/assets%2F-MI7KRyeBH5dlW-CkUtn%2Fsync%2F6781f46f4933fc4c29a9a169d912a49ee1f6c0a1.png?generation=1614002737815068\&alt=media)

上面这步导致了子堆\[4, 5, 6]结构混乱, 继续调整, 需要将4下沉:

![](https://1942165044-files.gitbook.io/~/files/v0/b/gitbook-legacy-files/o/assets%2F-MI7KRyeBH5dlW-CkUtn%2Fsync%2F4c1550d5c30142645333ea90e2869b02cb938559.png?generation=1614002738296656\&alt=media)

此时, 我们就将一个无需序列构造成了一个大顶堆.

### 交换堆顶元素和末尾元素并重建堆

将堆顶元素与末尾元素进行交换, 使末尾元素最大. 最大的数被找到了, 而且也放在了数组的最后. 要在剩余的$$n-1$$个数继续找最大的数, 因此需要调整得到新的堆, 再将堆顶元素与末尾元素交换. 如此反复进行**交换**, **重建**, 数组最后的部分就是排序好的大元素. 示例如下:

将堆顶元素9和末尾元素4进行交换:

![](https://1942165044-files.gitbook.io/~/files/v0/b/gitbook-legacy-files/o/assets%2F-MI7KRyeBH5dlW-CkUtn%2Fsync%2F402094df9c2646170b6bec5410260428ff99b94e.png?generation=1614002738347321\&alt=media)

重新调整结构, 使其继续满足堆定义:

![](https://1942165044-files.gitbook.io/~/files/v0/b/gitbook-legacy-files/o/assets%2F-MI7KRyeBH5dlW-CkUtn%2Fsync%2F897bca19e11ef56dda82e4719e50b1546e7d8834.png?generation=1614002738286135\&alt=media)

再将堆顶元素8与末尾元素5进行交换, 得到第二大元素8:

![](https://1942165044-files.gitbook.io/~/files/v0/b/gitbook-legacy-files/o/assets%2F-MI7KRyeBH5dlW-CkUtn%2Fsync%2F3d0d33d9ab7f3d523224fe8aa38c90f5c457d38b.png?generation=1614002738314328\&alt=media)

后续过程, 继续进行调整, 交换, 如此反复进行, 最终使得整个序列有序:

![](https://1942165044-files.gitbook.io/~/files/v0/b/gitbook-legacy-files/o/assets%2F-MI7KRyeBH5dlW-CkUtn%2Fsync%2F76e9c3ed0a5186a4fd3e3ab90acd3bd096d5f9e8.png?generation=1614002738427136\&alt=media)

### 时间复杂度

堆排序作为一种选择排序, 整体主要由**构建初始堆**和**交换堆顶元素和末尾元素并重建堆**两部分组成.

构建初始堆经推导复杂度为$$O(n)$$.

在交换并重建堆的过程中, 需交换$$n-1$$次, 而重建堆的过程中, 根据完全二叉树的性质, 对应的时间复杂度为$$\[\log(n-1), \log(n-2), \cdots, \log(1)]$$逐步递减, 近似为$$O(n \log n)$$.

所以堆排序时间复杂度一般认为就是$$O(n \log n)$$.

## 参考资料

* [图解排序算法(三)之堆排序](https://www.cnblogs.com/chengxiao/p/6129630.html)