这道题是我考试时出的，我解不出来，想看看答案是什么（这不是作业，因为它除了知识之外对我没有任何帮助）。
我们需要创建一个数据结构来包含键为实数的元素。
数据结构应具有以下功能：
Build(S, array)：在 O(n) 中构建具有 n 个元素的数据结构 S
O(lgn) 中的 Insert(S, k) 和 Delete(S, x)（k 是一个元素，x 是数据结构中指向它的指针）
Delete-Minimal-Positive(S)：删除正键最小的元素
Mode(S)：返回 S 中出现频率最高的键，时间复杂度为 O(1)
现在，以 O(n) 构建通常意味着应该使用堆，但这不允许找到频率。我找不到任何方法来做到这一点。我能想到的最好办法是构建一个红黑树（O(nlgn)），它将用于构建频率堆。
我很想知道答案...
谢谢！
仅使用比较模型，这个问题没有解决方案。
元素独特性问题具有可证明的 Omega(nlogn) 下界。这个（元素不同性）问题基本上是确定数组的所有元素是否不同的问题。
如果你的问题有解决方案，那么我们可以在 O(n) 时间内回答元素独特性问题（在 O(n) 时间内找到最频繁的元素，并查看该元素是否有多个实例，再次在 O(n) 时间内）。
所以，我建议你向你的教授询问计算模型。
那么，您可以使用哈希表来计算 O(1) 摊销时间内不同实数的出现次数，然后使用标准堆，其中项目是对（实数，出现次数），堆为根据出现次数字段排序。
插入键或删除键时，会将出现次数字段递增或递减 1，或者在极端情况下添加或删除堆元素。在这两种情况下，您都需要向上/向下渗透，因为排序字段已更改。
假设哈希表是 O(1) 操作，你有一个标准堆 + O(1) 哈希表，并且你可以在时间限制内获得上述所有操作。特别是，您可以通过读取堆的根元素来获取“模式”。
我认为以下解决方案是可以接受的。它基于两种数据结构：
二叉堆保存元组，其中包含（元素值，元素频率），堆是建立在频率之上的，因此它使我们能够在 O(1) 中找到众数。
红黑树包含一个元组，其中包含（元素值，指向堆中相同元素值的指针）
当您需要插入新元素时，您将尝试查找元素（需要 O(log n)），如果查找成功，则从 RB 树中创建的元素开始查找指针，增加频率，并重建堆（也是 O(log n))。如果搜索没有找到这样的元素，则将其插入 RB-tree(O(log n)) 并使用 value = (element, 1) （也是 O(1)）堆，将 RB-tree 中的指针设置为 new堆中的元素。
初始构建将花费 O(n)，因为从 n 个元素集合构建两个结构需要 O(n)。
抱歉，如果我错过了什么。
对于频率：
每个条目都双向链接到自己的频率/计数器（使用哈希表）
频率在链接列表中。
需要在链表上上下移动频率（删除插入元素），但最大差值为 1。
频率因此链接到+1和-1频率元素的指针。
（有例外但可以处理）
平衡二叉搜索树（BST）和频率哈希图可以串联使用，以有效管理具有实数键的元素，同时支持必要的操作。按排序顺序维护元素允许执行插入、删除和确定最小正键的 (O(\log n)) 操作。 BST 的例子有红黑树和 AVL 树。同时，哈希映射记录每个键的频率，从而能够 (O(1)) 检索最常用的键。创建数据结构首先需要 (O(n \log n)) 时间复杂度，因为所有元素都必须插入到 BST 中，并且它们的频率必须在哈希映射中更新。插入、删除和模式检索是有效管理的后续操作，复杂度分别为 (O(\log n)) 和 (O(1))。