この操作のためのどのデータ構造ですか？

Question

は、私は2つのアレイ、energy (E) and score (S)を持っており、彼らはこのような要素を持っている可能性が言う：

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

私が欲しい最高のエネルギーで最高のスコアです。

1 - 任意の項目がある場合：私はi.e. for any i,j where i!=j => score[i] > score[j] || energy[i] > energy[j]

を挿入する他の項目より少ないエネルギーと少ないスコアでアイテムを持っていない方法でアイテムを挿入するサポートすることができますどのようなデータ構造で、私は3つの手順を行いますより多くのまたは等しいスコアとエネルギーを持っています。

2つ以上のアイテムにスコアとエネルギーがある場合は、このアイテムを削除します。

3必要な項目を挿入します。

ここにいくつかの例があります： 1- insert 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ヒープのメソッドは、特定のノードのすべての子がすべて親よりも低い値になるように、最大​​値を上に上げます。このプロパティは、サブノードを削除してヒーププロパティを維持するための条件として使用できます。あなたのケースでは、挿入されたノードのエネルギーとスコアの両方が特定の子よりも大きい場合はサブツリー全体を削除し、エネルギーやスコアが大きい場合はノードを1つだけ削除するように思えます。