查找最大羣集的最小值？

一個唯一的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

查找最大羣集的最小值？

回答

相關問題