堆的原理实现详解以及堆的应用

• 堆是什么

  堆（heap）本质上就是一棵完全二叉树，只不过这棵完全二叉树有点特别，能够被称为堆的二叉树，除了它必须要是一棵完全二叉树外，它的每一个结点都必须大于或者小于其子节点。 解释一下就是对于树中的所有的结点都至少有一棵子树，对于这个结点的子树上所有的结点都必须要大于或者小于其父节点。因此，堆也是个递归的定义，通常，我们将结点都大于或者等于子树所有结点的堆称为最大堆 ；将结点都小于或者等于子树所有结点的堆称为最小堆 。如下图所示：

这里对堆结构的几个误区说一下，堆的定义中说的是，结点序大于其子树的结点，并不是说，第 i 层结点一定大于或者小于第 i + 1层的结点。这里需要注意。

• 堆的存储方式

  既然堆是一种二叉树，我们当让可以用类似二叉链表的方式来存放堆，但是二叉链表的方式，会存放额外的指针，因此会比较浪费内存。大家想想由于堆是一棵完全二叉树，数组是非常适合存储完全二叉树的，并且我们不需要通过指针就能定位到结点的左右子树，如图所示：

从图中我们可以看到在数组中第一个位置我们不存储任何元素，这样有什么好处呢？假如我们的某一个结点其数组索引为 i ，那么它的左节点索引为 i * 2，右结点的位置为 (i * 2) + 1，相应的，它的父节点的数组索引为 i / 2 。可以看到通过数组的索引和完全二叉树的性质，我们可以很容易访问到它的父节点和子节点，接下来我们来看看堆的相关操作。

• 插入结点

  在AVL树中我们知道当插入一个结点，需要维持二叉树的平衡需要做额外的操作，同样对于堆也是一样，当插入一个元素结点时，为了让这棵二叉树仍然保持堆的特性，我们需要对它进行调整，这个过程叫做堆化。 当我们对一个最大堆堆化的时候，其思路是，当插入一个元素时，我们将插入的元素和它的父节点元素比较，如果大于父节点，就将它与父节点交换，并且继续比较，直到父节点的值大于次结点，这时候堆化就完成了。如果是最小堆，思想是一样的，只是比较的时候条件不一样。我们以上图的最大堆为例，看看往堆中插入一个值为 28 的元素时的过程：

• 删除结点

  对于堆的结构，根据它的定义，假如我们要在最大堆的堆顶出删除一个元素，应该怎么做呢？可以知道，堆顶的元素是最大的元素，当删除后我们可以从它的左右子节点中选择一个大的然后放到堆顶，然后再从下面选择一个大的元素放在当前结点。但是这样的处理方式会有一个问题，什么问题呢？当我们如果一直访问到叶子结点中时，可能会将叶子结点中的元素往上提，那么这样就造成了，叶子结点中间出现了空缺结点。为了填补这个缺口，就需要将后面元素往前移动，这样很麻烦。那么有什么其他办法吗？
  我们可以采取这样的策略，当删除堆顶的元素后，我们将堆中最后一个元素拿出来放在堆顶，由于原先堆顶元素一定是最大的，由于它被删除了，那么最大的元素一定出现在堆顶元素的左右两个子节点中。因此我们的思路是这样的，将最后一个结点放入堆顶后，然后与子节点比较，假如子节点的值大于当前结点就将这两个结点交换，交换后继续向下与子节点比较，直到当前结点的值大于子节点，堆化就完成了。这也叫做从上往下堆化 方式，同样当我们插入元素的时候，叫做从下往上堆化 方式。

  我们看到，对于堆这种数据结构的插入和删除的过程，它只会沿着树的高度往上或者往下进行，也就是说每一次选择和比较只需要与子节点或者父节点比较，然后就会下降或者上升一层，因此它的时间复杂度是与树的高度相关的。对于一个包含 n 个结点的完全二叉树，它的高度为 log2n，因此，插入和删除操作的时间复杂度也为O(logn)。

• 堆排序

  对于堆的应用，堆排序肯定是一种，假如我们有一个数组，如何利用堆来给这个数组排序。从前面的分析，你要利用堆来排序，那你这个数组首先得是按照堆来存储的才行啊，因此第一步就是先将这个数组按照最大堆或者最小堆来存储。想一想，我们怎么来建立堆，假设开始堆中只有一个堆顶结点，利用前面的插入操作一步一步将结点插入到正确位置，直到将第n个元素也插入就完成了。实际上通过这种方式我们是将原来的数组分成了两部分，前面的那部分是已经建立好的堆，后面数组中的元素是待插入的元素。这样是一种方式。
  还有一种建立堆的方式是，我们从非叶子结点开始，依次以从上向下堆化的方式建立堆。这种方式是从数组的后面往前，而上面的第一种方式是从数组的头部开始往后建立堆。因为叶子结点没有子节点因此，不需要从叶子节点开始。说穿了，这种方式就是，就按照原先的数组把它当成一棵完全二叉树，只是从最后一个非叶子结点开始用从上往下堆化的方式调整它的位置，然后从倒数第二个非叶子结点以同样的方式调整，直到数组中第一个元素的位置也被调整好。第一步确定非叶子结点的位置：n / 2，这就是最后一个非叶子结点的数组索引。
  对于第二种建堆的方式，其时间复杂度是多少呢？首先我们需要对n/2 + 1个结点堆化，前面我们说过堆化的过程操作是logn。但是这里需要注意，这里的堆化过程并不是从顶点开始进行的。从算法的描述中可以知道，对于相同一层的所有结点，向下堆化最坏情况下的执行操作是一样的。对于一个n个结点的完全二叉树高度为logn。每一层的结点树为：2 ^ h，h为每一层的高度，堆顶的高度为0。因此所有非叶子结点的高度和应该为：s = 2^0 * h + 2^1* (h-1) + …+ 2^(h-1) * 1，可以利用错位相乘求得s = 2 ^(h+1) -h-2，由于h = logn，带入得到整个时间复杂度为O(n)。
  现在我们只是把堆给建好了，并没有排序。接下来我们就要对这个最大堆进行升序排序。 其实堆排序的过程与点像我们删除堆顶结点的过程，由于我们现在是按照最大堆的方式存储的，因此我们将堆顶的元素和数组中的最后一个元素交换，这样最大的元素就被放在了数组的最后一个位置，由于堆顶的元素改变了，因此需要重新调整再次从上往下堆化。完成后，我们再将堆顶元素与数组中倒数第二个元素交换，又再次堆化。以此往复直到堆中只有一个元素，这时整个数组就有序了。其实在代码实现中，我们只需要将数组分成两部分，前面的是堆，后面的是已经排好序的数组，用一个游标来标识。
  建堆过程的时间复杂度是 O(n)，排序过程的时间复杂度是 O(nlogn)，所以，堆排序整体的时间复杂度是 O(nlogn)。堆排序不是稳定的排序算法，因为在排序的过程，存在将堆的最后一个节点跟堆顶节点互换的操作，所以就有可能改变值相同数据的原始相对顺序。
  堆其实还有很多应用，例如优先级队列，搜索热门关键词等等，有兴趣可以去了解了解。

• 代码实现

// 堆以及堆的操作和排序
public class Heap {
  private int[] arry; // 数组，从下标1开始存储数据
  private int n;  // 堆可以存储的最大数据个数
  private int count; // 堆中已经存储的数据个数

  public Heap(int capacity) {
    arry = new int[capacity + 1];
    n = capacity;
    count = 0;
  }
  
  // 插入元素
  public void insert(int data) {
    //  // 堆满了
    if (count >= n) return;
    ++count;
    arry[count] = data;
    int i = count;
    while (i/2 > 0 && arry[i] > arry[i/2]) { // 自下往上堆化
      // 交换下标为i和i/2的两个元素
      swap(arry, i, i/2);
      i = i/2;
    }
  }
  
// 删除元素
public void removeMax() {
  if (count == 0) return -1; // 堆中没有数据
  arry[1] = arry[count];
  --count;
  heapify(arry, count, 1);
}

private void heapify(int[] arry, 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 && arry[maxPos] < arry[i*2+1]) maxPos = i*2+1;
    if (maxPos == i) break;
    swap(arry, i, maxPos);
    i = maxPos;
  }
}
}


// 堆排序
private static void buildHeap(int[] arry, int n) {
  for (int i = n/2; i >= 1; --i) {
    heapify(arry, n, i);
  }
}

private static void heapify(int[] arry, int n, int i) {
  while (true) {
    int maxPos = i;
    if (i*2 <= n && arry[i] < arry[i*2]) maxPos = i*2;
    if (i*2+1 <= n && arry[maxPos] < arry[i*2+1]) maxPos = i*2+1;
    if (maxPos == i) break;
    swap(arry, i, maxPos);
    i = maxPos;
  }
}

// n表示数据的个数，数组a中的数据从下标1到n的位置。
public static void sort(int[] arry, int n) {
  buildHeap(arry, n);
  int k = n;
  while (k > 1) {
    swap(arry, 1, k);
    --k;
    heapify(arry, k, 1);
  }
}