优先队列、堆与堆排序详解

最近在LeetCode刷题时碰到了一道难度级别为hard的题：

给定两个大小分别为 m 和 n 的正序（从小到大）数组 nums1 和 nums2。请你找出并返回这两个正序数组的 中位数 。

这是LeetCode的第四题，我第一眼看到的时候感觉很简单，只需要将两个数组合并排序然后直接拿中位数就行了，但是我忘了归并排序怎么写？ 所以我又想了一招，求中位数只需要排除掉中位数前面的数字就行了，那我正好可以将这道题转化为求TopK的问题，求TopK问题最常用的方法是堆数据结构了。

可能是我直接用了Java中的PriorityQueue的缘故吧，提交的结果不尽如人意，不过我今天的主题并不是和大家研究这道算法题，而是想借此给大家讲讲什么是堆、优先队列和堆什么关系、堆排序又是什么，以及堆的使用场景。

1. 堆的概述

初学数据结构的小伙伴们可能没听过堆这个数据结构，但是只要有一定编程经验的人一定听过优先队列这个东西。

优先队列的特性是：在优先队列中的元素可以按照它的权重进行逐个出队。

如果你在优先队列中放一组订单数据，你可以让它们按照金额大小的顺序进行逐个pop，听起来很像将他们进行排序之后逐个pop，但实际上优先队列更常使用堆数据结构作为内部数据结构。

堆 (Heap) 通常是一个可以被看做一棵完全二叉树的数组对象。

堆是一类堆数据结构的总称，而在这里我们一般是使用二叉堆作为实现(下文的堆都指代二叉堆)。

使用二叉堆而不是用排序进行处理的关键在于，二叉堆更快，二叉堆的插入/删除时间复杂度是O(logN)，而最快的排序的时间复杂度也要O(NlogN)。

说到这，可能你还不太明白，二叉堆的构成是什么样的，也不明白二叉堆数据结构为何如此的高效，接下来我将用一张图为你表述一个二叉堆数据结构的样子。

这就是一个二叉堆，虽然看上去很像一个二叉树，虽然它的每个节点也都有左右节点，但是它和二叉树有着本质的不同。

二叉树的左右节点和它的中间节点都有相对的大小关系，但是在上面这张图上只能看出下层的节点比下层的节点大，根节点最小这种规律，所以二叉堆虽然表现形式像一个二叉树，但它不是。

二叉堆按照功能可以分为两种：最小堆和最大堆。

上图这个就是最小堆，最小堆的定义的是根节点小于所有的子节点，而对应的最大堆则是根节点大于所有的子节点，这类似于排序中的从小到大和从大到小。

2. 堆的push与pop

看完了堆长什么样，我们来说说二叉堆的插入(push)与删除(pop)。

先来说说二叉堆的pop好了，因为理解了pop就可以更好的理解push。

以上图中的最小堆举例，当它进行pop时，会把它的根节点删除并返回，同时因为二叉堆没了根节点，剩下的节点中要再选出一个最小的节点( 就像二叉树需要进行平衡一样 )，并将它放在根节点上，这个操作在堆中被称为下浮。

我们继续以这个最小堆为例，可我们把节点一pop出去之后，我们需要选择一个堆底的数据将它放在根节点，堆底的数据在树上表现的不明显，在下一节对这棵树进行平展之后就比较明显了，堆底的数据在树上肯定是最底层的其中一个，这里我就以节点五举例。

当我们把堆底的数据放在根节点之后很明显，这个堆不再符合二叉堆的定义了，那么我们就要将根节点的数据逐渐下沉。

下沉的过程就是不断的将自己与自己的两个子节点进行交换，由于我们是一个最小堆，所以我们会选择比较小的那个节点和自己交换。

依旧不满足二叉堆的定义，继续交换：

这样交换之后，就满足了二叉堆的定义，很明显，如果我们继续pop，下一个被取出的元素就是2，下一个根节点将会是3。

这个操作如果映射在优先队列上，就是不断取出权重最低的数据，或者不断取出权重最高的数据( 最大堆 )。

说完了pop，我们再来看看push。

很明显，有了下沉，我们还有一个对应的操作叫做上浮，这俩名字都非常形象的说明了它俩所做的事，继续拿下图举例：

我们对这个最小堆插入一个节点0：

插入都是直接放在堆的堆底，这里为了画着方便，所以我放在了最右边。

很明显，额，我已经说了很多次很明显了，可能不太明显，节点0的出现让这个二叉堆不符合它的定义了，因为插入的元素是放在堆底，所以我要将它往上移动，如果父节点的元素比我大，我就和它互换位置，因为这是最小堆。

现在节点0已经上移了，可以遇见的是，直到父节点比较小为止，它将继续上移。

最后它就上来了，这种让二叉堆变成它本来该有的那个样子的动作也被称为：堆序平衡。

3. 堆的构造

上面我们从理论上理解了二叉堆，现在要开始实操了。

其实从上面的图来看，大家可能以为要构造一个堆的话，用树形结构会比较方便，但是实际中用的更多的却是数组。

再来看看这个例子把，假如我们采用层序遍历的方式对这棵树进行遍历，会发现它可以平展为这样：

其中节点一是节点二和三的父节点，节点二则是节点四和五的父节点。

不知道是哪位学者发现了它们的关系，可能是我没有经过数学思维训练我一开始并没有发现。

当一个二叉堆平展为数组之后，对任意一个节点来说，它的左子节点的是它的下标乘于2，如果它的下标是i，则左子节点下标是2i，右子节点的下标是2i+1，而它的父亲则是i / 2( 舍弃余数 )。

那么当我们用数组来构造它时，我们可以将第一个数组元素作为空节点不使用，从第二个数组元素开始依次插入二叉堆上的所有元素，最后就是这样的：

利用数组，我们可以非常方便的进行数据交换，因为对任意一个数组下标进行操作的时间复杂度都是O(1)。

接下来，我们来看代码吧。

public class Heap {
    private Integer[] table = new Integer[100];

    Integer size = 0;

    public void push(Integer i) {
        size++;
        table[size] = i;
        swim();
    }

    private void swim(){
        Integer a = size;
        while (table[a/2] != null && table[a] != null &&  table[a] < table[a/2]) {
            if (table[a] < table[a/2]) {
                less(a, a/2);
                a = a / 2;
            }

        }

    }

    private void less(Integer a, Integer b) {
        Integer temp = table[b];
        table[b] = table[a];
        table[a] = temp;
    }

    public Integer pop() {
        Integer i = table[1];
        if (i == null) return null;
        table[1] = table[size];
        table[size] = null;
        size--;
        sink();
        return i;
    }

    private void sink(){
        Integer a = 1;

        while (2 * a <= size) {
            int b = 0;
            if (2 * a + 1 > size) {
                b = 2 * a;
            }else {
                if (table[2 * a] < table[2 * a + 1]) {
                    b = 2 * a;
                } else {
                    b = 2 * a + 1;
                }
            }
            if (table[a] > table[b]) {
                less(b, a);
                a = b;
            } else {
                break;
            }

        }
    }

   } 

正如上文所说，我用数组构造了这个堆，并实现了push和pop。

代码里面有一些可以简化的判断，我没简化，主要是为了留给读者练手，绝对不是因为我懒🐶。

同时，我还写了一个测试类，copy可以直接运行：

    public static void main(String[] args) {
        Heap heap = new Heap();
        heap.push(10);
        heap.push(500);
        heap.push(200);
        heap.push(0);
        heap.push(100);
        heap.push(20);
        heap.push(30);
        heap.push(80);
        heap.push(300);
        heap.pop();
        System.out.println(Arrays.toString(heap.table));

    }

用这个测试类可以检验我上面代码的正确性，我测试了几遍都没发现问题，读者里面如果有捉虫高手可以帮我看一哈～

4. 堆排序

堆排序是一种基于二叉堆的排序，既然二叉堆每次都可以输出它最大或者最小的元素，那么我们将这个二叉堆完全输出之后，岂不就是一个排好序的数组吗？ 基于这种思想，我用上面的二叉堆数据结构写了一个测试用例：

    public static void main(String[] args) {
        Heap heap = new Heap();
        heap.push(10);
        heap.push(500);
        heap.push(200);
        heap.push(0);
        heap.push(100);
        heap.push(20);
        heap.push(30);
        heap.push(80);
        heap.push(300);
        List<Integer> array = new ArrayList<>();
        int count = heap.size;
        for (int i = 0; i < count; i++) {
            array.add(heap.pop());
        }
        System.out.println(array);
        System.out.println(Arrays.toString(heap.table));
    }

通过输入一些测试数据之后，利用循环将整个二叉堆不断的pop，直到为空，然后我们再打印这个新的数组，就可以看到已经排好序的数据了：

[0, 10, 20, 30, 80, 100, 200, 300, 500]

那么它的时间复杂度是多少呢？

其实所有的排序算法平均情况下都无法打破O(N)，也就是说最低也要是O(NlogN)级别的，这个堆排序也不例外，它的时间复杂度也是O(NlogN)。

5. 堆的应用

聊起堆的应用，我想起在一次公司的内部分享上，有个同组的开发分享了node.js的源码，虽然我忘了为什么我一个后端要去看那个，但是我记得我在里面看到了堆数据结构的应用，那就是js的定时器。

定时器一般使用setInterval() 或者 setTimeout() 进行设置，它们的内部其实都是存储在一个堆里面，很明显在定时器这个应用场景上是一个最小堆，也就是定时时间短的任务在比堆中的位置比较靠前。

为此我还专门查询了定时器的设计方案，一般分为时间轮和时间堆，很明显node.js中就使用了第二种方案。

除了上面这个，我能立马想起的另一个应用就是优先队列了，因为堆的特性导致它每次插入和删除的时间复杂度都是O(logN)，这要比一个排好序的队列再进行插入或者删除快多了。

结语

文章的最后，说回最开始那道题，其实用堆来解不是最有效的，因为题中的数据是有序的，单纯的使用堆来解题纯粹是浪费了有序这个条件。

比较好的方式是使用二分法进行求解，能达到O(logN)的速度。

在解答无序数据的topK问题上，堆才更有效率。

最近陆陆续续加上本篇写了四篇关于数据结构的文章，一共提到了七种数据结构，这七个是我认为一个开发者必须要掌握的七种数据结构，所以下一篇我应该不会更数据结构了，后续会继续更，下一篇打算写一篇常用算法合集。

比如选择排序、归并排序、快速排序之类的常见算法，可以不会手写，但是其思想还是有必要了解的。

最后，如果文章对您有帮助，还请大家多多点赞转发，你们的支持才是我不竭的创作动力。

大家，下篇见。

参考书目：

1. 算法第四版

推荐阅读

1. 详解哈希数据结构，手写哈希表
2. 树、二叉树与手写AVL，树型数据结构详解