2

我有一个工作列表和等待这些工作的工人队列。所有的工作都是一样的，但工人是不同的，并根据他们执行工作的能力进行分类。也就是说，第一个人可以最好地完成这项工作，第二个人可以做得更差一点，依此类推。工作总是被分配给当时空闲的人中技能最高的人。当一个人被分配一份工作时，他会退出队列一段时间。但是当他完成后，他又回到了他的位置。因此，例如，在某个时刻，工作队列看起来像：

[x, x, .83, x, .7, .63, .55, .54, .48, ...]

其中x's 代表失踪工人，数字显示离开工人的技能水平。当有新工作时，它被分配给第 3 名工人，作为可用工人中技能最高的一名。所以下一刻队列看起来像：

[x, x, x, x, .7, .63, .55, .54, .48, ...]

假设此时工人 #2 完成了他的工作并返回列表：

[x, .91, x, x, .7, .63, .55, .54, .48, ...]

我希望这个过程现在完全清楚了。我的问题是使用什么算法和数据结构来实现工人的快速搜索和删除以及插入回他的位置。

目前我能看到的最好的方法是使用已摊销的斐波那契堆O(log n)来删除最小元素（分配作业并从队列中删除工作人员）O(1)并将他插入回来，这非常好。但是，是否有更好的算法/数据结构可能考虑到元素已经排序并且不时地从队列中删除的事实？

4

2 回答 2

2

使用常规堆，它比斐波那契堆更容易实现，并且还支持插入和删除O(lg n)（删除与插入一样多，因此获得更便宜的插入并不值得）。与斐波那契堆相反，常规堆通常在标准库中实现，例如priority_queue在 C++ 中的 STL 中。

如果存在更快的数据结构，您可以使用它来执行比 更快的排序Omega(n lg n)，这在一般情况下是不可能的。如果技能级别的数字有一些特殊的属性（比如说，它们是限制范围内的整数），那么执行排序的速度可能比 快Omega(n lg n)，但我不知道在这种情况下是否存在更快的优先级队列。

（顺便说一下，“rambo coder”的评论是绝对正确的；您应该将堆的实际性能与未排序列表的性能进行比较）。

于 2012-11-23T17:30:34.337 回答
2

作为一个理论练习，您可以考虑对数据进行预处理，以将所有内容减少为小整数，从而在完整队列中占据位置。然后首先想到的是http://en.wikipedia.org/wiki/Van_Emde_Boas_tree，理论上它可以将 log n 减少到 log n。请注意，在本文的末尾，有一些关于不太实际的解决方案的想法。http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.137.8757的文章（Integer Priority Queues with Decrease Key in constant time...）声称在理论上比斐波那契树更好对于小整数键的情况，并确实注意到与排序问题的链接 - 并参考了另一篇带有排序链接的论文 - 也是非常理论的。

于 2012-11-23T20:25:53.640 回答