相信很多读者在学习排序算法的时候，理解并背下了快速排序和归并排序的代码。而对于堆排序可能了解不多，对堆的印象可能只停留在大顶堆堆顶元素最大，小顶堆堆顶元素最小。但其实，堆排序才是个人认为的原理最简单、代码最简洁的一种优秀排序算法。
0.完全二叉堆
在深入了解堆之前，可以先想这么一个问题，堆长什么样？有的读者会觉得，（大顶）堆堆顶元素最大，然后它的左右孩子比它小，所以应该是树怎么存，它就怎么存吧。用一个个的节点存值，然后节点的左右孩子指针指向它的左右孩子。这确实没错，但要注意到完全二叉堆在逻辑结构上等同于一棵完全二叉树，跟线性的数组有着紧密的对应关系。所以我们可以用数组来存储这个完全二叉堆，这么做的优势也很明显，各节点在物理上连续排列，还可以轻松的按照索引来访问节点。
1.完全二叉堆的表示
铺垫了这么多，我们来看一个堆的实例，理解完全二叉堆的表示和存储。
如图，右边是我们想象中的一个小顶堆的样子，左上角的完全二叉树是这个小顶堆对应的二叉树表示，左下角连续排列的元素是该完全二叉树按层次遍历得到的结果，元素的不同层级代表了元素在完全二叉树中所处的不同深度。这一实现方式的优势首先体现在，各节点在物理上连续排列，故总共仅需
空间。而更重要的是，利用各节点在数组中的索引，也可便捷地判别父子关系。比如，节点2在数组中的索引是2，而它的左右孩子5和6的索引分别是5和6，恰好满足
。更一般的，对于索引为
的节点，它的左右孩子和父节点的索引必然满足：
左孩子索引
右孩子索引
父节点索引
2.完全二叉堆的操作
当在完全二叉堆中插入或者删除元素后，完全二叉堆的“堆序性”可能不在满足，所谓的“堆序性”是指堆顶以外的每个节点都不小（大）于其父节点。而为了让完全二叉堆重新满足“堆序性”，需要对其进行上滤和下滤操作。
2.1上滤
上滤发生在向堆中插入新元素的时候，首先要把待插入元素置于数组末尾，然后不断调整其和父节点的偏序关系，这一过程体现在树中就仿佛叶子节点在不断向上浮，因此叫上滤。
在如图(a)所示由5个元素组成的初始堆中，现拟插入值为5的新元素。为此：
首先如图(b)所示，将该元素置于数组的末尾；新元素5与其父节点0逆序，故如图(c)所示，经一次交换之后，新元素5上升一层；新元素5与其新的父节点4依然逆序，故如图(d)所示，经一次交换后再上升一层；此时因5已抵达堆顶，插入操作完毕，故算法终止。2.2下滤
下滤发生在从堆中删除最值元素的时候，首先从数组头部将最值元素摘除，接着为调整偏序关系，需要把数组末尾元素交换到头部，然后不断调整头部元素和其孩子节点的偏序关系，这一过程体现在树中就仿佛根节点在不断向下沉，因此叫下滤。
从如图(a)所示由6个元素组成的完全堆中，现拟删除堆顶元素5。为此：
首先如图(b)所示将该元素摘除，并将向量的末元素1转入首单元，当作堆顶；1与其孩子节点均逆序。故如图(c)所示，在与其孩子中的大者4交换之后，1下降一层；1与其新的孩子2依然逆序，故如图(d)所示经又一次交换后再下降一层；此时因1已抵达底层，删除操作完毕，算法成功终止。2.3建堆
建堆的方式有好多种，我们只讲复杂度最低的一种：Floyd建堆。
首先如图(a)所示，将9个元素组织为一棵完全二叉树。要注意到，在多数情况下，输入数据都是以数组形式给出，故除了明确各元素间的父子关系外，并不需要做任何实质的操作。此时，所有叶节点各自即是一个规模为1的堆。之后，自底而上地逐层合并：首先如图(b)所示，在对3实施下滤调整之后，{8}和{5}合并为{8,3,5}；接下来如图(c)所示，在对1实施下滤调整之后，{8,3,5}与{9}合并为{9,8,1,3,5}；对6实施下滤调整之后，{7}与{4}合并为{7,6,4}；最后如图(d)所示，在对2实施下滤调整之后，{9,8,1,3,5}与{7,6,4}合并为{9,8,7,5,1,6,4,3,2}，建堆完毕。2.4操作复杂度
上滤和下滤：最多进行树高次，而每次调整的仅涉及两个元素的交换，时间复杂度为
，因此，上滤和下滤的时间复杂度为
。
Floyd建堆：时间复杂为
，建堆算法需做n步迭代，以对所有节点各做一次下滤。这里，每个节点的下滤所需的时间线性正比于其高度，故总体运行时间取决于各节点的高度总和。
3.堆排序
有了上滤、下滤、建堆的基础，我们就可以实现堆排序了，这里介绍原地堆排序算法。
图中Heap为大顶堆部分，Sorted为有序区部分。Heap和Sorted都在一个数组中存储，只是通过不同的索引来控制两部分的范围。最开始Heap占据整个数组，Sorted为空，随着我们不断将Heap中堆顶的最大元素交换到Sorted部分，Heap规模逐渐减小，Sorted规模逐渐扩大，又因为每次从Heap交换到Sorted中的最大值都在上一个最大值的左边，所以Sorted保持升序。
更具体的，首先如图(a)，取出首元素M，将其与末元素X交换，如此交换之后M必处于正确的排序位置。故如图(b)，此时可等效地认为Sorted向前扩大了一个单元，Heap相应地缩小了一个单元。但存在的问题是，元素X在Heap中的位置不一定准确，但只需对X实施一次下滤调整，即可使Heap整体的堆序性重新恢复，结果如图(c)所示。重复上述操作，当Sorted规模扩大到整个数组，即完成了原地堆排序。
4.堆、完全二叉树、完全二叉堆、优先级队列的关系
在练习算法题时用过堆排序的读者可能会留意，在C++和Java语言中，“堆”是用优先级队列实现的。那堆、完全二叉堆、完全二叉树和优先级队列之间究竟是什么关系？
堆（Heap）是计算机科学中的一种特别的完全二叉树。若是满足以下特性，即可称为堆：“给定堆中任意节点P和C，若P是C的母节点，那么P的值会小于等于（或大于等于）C的值”。
堆的实现通常是通过构造完全二叉堆（CompleteBinaryHeap），因为完全二叉堆应用很普遍，当不加限定时，堆通常指的就是完全二叉堆。
简单来说，堆其实就是指完全二叉堆。因为他们的堆序性和完全二叉性一样。
但其实，当我们提到堆时，往往关心的不是堆这种数据结构，而是它里面的偏序思想，也就是只从中获取最大值（最小值）、高优先级（低优先级）元素，并不关心其他元素。事实上，在C++的STL里，堆并不是一种容器，而是一种算法，只提供了关于堆调整的算法。
刚说了，能从堆里获取优先级最高（最低）的元素，所以把这种算法加上能够提供随机访问迭代器的容器（如：Vector），就得到了优先级队列。
所以，我们才能在代码中使用优先级队列来模拟“堆”。
5.总结
以上就是关于堆和堆排序的讲解，更具体的算法实现代码在后续文章中分享。文中所有图片和部分文字来源于清华大学出版的《数据结构（C++语言版）》，教材链接在文章最后。
