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

Question

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

Answer 1

假设“有效”是指这些操作的复杂程度，big-O风格的扩展方式，我认为其中包括：

以整数为键，其频率为值的哈希图
• 一种树结构（例如，可能是二进制搜索树），其中其节点具有代表频率的数字和具有该频率的数字的哈希集。

插入数字时：1.在哈希图中查找数字以查找其频率。 （O(1)）2.在树中查找频率（O(log N)）。从其收藏夹中删除该号码（O(1)）。如果集合为空，则从树（O(log N)）中删除频率。3.增加号码的频率。在哈希图中设置该值（O(1)）。4.在树（O(log N)）中查找其新频率。如果存在，则将数字添加到该集合中（O(1)）。如果不是，请添加一个新节点，并在其集合中添加该编号（O(log N)）。

[以最大频率删除项目时：1.从树中删除值最高的节点（O(log N)）。2.对于该节点集合中的每个数字，从哈希图中删除该数字的条目（对于每个删除的数字，O(1)）。

如果要添加和删除N个数字，则最坏情况应为O(N log N)，而不管频率的实际分布或数字的添加和删除顺序。

[如果您知道可以对要添加的数字进行的任何假设，则可以进行进一步的增强，例如使用索引数组而不是有序树。但是，如果您的输入是相当不受限制的，那么这似乎是一个很好的结构，可以处理所需的所有操作，而无需进入O(n²)领域。

Answer 2

我的想法：

• 您将需要两张地图。
• 映射1：整数作为键，频率作为值。
• 映射2：将频率映射作为键，将整数列表作为值。
• 添加整数：将整数添加到映射1。获取频率。将其添加到地图2中的频率键列表中。
• Delete Integer：我们显然可以在这些操作中的变量中保持最大频率。现在，从map2移除具有此最大频率并减小最大频率的键。
• 因此，添加和删除性能平均应为O（1）。

---

在上述情况下，我们将在映射1中仍然存在整数，并且从映射2中删除后的频率不切实际。在这种情况下，当添加相同的整数时，我们将在映射1中进行按需更新。 ，也就是说，如果映射1中的当前频率在映射2中不存在该整数，则意味着它已被删除，我们可以将其重新设置为1。

Answer 3

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

[频率节点可以定义为

class Freq {
   int frequency;
   List<Integer> values_with_frequency
}

然后，元素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节点将通过频率值维护在列表
sorted
中，例如freq_nodes。请注意，如下所述，将不需要任何log（n）操作来使列表在添加/删除操作上保持排序。add(x)和delete_max_freq()操作的实现方式如下
add
（x）：如果在elements映射图中找不到x，请检查前面是否存在，检查freq_nodes的第一个元素是否包含频率为1的频率对象。如果是，则将x添加到频率对象的values_with_frequency列表中。否则，创建一个频率值为1的新Freq对象，并将x添加到（现在仅单个元素）包装列表values_with_frequency[否则，（即，如果elements映射中已经存在x），请在与[in]中对应x元素的条目的值中的指针跟随[c0]中的Freq对象，从[c0]中删除x频率对象的字段，注意x频率的当前值，即freq_nodes的值（在F中保留此值）。如果由于此删除而使列表values_with_frequency变为空，请从elements.get(x).frequency链接列表中删除相应的节点。最后，如果values_with_frequency链表中的下一个Freq节点的频率为F + 1，只需将x添加到下一个节点的freq_nodes字段即可。否则，就像不存在频率为1的频率节点那样，只需创建频率节点即可。 
最后，将条目freq_nodes添加到values_with_frequency映射。我们可以使用数据结构的组合。一个hash_map，用于维护频率映射，其中键是整数，而value是指向“频率”节点的指针，该节点表示频率值和具有相同频率的整数集。频率节点将保留在按频率值排序的列表中。
[频率节点可以定义为
(x, Freq)
然后，元素HashMap将包含以下形式的条目：>
elements
因此，对于数据集的快照，例如class Freq {
   int frequency;
   List<Integer> values_with_frequency
}
其中字母表示整数，以下是数据结构的样子。
Entry<Integer, Freq>
Freq节点将通过频率值维护在列表
sorted
中，例如a,b,c,b,d,d,a,e,a,f,b。请注意，如下所述，将不需要任何log（n）操作来使列表在添加/删除操作上保持排序。
c -----> (1, [c, e, f])
    |
    |
e --
    |
    |
f --

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

d --> (2, [d])

和freq_nodes操作的实现方式如下
add
（x）：如果在add(x)映射图中找不到x，请检查前面是否存在，检查delete_max_freq()的第一个元素是否包含频率为1的频率对象。如果是，则将x添加到频率对象的elements列表中。否则，创建一个频率值为1的新Freq对象，并将x添加到（现在仅单个元素）包装列表freq_nodes[否则，（即，如果values_with_frequency映射中已经存在x），请在与[in]中对应x元素的条目的值中的指针跟随[c0]中的Freq对象，从[c0]中删除x频率对象的字段，注意x频率的当前值，即values_with_frequency的值（在F中保留此值）。如果由于此删除而使列表elements变为空，请从freq_nodes链接列表中删除相应的节点。最后，如果freq_nodes链表中的下一个Freq节点的频率为F + 1，只需将x添加到下一个节点的freq_nodes字段即可。否则，就像不存在频率为1的频率节点那样，只需创建频率节点即可。 
最后，将条目values_with_frequency添加到elements.get(x).frequency映射。请注意，整个add（x）操作将及时变为O（1）。
delete_max_freq
（）操作将只涉及删除链表values_with_frequency的最后一个条目，并迭代包装表values_with_frequency中的键以从(x, Freq)映射中删除相应的键。此操作将花费O（k）时间，其中k是具有最大频率的元素数。