查找最大群集的最小值？

一个唯一的ID
值
创建时间
删除时间

我有两个输入流 - 一个告诉我当物品被创建时，会在物品被删除时通知我。调用已创建但尚未销毁的项目“生活”。

我可以跟踪使用堆的所有生活用品的最大值：

whenCreated(item): 
    i = heap.size 
    heap-up(item, heap.size) 
    heap.size = heap.size + 1 
    max-value = heap[0] 

whenDeleted(item): 
    ktem = heap[heap.size - 1] 
    heap.size = heap.size - 1 
    heap-up(ktem, index[item.id]) 
    heap-down(ktem, index[ktem.id]) 
    max-value = heap[0] 

heap-up(item, i): 
    while (i > 0): 
    j = floor((i-1)/2) 
    jtem = heap[j] 
    if (jtem.value > item.value): 
     break while 
    index[jtem.id] = i 
    heap[i] = heap[i] 
    i = j 
    index[item.id] = i 
    heap[i] = item 

heap-down(item, i): 
    while (2*i + 1 < heap.size): 
    if (2*i + 1 == heap.size or heap[2*i+1].value > heap[2*i+2].value): 
     j = 2*i + 1 
    else 
     j = 2*i + 2   
    jtem = heap[j] 
    if (jtem.value < item.value): 
     break while 
    index[jtem.id] = i 
    heap[i] = heap[i] 
    i = j   
    index[item.id] = i 
    heap[i] = item

如果我有n项，然后添加或删除一个需要O(log n)时间。

现在假设项目聚集，从而给出了两个项目，a和b，|a.value - b.value| < delta ⇒ a和b是相同的群集。

举例来说，如果我们已经得到了价值(1, 2, 3, 4, 7, 8, 11, 13, 14, 15, 16)和delta = 2，那么集群(1, 2, 3, 4)，(7, 8)，(11)和(13, 14, 15, 16)。

我想跟踪包含最大生命值的群集的最小值。我可以通过从堆中读取值来完成此操作，直到找到大小大于delta的值之间的间隔为止。但是，这需要O(n)时间，这看起来相当麻烦。

是否有O(log n)算法来跟踪该群集的最小值？

来源

2012-02-03 rampion

集群是传递的吗？例如，如果增量为2，那么1,2,3,4,5和6都在同一个群集中？ – templatetypedef 2012-02-03 18:53:39

我怀疑你只能使用当前堆做到这一点。看起来你需要一个单独的数据结构来有效地完成这项工作。虽然你的集群可以合并然后取消合并，但是不相交的集合会很好，所以你需要一些允许分离的东西（这种联合发现不会），也就是分区细化。 – davin 2012-02-03 18:57:28

templatetypedef的答案有效，尽管它似乎很难实现。如果你没有预料到许多临界情况，那么也许简单的'O（n）'解决方案是值得的。意思是，如果集群的末端经常变化，那么它不会是世界末日。你可以通过移动到BST并保持单个指针来稍微改进它，然后你的'O（n）'工作不会在删除时发生，只有在插入时才会发生，如果你期望小簇相对于'n'它不应该引人注目。 – davin 2012-02-03 19:45:02

您可以使用二叉树（或其变体）而不是堆。查找值和最小值都在O（logn）中。为每个群集构建单独的二叉树。

我不确定集群是如何完成的（您可以构建多个满足您提到的增量条件的集群，为什么选择这个特定的集群？）。您也可以考虑使用一个巨大的二叉搜索树来存储所有值并将某些节点指定为“簇头”（即包含此节点的子树中的元素是一个簇）。这样，您应该可以轻松地创建和删除新的群集。

来源

2012-02-03 18:50:58 ElKamina

我不确定我看到这是如何帮助你在集群中的因素。您如何有效地确定两个节点是否在同一个集群中？ – templatetypedef 2012-02-03 18:54:15

如果您需要合并两个集群会发生什么？或者将一个集群分成两部分？ – templatetypedef 2012-02-03 18:56:57

@templatetypedef为每个群集创建单独的树。 – ElKamina 2012-02-03 18:57:05

我相信你可以使用一个平衡二叉搜索树的splay树来保证每个操作的O（log n）摊销时间。

假设我们没有做任何聚类。在这种情况下，您可以将所有元素存储在平衡二叉搜索树中以获取O（log n）插入，删除和find-min。但是，随着集群，这改变。我的建议是保持群集中的BST值，并按照群集中保存的值的范围进行排序，其中每个群集都表示为其包含的节点的展开树。

要将元素插入到数据结构中，请在BST中搜索相关元素的前导和后继。如果节点不属于这两个群集，则从该节点创建一个单身显示树并将其插入BST。如果它包含在您找到的两个群集中的一个中，请将其插入该群集中。如果它包含在两个群集中，则从BST中删除两个群集，将它们合并成一个群集，将新节点插入该群集，然后将群集重新插入BST。 O（log n）查找时间在所有情况下找到两个集群，然后O（log n）分摊时间插入到集群中。合并两棵张开的树实际上在这里很快;因为他的集群之前没有合并过，所以一棵树的值都大于其他树中的所有值，所以合并可以通过退出指针在O（log n）分摊时间完成。移除两棵树并将其添加回去的成本也是O（log n）。

要查找最大群集的最小值，请在O（log n）时间中查找BST中的最大群集，然后查找在分期O（log n）时间中找到的群集的最小元素。

要删除元素，请在O（log n）时间内找到包含它的集群。如果它位于其自己的群集中，请从该树中删除该群集。如果不是，从它所在的集群中移除该元素，然后在该集群内找到它的前任者和后继者。如果它们在彼此的三角洲内，那么该群集仍然很好，我们就完成了。否则，群集必须拆分。在O（log n）摊销时间中，将群集分成小于或等于前导节点的群集，并且大于或等于后继节点，然后将两个群集重新插入树中。

总的来说，这给出了每个操作的O（log n）摊销。

希望这会有所帮助！

来源

2012-02-03 19:15:01 templatetypedef

我会看一看树木，谢谢！ – rampion 2012-02-03 21:51:23

查找最大群集的最小值？

回答

相关问题