Say I have two arrays, { energy and score }, and they could have elements like this:
E: 1 3 4 7
S: 16 10 5 1
What I want is the best score with the best energy. What data structure can support inserting items in a way that I don't have have an item with less energy and less score than another item i.e. for any i,j where i!=j => score[i] > score[j] || energy[i] > energy[j]
When inserting, I do three steps:
1- if any item has more or equal score and energy, return;
2- if any item has less or equal score and energy, remove this item;
3- insert the required item.
Here are some examples:
1- insert e=8, s=1. The arrays become:
E: 1 3 4 8
S: 16 10 5 1
^
2- insert e=5, s=6. The arrays becomes:
E: 1 3 5 8
S: 16 10 6 1
^
3- insert e=5, s=11. The arrays becomes :
E: 1 5 8
S: 16 11 1
^ (3,10) is removed because (5,11) has more energy and more score than it.
What data structure can support this in (hopefully) O(logn) time?