用于有效返回哈希表的前K个条目的数据结构(地图,字典)

Question

这是一个描述:

它的操作类似于带有get,put和remove方法的常规地图,但有一种getTopKEntries(int k)获取前K个元素的方法,按键排序:

对于我的具体使用情况下,我添加,删除,并在结构调整很多价值观,但在任何一个时间有大约500-1000元; 我想有效地返回前10个键的条目.

我希望为O(1) get,put和remove运营,并getTopKEntries以仅取决于K,没有在地图的大小.

那么有效返回地图的前K个元素的数据结构是什么？

我的另一个问题是类似的,但是用于返回地图的所有元素,按键排序.

如果有帮助,则键和值都是4字节整数.

Answer 1

二叉搜索树（即std::map在 C++ 中）听起来像是完美的结构：它\xe2\x80\x99 已经按字典顺序排序，即简单的中序遍历将产生按升序排列的元素。因此，迭代前k个元素将直接产生前k 个元素。

\n\n

此外，由于您预见到大量的 \xe2\x80\x9cremove\xe2\x80\x9d 操作，因此哈希表无论如何都不会很适合：删除操作会破坏哈希表的负载因子特征，从而导致导致运行时间迅速恶化。

\n

二叉树在平均情况下需要 O(log n) 时间，但在最坏情况下需要 O(n) 时间。不是真正的 O(1) .. 我认为在这种情况下，如果不使用 TreeMap （二叉树 + 哈希图）， O(1) 是不可能的。 (2认同)