代码之家 › 专栏 › 技术社区 › JoshD

映射和最小堆以获得更好的速度

data-structures language-agnostic

2

JoshD · 技术社区 · 15 年前

一个map和一个min堆一起使用是否可以提供更好的摊余时间?

假设我有一个项目需要跟踪几个项目。这些项目具有过期时间和唯一ID:

class Item {
  ID uid;
  Time expiration;
};

对于这个例子,时间和ID都是原始的整型数据类型。我需要能够通过ID快速访问一个项目,我还需要能够找到所有项目的最短到期时间。

此外,我还将进行大量的插入和删除。

使用地图,我将得到O(log n)的分期查找次数。(是的,我将为此提供一个比较函数。)但是找到最小值是O(N)。

如果我使用一个最小堆,那么我按ID查找的时间将是O(n),但查找最小到期时间是O(1)。

在这两种情况下,插入都是O(log n)。对于此程序,仅对最小项执行删除操作。

或者,我可以两者兼用。跟踪相同对象的映射和最小堆。

考虑到这一设置,使用最小堆和映射来避免O(N)复杂性是否有益?

1 回复 | 直到 15 年前

1

bdonlan 15 年前

是的,使用双索引可能会对您有所帮助(给定足够数量的项以击败所涉及的常量因子)。但是,要小心-您需要跟踪项目在min堆中的位置,以便快速将其从堆中删除。