lad*_*adi 5 java algorithm priority-queue
我正在寻找一个有效的数据结构来表示优先级列表.具体来说,我需要为一组项目分配优先级,并仅返回最高评分项目.我已经查看了优先级排队,但这些队列似乎并不适合我的需求.一旦我从队列中轮询最高评级项目,他们将重新组织堆结构.
最简单的解决方案当然是链表,在最坏的情况下,插入操作需要很长时间.
有没有人有更好的解决方案？
小智 5
堆看起来非常合适，但似乎你的做法是错误的。
假设您想要前 x 个元素（顺便说一句，这个 x 与 n 相比如何？）
您正在做的是将所有内容放入最大堆并获取顶部 x。
我建议您使用恰好包含 x 个元素的最小堆。
您插入堆的前 x 个元素。
下一个传入元素，您将与堆中的最小值进行比较，这可以非常快地完成（O(1) 时间）。如果较小，则忽略传入元素。
如果传入元素大于 min，则增加传入元素的 min 并将其在堆中筛选。最坏情况下这应该是 logx 时间。
完成后（在 nlogx 时间内），您可以在 O(xlogx) 时间内按排序顺序从堆中检索元素。
根据数据的大小（以及 x 的大小），使用此最小堆解决方案可能会非常快。
如果您确实希望插入速度超快并且不太关心检索，那么您也可以执行以下操作。
按元素出现的顺序将元素插入到向量（具有摊销 O(1) 插入时间的数组）中。
使用选择算法找到第 x 个最大元素（在 O(n) 时间内，但常数可能很大）。假设这个数字是S。
现在遍历数组，将每个元素与 S 进行比较，并选择与 S 一样大的元素。
如果 x 的大小合理并且与 n 相当（例如 n/2 或其他），这可能会很好，但如果 x 与 n 相比很小，我建议使用最小堆。