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

优先队列、堆与堆排序详解我今天的主题并不是和大家研究这道算法题,而是想借此给大家讲讲什么是堆、优先队列和堆什么关系、堆排序又是什么,以及堆的使用场景。

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

给定两个大小分别为 mn 的正序(从小到大)数组 nums1nums2。请你找出并返回这两个正序数组的 中位数

这是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,树型数据结构详解

今天的文章优先队列、堆与堆排序详解分享到此就结束了,感谢您的阅读。

版权声明:本文内容由互联网用户自发贡献,该文观点仅代表作者本人。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容, 请发送邮件至 举报,一经查实,本站将立刻删除。
如需转载请保留出处:https://bianchenghao.cn/18099.html

(0)
编程小号编程小号

相关推荐

发表回复

您的电子邮箱地址不会被公开。 必填项已用*标注