数据结构问题

Question

这个问题来自我的考试,我无法解决它,想看看答案是什么(这不是作业,因为除了知识以外它不会帮助我).

我们需要创建一个数据结构来包含其键是实数的元素.
数据结构应具有以下功能:
Build(S,array):构建数据结构S,其中包含O(n)中的n个元素
插入(S,k)和删除(S,x)中的O(lgn)(k是一个element,x是数据结构中指向它的指针)
Delete-Minimal-Positive(S):删除带有最小正键的元素
Mode(S):返回O中最常用的键(1)

现在,在O(n)中构建通常意味着应该使用堆,但这不允许查找频率.我找不到任何办法这样做.我能想到的最好的是构建一个用于构建频率堆的红黑树(O(nlgn)).

我很想知道答案......

谢谢!

Answer 1

好吧，您可以使用哈希表来计算 O(1) 摊销时间内不同实数的出现次数，然后使用标准堆，其中项目是对（实数、出现次数）并对堆进行排序根据出现次数字段。

当插入键或删除键时，会将出现次数字段增加或减少 1，或者在极端情况下添加或删除堆元素。在这两种情况下，您都需要向上/向下渗透，因为排序字段已更改。

假设哈希表是 O(1) 操作，您有一个标准堆 + O(1) 哈希表，并且您可以在时间限制内获得上述所有操作。特别是，您可以通过读取堆的根元素来获取“模式”。