在動態數組的前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個元素中查找最大元素

回答

相關問題