从Timer中学习优先队列的实现

anquan 发布于2019-08-16 10:32 / 2345人阅读

摘要：从中学习优先队列的实现是定时器的实现，用来调度定时执行的任务和执行一次的任务，就像的和的意思，它也可以作为后台程序运行。通过和的方法可以保证整个优先队列的关系，保证的是最小的。作用是构建堆，可以从的数组构建堆，来表示优先队列。

从Timer中学习优先队列的实现

Timer是Java定时器的实现，用来调度定时执行的任务和执行一次的任务，就像JavaScript的setInterval和setTimeout的意思，它也可以作为后台程序（Daemon）运行。

Timer

Timer调度的实现是通过TimerThread辅助类来实现的，在构造Timer实例的时候TimerThread就开始运行了；TimerThread需要从队列（TaskQueue）中获得需要被执行的任务（TimerTask），这是一个优先队列，TimeTask的executionTime（TimerTask设置要执行的时间Date.getTime()形式表示的）越小的越优先执行。

TimerThread如何调度

略

TaskQueue data structure

TaskQueue实现了优先队列的数据结构，内部是一个数组，数组内容实际上是从下标1开始填充的；它其实是用balanced binary heap来表示的，设父节点是queue[n]，则它的两个字节点分别是queue[2*n]和queue[2*n+1]
这个数据结构的API方法包括：

add(T object)

getMin()

removeMin()

fixDown(int k)

fixUp(int k)

heapify()

最重要的两个是fixDown和fixUp，表示从queue[k]节点位置开始demoting或promoting。

TaskQueue.fixDown

假设要操作的节点是queue[k]，那么它的子节点分别是queue[j]和queue[j+1]，j=k*2，对queue[k]做demoting处理，

    private void fixDown(int k) {
        int j;
        while ((j = k << 1) <= size && j > 0) {
            if (j < size &&
                queue[j].nextExecutionTime > queue[j+1].nextExecutionTime)
                j++; // j indexes smallest kid
            if (queue[k].nextExecutionTime <= queue[j].nextExecutionTime)
                break;
            TimerTask tmp = queue[j];  queue[j] = queue[k]; queue[k] = tmp;
            k = j;
        }
    }

1.首先比较两个子节点选出executionTime更小的那个，
2.如果右子节点的executionTime更小，则j++自增，这样就相当于选择了右节点（下次fixDown的位置从这里开始）
3.然后父节点和选中的更小executionTime子节点比较
4.如果父节点的executionTime更小，则交换父节点和这个子节点
那么为什么要执行2呢
之前，

之后，

如果是queue[j]变成了父节点就会破坏queue[n]<=queue[2*n+1]的关系。
然后就是一直fixDown到最后一个节点queue[size]。
我们可以思考下这个方法的时间复杂度是不是O(logn)。

TaskQueue.fixUp

假设要操作的节点是queue[k]，那么它的父节点分别是queue[j]，j=k/2，对queue[k]做promoting处理，

    private void fixUp(int k) {
        while (k > 1) {
            int j = k >> 1;
            if (queue[j].nextExecutionTime <= queue[k].nextExecutionTime)
                break;
            TimerTask tmp = queue[j];  queue[j] = queue[k]; queue[k] = tmp;
            k = j;
        }
    }

promoting比demoting简单一点，只需要比较queue[k]和queue[j]两个节点，然后做交换即可。

TaskQueue other methods

通过fixUp和fixDown的方法可以保证整个优先队列的关系，保证queue[1]的executionTime是最小的。
1.heapify()作用是构建堆，可以从{0,q[1],q[2],...,q[size]}的数组构建堆，来表示优先队列。

    void heapify() {
        for (int i = size/2; i >= 1; i--)
            fixDown(i);
    }

从中间下标到1做fixDown。

2.add(T object)，往数组中添加元素，重新构建堆

    void add(TimerTask task) {
        // Grow backing store if necessary
        if (size + 1 == queue.length)
            queue = Arrays.copyOf(queue, 2*queue.length);

        queue[++size] = task;
        fixUp(size);
    }

不过需要判断数组空间是否有剩余，没有则扩展数组，并拷贝原来的数组元素，最后对queue[size]节点，也是新元素做fixUp。
3.getMin() 直接获得queue[1]元素
4.removeMin() 将queue[size]节点替换queue[1]，然后对queue[1]做fixDown。

总结

这个TaskQueue的优先队列的实现代码是比较清晰的，重要方法的时间复杂度也可以算优秀。
阅读完这部分代码后或许可以进一步阅读PriorityQueue。
附：测试代码

私有云超融合服务器优先队列消息队列的实现 python优先队列队列实现原理

文章版权归作者所有，未经允许请勿转载,若此文章存在违规行为，您可以联系管理员删除。

转载请注明本文地址：https://www.ucloud.cn/yun/69961.html

从Vue.js源码看异步更新DOM策略及nextTick

摘要：我们发现默认是使用异步执行更新。优先使用，在不存在的情况下使用，这两个方法的回调函数都会在中执行，它们会比更早执行，所以优先使用。是最后的一种备选方案，它会将回调函数加入中，等到执行。写在前面因为对Vue.js很感兴趣，而且平时工作的技术栈也是Vue.js，这几个月花了些时间研究学习了一下Vue.js源码，并做了总结与输出。文章的原地址：https://github.com/ans...

leo108 2019-08-21 16:43 评论0 收藏0
从Bug中学习--Bug根因分析法

摘要：总结根因分析法是很有价值的，但并不是每一个都需要这样刨根问底的分析，也没有这样的精力和时间允许我们这样做。所以，在进行根因分析时，要以的价值作为选取标准。一提起测试，大多数人很容易就会联想到Bug。的确，测试的日常工作离不开Bug，测试工作很重要的一部分就是发现Bug。但是，发现Bug、解决Bug，就足够了吗？肯定不是的。 Bug是我们测试人员宝贵的财富，通过Bug我们可以获得经验，...

linkin 2019-05-29 17:07 评论0 收藏0
「真®全栈之路」Web前端开发的后端指南

前言在若干次前的一场面试，面试官看我做过python爬虫/后端的工作，顺带问了我些后端相关的问题：你觉得什么是后端？送命题。当时脑瓦特了，答曰：逻辑处理和数据增删改查。。。 showImg(https://user-gold-cdn.xitu.io/2019/4/24/16a4ed4fc8c18078); 当场被怼得体无完肤，羞愧难当。事后再反思这问题，结合资料总结了一下。发现自己学过的Re...

chuyao 2019-05-23 16:27 评论0 收藏0
「中高级前端面试」JavaScript手写代码无敌秘籍

摘要：第一种直接调用避免在不必要的情况下使用，是一个危险的函数，他执行的代码拥有着执行者的权利。来自于此外，实现需要考虑实例化后对原型链的影响。函数柯里化的主要作用和特点就是参数复用提前返回和延迟执行。手写路径导航实现一个new操作符实现一个JSON.stringify 实现一个JSON.parse 实现一个call或 apply 实现一个Function.bind 实现一个继承实现一个J...

Zhuxy 2019-05-23 16:26 评论0 收藏0
代码之髓读后感——如何高效的学习语言

摘要：代码之髓读后感如何高效的学习语言技术读后感王垠如何掌握程序语言代码之髓这本书里提出了三种学习语言的方法如何高效的学习语言在比较中学习在历史中学习在实践中学习在比较中学习通过比较多种语言，总结出某种语言的独有特点，以及多种语言的共有特点。 title: 代码之髓读后感——如何高效的学习语言date: 2017-07-08 17:17:00categories: 技术tags: 读后感 ...

ivyzhang 2019-08-15 10:36 评论0 收藏0