c++ - 查找具有唯一标签的前 K 个元素的算法

Question

我有一个自定义结构数据:

struct mydata
{
    double distance;
    string label;
}

我将在循环中生成大量mydata。我想获得顶级的最小距离商品，同时它们的标签必须是唯一的。 现在我使用最大堆来解决这个问题。我的算法是这样的:

// get topK items with unique label
for i = 1:N
{
    mydata item = generate_a_data();
    if (max_heap.size() < K)
    {
        insert_to_max_heap(item);
    }
    else // max_heap is full
    {
        if (item.distance < max_heap(top).distance)
        {
            insert_to_max_heap(item);
        }
    }
}

问题发生在 insert_to_max_heap() 中，因为唯一标签的约束，我不能只用新项替换最大堆中的顶部节点，所以我必须迭代堆查找是否存在相同的标签。如果存在具有相同标签的节点，我只需更新旧节点的距离。伪代码:

insert_to_max_heap(item)
{
    for_each node in max_heap
    {
        if (node.label == item.label)
        {
            if (node.distance > item.distance)
            {
                // update min distance
                node.distance = item.distance;
            }
            return;
        }
    }
    // no identical label, replace the top node
    max_heap.top = item;
    sort_max_heap();
}

是否有更有效的方法来改进我的算法或解决问题的新想法？算法应该尽可能快，但我没有足够的空间来保存循环中的所有项目。

Answer 1

我认为您需要维护一个 HashMap ，其中键是标签，值是最大堆中结构的位置(或指针)。

当生成新的mydata时，首先检查 HashMap 中是否存在具有相同标签的结构体。如果是，则判断是否替换它(替换后，根据距离在堆中下移(如果需要的话)或不下移，否则确定是否将新的mydata插入到你的堆中，而不是'不要忘记同时更新您的 HashMap 。