algorithm - 哪种数据结构有效地支持给定的操作

Question

我需要想一个数据结构，它可以有效地支持以下操作:
1) 加一个整数x
2) 删除一个具有最大频率的整数(如果有多个具有相同最大频率的元素则全部删除)。
我正在考虑实现一个线段树，其中每个节点存储其具有最大频率的子节点的索引。
任何有关如何解决此问题或应如何实现的想法或建议都将不胜感激。

Answer 1

我们可以使用数据结构的组合。用于维护频率映射的 HashMap ，其中键是整数，值是指向表示频率值和具有相同频率的整数集的“频率”节点的指针。频率节点将维护在按频率值排序的列表中。

频率节点可以定义为

class Freq {
   int frequency;
   Set<Integer> values_with_frequency;
   Freq prev;
   Freq next;
}

元素 HashMap 将包含以下形式的条目

Entry<Integer, Freq>

因此，对于数据集的快照，例如 a,b,c,b,d,d,a,e,a,f,b其中字母表示整数，以下是数据结构的样子。

c -----> (1, [c, e, f])
    |
    |
e --
    |
    |
f --

a -----> (3, [a, b])
    |
    |
b --

d --> (2, [d])

Freq 节点将维护在链表中，例如 freq_nodes , 按频率值排序。请注意，如下所述，在添加/删除操作时保持列表排序不需要任何 log(n) 操作。

add(x)的方式, 和 delete_max_freq()可以实现的操作如下

添加(x) :如果在 elements 中找不到 x map ，检查是否是 freq_nodes 的第一个元素包含频率为 1 的 Freq 对象。如果是这样，将 x 添加到 values_with_frequency Freq 对象的集合。否则，创建一个新的 Freq 对象，将 1 作为频率值并将 x 添加到(现在只有单个元素)包装集 values_with_frequency

否则，(即如果 x 已经存在于 elements 映射中)，按照元素中 x 对应的条目值中的指针指向 freq_nodes 中的 Freq 对象。 , 从 values_with_frequency 中删除 x Freq 对象的字段，记录 x 频率的当前值，即 elements.get(x).frequency 的值(在说 F 中保留此值)。如果设置values_with_frequency由于此删除而呈现为空，请从 freq_nodes 中删除相应的节点链表。最后如果 freq_nodes 中的下一个 Freq 节点链表的频率为 F+1，只需将 x 添加到 values_with_frequency下一个节点的字段。否则，只需创建一个 Freq 节点，就像在上面不存在频率为 1 的 Freq 节点的情况下所做的那样。

最后，添加条目 (x, Freq)到 elements map 。请注意，整个 add(x) 操作的时间复杂度为 O(1)。

下面是一系列 add() 操作以及数据结构的后续状态的示例。

添加(a)

a -> N1 :       freq_nodes :   |N1 (1,  {a}) |   ( N1 is actually a Freq object)

添加(b)

a -> N1 :        freq_nodes :   |N1 (1,  {a, b}) | 
b -> N1

添加(a)此时'a'指向N1，然而，它的当前频率是2，所以我们需要在DLL中的N1旁边插入一个节点N2，在从N1的values_with_frequency中删除它之后。设置 {a,b}

a -> N2 :       freq_nodes :   |N1 (1,  {b}) |  --> |N2 (2,  {a}) | 
b -> N1

这里要注意的有趣的一点是，每当我们将现有元素的频率从 F 增加到 F+1 时，我们需要执行以下操作

if (next node has a higher frequency than F+1 or we have reached the end of the list):

     create a new Freq node with frequency equal to F+1 (as is done above) 
     and insert it next to the current node
else :
    add ‘a’ (the input to the add() operation) to the ```values_with_frequency``` set of the next node

delete_max_freq() 操作只涉及删除链表的最后一个条目 freq_nodes ，并遍历包装集中的键 values_with_frequency从 elements 中删除相应的键 map 。此操作将花费 O(k) 时间，其中 k 是具有最大频率的元素数。