天天看点

经典算法题每日演练——第九题 优先队列

      前端时间玩小爬虫的时候,我把url都是放在内存队列里面的,有时我们在抓取url的时候,通过LCS之类的相似度比较,发现某些url是很重要的,

需要后端解析服务器优先处理,针对这种优先级比较大的url,普通的队列还是苦逼的在做FIFO操作,现在我们的需求就是优先级大的优先服务,要做

优先队列,非堆莫属。

一:堆结构

   1:性质

      堆是一种很松散的序结构树,只保存了父节点和孩子节点的大小关系,并不规定左右孩子的大小,不像排序树那样严格,又因为堆是一种完全二叉

树,设节点为i,则i/2是i的父节点,2i是i的左孩子,2i+1是i的右孩子,所以在实现方式上可以采用轻量级的数组。

经典算法题每日演练——第九题 优先队列

2:用途

    如果大家玩过微软的MSMQ的话,我们发现它其实也是一个优先队列,还有刚才说的抓取url,不过很遗憾,为什么.net类库中没有优先队列,而java1.5

中就已经支持了。

3:实现

 <1>堆结构节点定义:

       我们在每个节点上定义一个level,表示该节点的优先级,也是构建堆时采取的依据。

<2> 入队操作

      入队操作时我们要注意几个问题:

     ①:完全二叉树的构建操作是“从上到下,从左到右”的形式,所以入队的节点是放在数组的最后,也就是树中叶子层的有序最右边空位。

     ②:当节点插入到最后时,有可能破坏了堆的性质,此时我们要进行“上滤操作”,当然时间复杂度为O(lgN)。

经典算法题每日演练——第九题 优先队列

当我将节点“20”插入到堆尾的时候,此时破坏了堆的性质,从图中我们可以清楚的看到节点“20”的整个上滤过程,有意思吧,还有一点

就是:获取插入节点的父亲节点的算法是:parent=list.count/2-1。这也得益于完全二叉树的特性。

<3> 出队操作

       从图中我们可以看出,优先级最大的节点会在一阵痉挛后上升到堆顶,出队操作时,我们采取的方案是:弹出堆顶元素,然后将叶子层中

的最右子节点赋给堆顶,同样这时也会可能存在破坏堆的性质,最后我们要被迫进行下滤操作。

经典算法题每日演练——第九题 优先队列

我图中可以看出:首先将堆顶20弹出,然后将7赋给堆顶,此时堆性质遭到破坏,最后我们清楚的看到节点7的下滤过程,从摊还分析的角度上

来说,下滤的层数不超过2-3层,所以整体上来说出队的时间复杂度为一个常量O(1)。

最后我还扩展了一个弹出并下降节点优先级的方法,好吧,这个方法大家自己琢磨琢磨,很有意思的,实际应用中使用到了。

经典算法题每日演练——第九题 优先队列

继续阅读