一、堆：
1、概念：
①、堆是一个完全二叉树；
②、堆中每一个节点的值都必须大于等于（或小于等于）其子树中每个节点的值。对于每个节点的值都>=子树中每个节点值的堆，叫作“大顶堆”。对于每个节点的值都<=子树中每个节点值的堆，叫作“小顶堆”。
2、堆的实现（以大顶堆为例）：
<1>、堆的存储：
(1)、原理：
用数组存储堆，如果堆中的数据是从数组下标为1的位置开始存储的，数组中下标为的节点的左子节点，就是下标为
的节点，右子节点就是下标为
的节点，父节点就是下标为
的节点。堆中的数据是从数组下标为0的位置开始存储的，数组中下标为
的节点的左子节点的下标就是
，右子节点的下标就是
，父节点的下标就是
。
(2)、图示：
![]()
堆的存储
<2>、往堆中插入一个元素：
(1)、原理：
把新插入的元素放到堆的最后，然后进行调整，让其重新满足堆的特性，这个过程起了一个名字，叫作堆化（heapify）。堆化非常简单，就是顺着节点所在的路径，向上或者向下，对比，然后交换。让新插入的节点与父节点对比大小。如果不满足子节点小于等于父节点的大小关系，我们就互换两个节点。一直重复这个过程，直到父子节点之间满足刚说的那种大小关系。
(2)、图示：
![]()
堆的插入
(3)、代码：
public class Heap {
private int[] a; // 数组，从下标1开始存储数据
private int n; // 堆可以存储的最大数据个数
private int count; // 堆中已经存储的数据个数
public Heap(int capacity) {
a = new int[capacity + 1];
n = capacity;
count = 0;
}
public void insert(int data) {
if (count >= n) return; // 堆满了
++count;
a[count] = data;
int i = count;
while (i/2 > 0 && a[i] > a[i/2]) { // 自下往上堆化
swap(a, i, i/2); // swap()函数作用：交换下标为i和i/2的两个元素
i = i/2;
}
}
}
<3>、删除堆顶元素:
(1)、原理：
把最后一个节点放到堆顶，然后利用同样的父子节点对比方法。对于不满足父子节点大小关系的，互换两个节点，并且重复进行这个过程，直到父子节点之间满足大小关系为止。这就是从上往下的堆化方法。因为移除的是数组中的最后一个元素，而在堆化的过程中，都是交换操作，不会出现数组中的“空洞”，所以这种方法堆化之后的结果，肯定满足完全二叉树的特性。
(2)、图示：
![]()
删除堆顶元素
(3)、代码：
public void removeMax() {
if (count == 0) return -1; // 堆中没有数据
a[1] = a[count];
--count;
heapify(a, count, 1);
}
private void heapify(int[] a, int n, int i) { // 自上往下堆化
while (true) {
int maxPos = i;
if (i*2 <= n && a[i] < a[i*2]) maxPos = i*2;
if (i*2+1 <= n && a[maxPos] < a[i*2+1]) maxPos = i*2+1;
if (maxPos == i) break;
swap(a, i, maxPos);
i = maxPos;
}
}
<4>、时间复杂度：
一个包含个节点的完全二叉树，树的高度不会超过
。堆化的过程是顺着节点所在路径比较交换的，所以堆化的时间复杂度跟树的高度成正比，也就是
。插入数据和删除堆顶元素的主要逻辑就是堆化，所以，往堆中插入一个元素和删除堆顶元素的时间复杂度都是
。
二、堆排序：
1、堆排序的步骤：
堆排序的过程大致为两个步骤， 建堆和排序。
2、建堆：
<1>、步骤：
方法一：是在堆中插入一个元素的思路。尽管数组中包含个数据，但是可以假设，起初堆中只包含一个数据，就是下标为
的数据。然后，调用前面讲的插入操作，将下标从
到
的数据依次插入到堆中。这样我们就将包含
个数据的数组，组织成了堆。
方法二：第一种建堆思路的处理过程是从前往后处理数组数据，并且每个数据插入堆中时，都是从下往上堆化。而第二种实现思路，是从后往前处理数组，并且每个数据都是从上往下堆化。对下标从 开始到
的数据进行堆化，下标是
到
的节点是叶子节点，不需要堆化。实际上，对于完全二叉树来说，下标从
到
的节点都是叶子节点。
<2>、图示：
![]()
建堆
<3>、代码：
private static void buildHeap(int[] a, int n) {
for (int i = n/2; i >= 1; --i) {
heapify(a, n, i);
}
}
private static void heapify(int[] a, int n, int i) {
while (true) {
int maxPos = i;
if (i*2 <= n && a[i] < a[i*2]) maxPos = i*2;
if (i*2+1 <= n && a[maxPos] < a[i*2+1]) maxPos = i*2+1;
if (maxPos == i) break;
swap(a, i, maxPos);
i = maxPos;
}
}
<4>、建堆的时间复杂度：)
3、排序：
<1>、步骤：
建堆结束之后，数组中的数据已经是按照大顶堆的特性来组织的。数组中的第一个元素就是堆顶，也就是最大的元素。把它跟最后一个元素交换，那最大元素就放到了下标为的位置。这个过程有点类似“删除堆顶元素”的操作，当堆顶元素移除之后，把下标为
的元素放到堆顶，然后再通过堆化的方法，将剩下的
个元素重新构建成堆。堆化完成之后，我们再取堆顶的元素，放到下标是
的位置，一直重复这个过程，直到最后堆中只剩下标为
的一个元素，排序工作就完成了。
<2>、图示：
![]()
堆的排序过程
<3>、代码：
// n表示数据的个数，数组a中的数据从下标1到n的位置。
public static void sort(int[] a, int n) {
buildHeap(a, n);
int k = n;
while (k > 1) {
swap(a, 1, k);
--k;
heapify(a, k, 1);
}
}
<4>、排序的时间复杂度：)
4、堆排序的时间复杂度：
堆排序包括建堆和排序两个操作，建堆过程的时间复杂度是，排序过程的时间复杂度是
，所以，堆排序整体的时间复杂度是
。
