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

Question

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

Answer 1

假设 "efficient" 指的是这些操作规模的复杂性，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

我的想法：

您将需要 2 张地图。
映射 1：整数作为键，频率作为值。
映射 2：将频率映射作为键，将整数列表作为值。
Add Integer：将整数添加到地图1。获取频率。将其添加到地图2中的频率键列表中。
删除整数：我们显然可以在这些操作中保持变量的最大频率。现在，从 map2 中删除具有此最大频率的密钥并减少最大频率。
所以，增删性能平均应该是O(1)。

在上面的场景中，我们在地图 1 中仍然会有整数，它们存在并且频率在从地图 2 中删除后是不现实的。在这种情况下，当添加相同的整数时，我们会进行按需更新在地图 1 中，意思是，如果该整数在地图 2 中不存在地图 1 中的当前频率，则意味着它已被删除，我们可以再次将其重置为 1。

实施：

import java.util.*;
class Foo{
    Map<Integer,Integer> map1;
    Map<Integer,Set<Integer>> map2;
    int max_freq;
    Foo(){
        map1 = new HashMap<>();
        map2 = new HashMap<>();
        map2.put(0,new HashSet<>());
        max_freq = 0;
    }


    public void add(int x){
        map1.putIfAbsent(x,0);
        int curr_f = map1.get(x);
        if(!map2.containsKey(curr_f)){
            map1.put(x,1);
        }else{
            map1.merge(x,1,Integer::sum);
        }

        map2.putIfAbsent(map1.get(x),new HashSet<>());
        map2.get(map1.get(x)-1).remove(x); // remove from previous frequency list
        map2.get(map1.get(x)).add(x);// add to current frequency list
        max_freq = Math.max(max_freq,map1.get(x));
        printState();
    }

    public List<Integer> delete(){
        List<Integer> ls = new ArrayList<>(map2.get(max_freq));
        map2.remove(max_freq);
        max_freq--;
        while(max_freq > 0 && map2.get(max_freq).size() == 0) max_freq--;
        printState();
        return ls;
    }

    public void printState(){
        System.out.println(map1.toString());
        System.out.println("Maximum frequency: " + max_freq);
        for(Map.Entry<Integer,Set<Integer>> m : map2.entrySet()){
            System.out.println(m.getKey() + " " + m.getValue().toString());
        }
        System.out.println("----------------------------------------------------");
    }

}

演示： https://ideone.com/tETHKV

注意： 对 delete() 的调用是分期付款的。

Answer 3

我们可以使用数据结构的组合。 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，按频率值排序。请注意，如下所述，在 add/delete 操作中保持列表排序不需要任何 log(n) 操作。

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

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

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

最后，将条目 (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，所以我们需要在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 映射中删除相应的键。此操作将花费 O(k) 时间，其中 k 是具有最大频率的元素数。

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

Which data structure supports given operations efficiently

algorithm

optimization

performance

memory-efficient

data-structures