這個操作的數據結構是什麼？

Question

說我有兩個數組，energy (E) and score (S)，他們能有這樣的內容：

E = {1 , 3 , 4, 7}; 
S = {16, 10, 5, 1}; 

我要的是最好的能量的最好成績。哪些數據結構可以支持插入的方式的項目，我沒有擁有的項目使用更少的能源和更少的分數比其他項目i.e. for any i,j where i!=j => score[i] > score[j] || energy[i] > energy[j]

插入時，我做的三個步驟：

1，如果任何項目有更多或同等的分數和能量，回報;如果有任何項目的分數和能量較少或相等，請刪除此項目;

3-插入所需的項目。

以下是一些示例： 1-插入e = 8，s = 1。陣列成爲：

E = {1 , 3 , 4, 8}; 
S = {16, 10, 5, 1}; 
       ^

2-刀片e=5，s=6。陣列變爲：

E = {1 , 3 , 5, 8}; 
S = {16, 10, 6, 1}; 
      ^

3-插入e = 5，s = 11。該陣列變成：

E = {1 , 5 , 8}; 
S = {16, 11, 1}; 
     ^ (3,10) is removed because (5,11) has more energy and more score than it. 

什麼數據結構可以支持這一點（希望）O（LOGN）的時間？

Answer 1

我對此問題的解決方案是使用存儲pair結構作爲其節點值的max-heap。如果你不熟悉堆，CLRS book, chapter 6有我讀過的最好的討論。

堆的方法max-heapfiy最大到最高，這樣任何特定節點的子節點都比父節點的值低。您可以將此屬性用作刪除子節點和維護堆屬性的條件。在你的情況下，當插入節點的能量和分數都大於特定子節點時，聽起來你可能會刪除整個子樹，並且只有在能量或分數較大時才刪除單個節點。