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

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

频率节点可以定义为

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()操作可以实现如下：

add（x）：如果在elements地图中找不到x ，请检查的第一个元素是否 freq_nodes包含频率为1的Freq对象。如果是，则将x添加到values_with_frequencyFreq对象的集合中。否则，创建一个新的频率对象，频率值为1，并将x添加到（现在仅单个元素）包装的集合中values_with_frequency

否则，（例如，如果elements地图中已经存在x ），则在与x中的x in元素相对应的条目的值中，将指针跟随到的Freq对象中freq_nodes，从values_with_frequencyFreq对象的字段中删除x ，并注意x的当前值。 x的频率，即elements.get(x).frequency（在F中保持该值）的值。如果values_with_frequency由于删除而使集合变为空，请从freq_nodes链接列表中删除相应的节点。最后，如果freq_nodes链表中的下一个频率节点的频率为F + 1，只需将x添加到values_with_frequency下一个节点的字段中即可。否则，就像不存在频率为1的频率节点那样，只需创建频率节点即可。

最后，将条目添加(x, Freq)到elements地图。请注意，整个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，因此，在将N1从values_with_frequency集合{a，b}中删除之后，我们需要在DLL中的N1旁边插入一个节点N2。

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映射。此操作将花费O（k）时间，其中k是具有最大频率的元素数。