在动态数组的前N个元素中查找最大元素

我正在寻找一种有效的算法或数据结构来查找multiset的前N个元素中的第二个参数的最大元素，在这个元素中，我将创建很多，所以我不能使用细分树。任何想法？在动态数组的前N个元素中查找最大元素

注意：我有多组对。

2017-02-25 luka25

与其他近亲选民不同，我在这个问题上的问题并不在于它太宽泛，而是目前还不清楚。你需要在这个“数组”上执行什么类型的插入和删除？这些需要具备哪些性能？（如果它实际上是一个数组，那么在任意位置的插入和删除无论如何都是O（大小），所以您似乎也可以直接遍历第一个* N *元素来查找最大的元素。）很明显，您有一些你没有提到的要求;大概他们从我们作为读者缺乏的上下文中显而易见。 – ruakh

那么我需要logN的复杂性。而且这个数组是一个按其他参数排序的多重集。 – luka25

当你说“数组”时，你究竟是什么意思？在大多数语言中，“数组”是一个非常特殊的事物，它不*支持对数时间的插入和删除。 – ruakh

您可以使用任何熟悉的平衡二叉搜索树实现。可以说最为人熟知的是AVL树，红黑树。

通常二元搜索树描述提及键和值对存储在树节点中。钥匙从左至右排列。插入，删除和查找操作使用O（log（n））时间复杂度，因为树是平衡的。平衡通常由树轮旋转支持。

为了能够在一个范围内，你必须存储和维护的节点的子树和大小的子树的在每个树节点即包括maxValue其他信息元素的发现最大值。为节点定义一个递归函数，以便在其子树的前N个节点中找到最大值。如果N等于大小您将在当前节点的maxValue中已经有答案。否则，如果某些元素位于threir子树中，则调用左/右节点的函数。

F(node, N) = 
    if N == size[node] : maxValue[node] 
    else if N <= size[leftChild[node]] : 
     F(leftChild[node], N) 
    else if N == size[leftChild[node]] + 1 : 
     MAX(F(leftChild[node], N), value[node]) 
    else : 
     MAX(maxValue[leftChild[node]], 
      value[node], 
      F(rightChild[node], N - size[leftChild[node]] - 1)

如果您熟悉分段树，您将不会遇到此实现的任何问题。我建议您使用Treap。这是随机二叉树。由于这种随机性，树总是保持平衡，为基本操作提供O（log（n））时间复杂度。 Treap DS有两个基本操作分割和合并，所有其他操作通过它们的使用来实现。 treap的优势在于你不必处理旋转。

编辑：没有办法来维持maxKey/minKey中的每个节点明确地为O（log（N））。

来源

2017-02-26 00:08:23

@ruakh，你是对的。我会更新答案。 –

@ruakh，谢谢你的重要提示！ –

在我编辑问题后，这仍然工作吗？因为数据应该保持按其他参数排序。 – luka25

在动态数组的前N个元素中查找最大元素

回答

相关问题