可删除任意已知节点的左倾树
优先队列是一个非常有用的数据结构,一般用于多任务的优先权分配。比如一台打印机只能一个文档一个文档地打印,如果有多个打印任务,如何调度他们呢?一个简单的策略就是先来先打印(FIFO),可是如果一个等待处理的先来的任务有上千页,而后来的等待中的任务只有1,2页,那么仍然按照先来先打的策略将会很没有效率(恕我不解释"效率"这个词)。另外一个策略就是等待任务中页数最小的先打印。这个策略看上去更好一些。
我们现在的问题是如何调度类似的这些任务如何调度,合理的数据结构如何。这就要用到优先队列的这个数据结构了。一个有效的优先队列实现方案就是左倾树(Leftist Trees)。这在一些经典的数据结构和算法的书中都有介绍。
对这个数据结构稍加研究以后,就会发现它不能很好地解决一个特例,就是如果用户想取消一个还没有进行的任务(我想cancel一个打印文档是大家经常会遇到的)。解决这个特例直观的想法是重新构造左倾树,可是怎样做呢?上周五,布朗香写出了一个算法:可删除任意已知节点的左倾树。我有幸看到了这篇文章,记录于此。:)