CODEWITHSUNDEEP
c#arraysdata-structures
Ayman El Temsahi
Ayman El Temsahi

Reputation: 2610

What data structure for this operation?

Say I have two arrays, energy (E) and score (S), 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?

Upvotes: 1

Views: 78

Answers (1)

user5803074
user5803074

Reputation:

My solution to this problem is to use a max-heap that stores a pair structure as the value of its nodes. If you're not familiar with heaps, the CLRS book, chapter 6 has the best discussion I've read of them.

The max-heapfiy method of a heap bubbles up the max to the top, such that any particular node's children all have lower value than their parent. You can use this property as a condition for removing subnodes and maintaining the heap property. In your case, it sounds like you may be deleting entire subtrees when both energy and score of the inserted node are greater than a particular child, and only deleting a single node when either energy or score is greater.

Upvotes: 1

Related Questions