这个操作的数据结构是什么？

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最大到最高，这样任何特定节点的子节点都比父节点的值低。您可以将此属性用作删除子节点和维护堆属性的条件。在你的情况下，当插入节点的能量和分数都大于特定子节点时，听起来你可能会删除整个子树，并且只有在能量或分数较大时才删除单个节点。