数据结构-堆

什么是堆

堆其实就是一棵完全二叉树，即若设二叉树的深度为h，除第 h 层外，其它各层 (1～h-1) 的结点数都达到最大个数，第 h 层所有的结点都连续集中在最左边。

定义为：具有n个元素的序列（h1,h2,...hn），当且仅当满足（hi>=h2i,hi>=h2i+1）或（hi<=h2i,hi<=2i+1） (i=1,2,...,n/2)时称之为堆。完全二叉树的根结点称为堆的顶。

可以注意到，堆仅保证元素和其子结点之间的关系，并不保证兄弟结点之间的关系。

常见的堆包括最大堆和最小堆。

最大堆

最大堆，顾名思义，堆顶的键值是所有堆结点键值中最大者。套用前面讲到过的规则，当且仅当满足（hi>=h2i,hi>=h2i+1）或（hi<=h2i,hi<=2i+1） (i=1,2,...,n/2)，所有父结点的键值均大于子结点。

heap_max.png

最小堆

由最大堆的定义，可以很容易的理解最小堆，即所有父结点的键值均小于子结点。

heap_min.png

堆的内存形式

堆的内存形式有两种，一种是链表，一种是数组。

• 链表

  
  heap_linked.png

• 数组

  
  heap_array.png
  

  用数组保存堆，可以通过数组的下标来表达结点之间的位置关系，不需要额外的空间来储存指针信息，可以在很大程度上节约空间。
  具体来说，对堆进行广度优先遍历（BFS），依次将结点键值放入数组。用数学的方式表达就是：
  （1）父结点的下标：i
  （2）左子结点下标：2 * i + 1
  （3）右子结点下标：2 * i + 2

堆的操作

对于一个堆，常用的操作有两种，插入一个新的结点和删除堆顶。

插入新的结点

向堆插入一个结点，首先要保证堆依然是一个完全二叉树，即必须保证一行（也就是一层）构建完成才能继续添加下一层的结点。这就意味着完全二叉树新增加结点的位置是唯一固定的。对应数组来说，就是在数组的末尾增加一个元素。

进一步，对这个完全二叉树进行调整，即移动父结点和子结点的相互位置关系，使其满足条件而重新成为堆。这种调整可以简单的看成是一些列的上浮（shift-up）操作。可以看看下面这个简单的图。

heap_insert.png

可以看到，所谓的shift-up，就是将新插入的结点不停的和其父结点进行比较，如果子结点的键值大于（最大堆）/小于（最小堆）其父结点，那么就对二者进行交换，因为这里是数组，所以仅需要交换结点之间的键值，直到子结点的键值不大于（最大堆）/不小于（最小堆）其父结点。

删除堆顶

和插入新的结点类似，删除堆顶，还是首先要保证堆依然是一个完全二叉树，即必须保证一行（也就是一层）全部删除之后才能继续删除上一层的结点。这就意味着完全二叉树删除的结点的位置是唯一固定的。对应数组来说，就是删除数组末尾的元素。

删除堆顶的操作可以分为3步：

1. 将堆顶结点和末尾结点交换（仅交换键值）
2. 删除末尾结点
3. 对新的完全二叉树进行调整，使其重新称为堆

步骤1和2非常简单，执行完成之后，新的完全二叉树如图所示：

heap_del_1.png

步骤3是问题的重点和难点，可以简单的看成是一些列的下沉（shift-down）操作。

对于某个结点（parent），所谓的shift-down，包括以下子步骤（这里以最大堆为例）：

3.1 选择子结点中键值较大的一个child_max
3.2 将child_max和parent进行比较，
  3.2.1 如果parent>=child_max，则该完全二叉树已经满足堆的条件，操作结束。
  3.2.2 如果parent<child_max，则交换parent和child_max
3.3 将child_max作为parent，回到3.1

以上面的堆为例：

heap_del_2.png

1）此时在结点（15，2）中选择较大的一个和1做比较，即15 > 1的，所以15上浮到之前的20的结点处。
2）同第1步类似，找出（14，10）之间较大的和1做比较，即14>1的，所以14上浮到原来15所处的结点。
3）因为原来14的结点是叶子结点，所以将1放在原来14所处的结点处。

构建堆

构建堆有两种方式，一种是从无到有，也就是一个不断插入结点的过程；而另一种就是在原有完全二叉树的基础上，按照某种规则对结点进行调整。

从无到有

从原理上说，从无到有的构建堆比较简单，对于每一个新增结点，对其进行插入操作，结果必然是一个堆。

在原有的完全二叉树上进行调整

在原有的完全二叉树上进行调整，稍微复杂一些，可以从最后一个非叶结点开始，对每个非叶结点进行shift-down操作。

该操作的难点在于如何找到“非叶结点”和“最后一个非叶结点”。考虑非叶结点的定义，一个结点如果有至少一个子结点，那么就称其为非叶结点。因此，我们只要遍历所有的结点（根结点除外）的父结点，就可以遍历所有的非叶结点。知道了如何找到“非叶结点”，找出“最后一个非叶结点”的方法显而易见，最后一个叶结点（数组的末尾）的父结点就是“最后一个非叶结点”。

shift-down和shift-up

通过之前的章节，不难看出，堆操作的核心是两个步骤：shift-down和shift-up，更进一步，这两个操作都是递归的。

shift-down

    /**
     * shift down current node.
     * If child is null, stop
     * If child is not null,
     *  if node.val < max(child.val), shift down.
     *  else stop
     */
    private static void shiftDown2(int curIndex){
        int childIndexLeft = curIndex * 2 + 1;
        int childIndexRight = curIndex * 2 + 2;

        if(childIndexLeft > curEnd){
            return;
        }else{
            int indexToBeCompared = childIndexLeft;
            if(childIndexRight <= curEnd && heapArray[childIndexLeft].val < heapArray[childIndexRight].val){
                indexToBeCompared = childIndexRight;
            }

            if(heapArray[curIndex].val < heapArray[indexToBeCompared].val){
                swapNode(curIndex, indexToBeCompared);
                shiftDown2(indexToBeCompared);
            }
        }
    }

shift-up

    /**
     * shift up current node.
     * If parent is null, stop
     * If parent is not null,
     *  if node.val > parent.val, shift up.
     *  else stop
     */
    private static void shiftUp(int curIndex){
        int parentIndex = (curIndex-1)/2;
        if(parentIndex < 0){
            return;
        }else{
            if(heapArray[curIndex].val > heapArray[parentIndex].val){
                swapNode(curIndex, parentIndex);
                shiftUp(parentIndex);
            }else{
                return;
            }
        }
    }

用途

不仅在面试中，堆在日常工作中也经常被使用。堆经常会被作为优先队列来使用，常见于例如任务调度，数组合并等场景。

Java实现

在java中，优先队列实现了堆的数据结构【1】。我之前的一篇文章Java 优先队列 （PriorityQueue）对优先队列进行了简单介绍，可以参考。
【1】https://docs.oracle.com/en/java/javase/11/docs/api/java.base/java/util/PriorityQueue.html

其他参考文章：
【2】最大堆（创建、删除、插入和堆排序）
【3】数据结构：堆（Heap）
【4】关于堆结构的详解
【5】构建堆的时间复杂度
【6】最大堆的插入/删除/调整/排序操作(图解+程序)（JAVA）