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

本文关键字：数据结构 是什么 操作 | 更新日期: 2023-09-27 18:03:24

假设我有两个数组，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-如果任何物品的分数和能量大于或等于，返回;

2-如果任何物品的分数和能量低于或等于该物品，移除该物品;

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)时间内支持这一点?

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

我对这个问题的解决方案是使用存储pair结构的max-heap作为其节点的值。如果你不熟悉堆，CLRS书的第6章有我读过的关于堆的最好的讨论。

堆的max-heapfiy方法将最大值冒泡到顶部，这样任何特定节点的子节点都具有比父节点更低的值。您可以将此属性用作删除子节点和维护堆属性的条件。在您的情况下，当插入节点的能量和分数都大于特定子节点时，听起来您可能会删除整个子树，并且仅在能量或分数大于时删除单个节点。

相关文章：