数据结构问题
这个问题来自我的一次考试，我无法解决它，想看看答案是什么（这不是作业，因为它除了知识之外对我没有任何帮助）。
我们需要创建一个数据结构来包含键为实数的元素。
数据结构应具有以下功能：
Build(S, array)：在 O(n) 内构建具有 n 个元素的数据结构 S
O(lgn) 中的 Insert(S, k) 和 Delete(S, x)（k 是一个元素，x 是数据结构中指向它的指针）
Delete-Minimal-Positive(S)：删除正键最小的元素
Mode(S)：在 O(1) 中返回 S 中最频繁的键
现在，在 O(n) 中构建通常意味着应该使用堆，但这不允许找到频率。我找不到任何方法来做到这一点。我能想到的最好办法是构建一个红黑树（O(nlgn)），它将用于构建频率堆。
我很想知道答案...
谢谢！
This question is from an exam I had, and I couldn't solve it and wanted to see what the answer is (this is not homework, as it will not help me in anything but knowledge).
We need to create a data structure for containing elements whose keys are real numbers.
The data structure should have these functions:
Build(S, array): Builds the data structure S with n elements in O(n)
Insert(S, k) and Delete(S, x) in O(lgn) (k is an element, x is a pointer to it in the data structure)
Delete-Minimal-Positive(S): Remove the element with the minimal positive key
Mode(S): returns the key that is most frequent in S in O(1)
Now, building in O(n) usually means a heap should be used, but that does not allow to find frequencies. I couldn't find any way to do this so. Best I could come up with is building a Red-Black-Tree (O(nlgn)) that will be used to build a frequency heap.
I'm dying to know the answer...
Thanks!
如果你对这篇内容有疑问，欢迎到本站社区发帖提问 参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。
绑定邮箱获取回复消息
由于您还没有绑定你的真实邮箱，如果其他用户或者作者回复了您的评论，将不能在第一时间通知您！
发布评论
评论（4）
仅使用比较模型，这个问题没有解决方案。
元素独特性问题具有可证明的 Omega(nlogn) 下界。这个（元素不同性）问题基本上是确定数组的所有元素是否不同的问题。
如果您的问题有解决方案，那么我们可以在 O(n) 时间内回答元素独特性问题（在 O(n) 时间内找到最频繁的元素，并再次查看该元素是否有多个实例在 O(n) 时间内）。
所以，我建议你向你的教授询问计算模型。
Using just the comparison model, there is no solution to this problem.
The Element Distinctness Problem has provable Omega(nlogn) lower bounds. This (element distinctness) problem is basically the problem of determining if all the elements of an array are distinct.
If there was a solution to your problem, then we could answer the element distinctness problem in O(n) time (find the most frequent element in O(n) time, and see if there are more than one instances of that element, again in O(n) time).
So, I suggest you ask your professor for the computational model.
好吧，您可以使用哈希表来计算 O(1) 摊销时间内不同实数的出现次数，然后使用标准堆，其中项目是对（实数、出现次数）并对堆进行排序根据出现次数字段。
当插入键或删除键时，会将出现次数字段增加或减少 1，或者在极端情况下添加或删除堆元素。在这两种情况下，您都需要向上/向下渗透，因为排序字段已更改。
假设哈希表是 O(1) 操作，您有一个标准堆 + O(1) 哈希表，并且您可以在时间限制内获得上述所有操作。特别是，您可以通过读取堆的根元素来获取“模式”。
Well, you can use a hash table to calculate the number of occurrences of distinct real numbers in O(1) amortized time, and then use a standard heap where the items are pairs (real number, number of occurrences) and the heap is sorted according to the number of occurrences field.
When you insert a key or delete a key, you increment or decrement the number of occurrences field by one, or in the extreme cases add or remove a heap element. In both cases you need to percolate up / down because the ordering field has changed.
Assuming the hash table is O(1) operation, you have a standard heap + O(1) hash table and you get all the operations above within the time limits. In particular, you get the "mode" by reading the root element of the heap.
我认为以下解决方案是可以接受的。它基于两种数据结构：
二叉堆保存元组，其中包含（元素值，元素的频率），堆是建立在频率之上的，因此它使我们能够在 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)。
抱歉，如果我错过了什么。
I think the following solution will be acceptable. It based on two data stuctures:
Binary heap holds tuple, that contain (element value, frequence of element), heap is builded on frequencies, so it's give us ability to find mode in O(1).
Red black tree contains a tuple that hold (element value, pointer to same element value in heap)
When you need to insert new element, you will try to find element(it takes O(log n)), if search was succeful, than go to the pointer from element founded in RB-tree, increase frequence, and rebuild heap(also O(log n)). If search didn't find such element than insert it into RB-tree(O(log n)) and to heap with value = (element, 1) (also O(1)), set a pointer in RB-tree to new element in heap.
Initial building will take O(n), because building both structures from set of n element takes O(n).
Sorry, if I am miss something.
对于频率：
每个条目都双向链接到自己的频率/计数器（使用哈希表）
频率在链接列表中。
需要在链表上向上/向下移动频率（删除插入元素），但最大差值为 1。
因此，频率链接到 +1 和 -1 频率元素的指针。
（有例外但可以处理）
For frequencies:
Each entry is bi-directionaly linked to own frequencies/counters (use hash table)
Frequencies are in linked list.
There is need to move frequency up/down over linked list,(deleting inserting element) but for max difference of 1.
Frequencies are thus linked to pointer of +1 and -1 frequency element.
(there are exceptions but can be handled)