这个问题来自我的考试,我无法解决它,想看看答案是什么(这不是作业,因为除了知识以外它不会帮助我).
我们需要创建一个数据结构来包含其键是实数的元素.
数据结构应具有以下功能:
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)).
我很想知道答案......
谢谢!