data structure needed

[achoracho]

hello guys I wanted to ask you if you know of some data structure that gives you the max(min) element of an array with complexity of O(log n) (or less) and can update the value of any element in the array with complexity O(1).

[helios]

Yes:

template <typename T>
struct S{
    T data;
    int max, min;
};

where T is any linear data structure with O(1) updates (e.g. an array) and for all 0 <= i < data.size(), data[max] >= data[i] and data[min] <= data[i].

[helios]

Correction: This data structure does not fulfill the constraints.

[devonrevenge]

0 log n is your binary tree, that's something like

template <typename T>
struct S{
    T data;
    
    S* higher;
   S* lower;

};

Iterators can be set to search higher only or lower :/ thas complicated IM due to do this at uni, will teach you in a month xD

[helios]

Binary trees don't have O(1) updates.

Now I'm not sure if a solution exists.

[TheIdeasMan]

Hi,

I don't think you will get both those requirements at the same time.

std::set is often implemented as a binary tree, so that gives the O(log n). But not O(1) for update.

std::unordered_set is efficient for find - it splits the data into "buckets" and uses a hash function to find which bucket an element is in. But not so good to visit each item. If the data can be sorted once, it may not be so bad to do an insert - just possibly move an item from one bucket to another. Min /max would be easier then too.

To get O(1) for update, my guess is that you will need a contiguous container like an std::array or std::vector in which case you will have O(n) for max / min. That might not be the end of the world, O(n) is still reasonable in the scheme of things.

This is all based on the assumption that it is not feasible to sort, or sort again if something is inserted.

So std::unordered_set is looking reasonable. Maybe you should test both with some data ?

[dhayden]

Helios has the right idea, but it's sort of cheating. You could wrap an array and record the minimum and maximum values in the wrapper. Each time you update the array, you compare the new value to the recorded min and max, and update them accordingly. When you want to know the min and max, just return the recorded values.

Time to update 1 element is O(1).
Time to retrieve the min/max is O(1).

Of course, time time to insert N items in the collection is O(N) and the min/max time is amortized over each of those N inserts.

This assumes that you will never REMOVE items from the collection.

[helios]

My original solution doesn't work even if the size of the array is constant. Consider this:

state0: array.size() = 4, array zeroed, max = 0, min = 0
state1: array[0] = 1, max = 1, min = 0
state2: array[1] = 2, max = 2, min = 0
state3: array[2] = 3, max = 3, min = 0
state4: array[3] = 4, max = 4, min = 0 (incorrect)

[doug4]

@dhayden,

You are forgetting that updating the value of an element in the array is not O(1) if the value you are updating is the old min or the max but is not the new min or max. Now the update becomes at least O(log n) because of the requisite sort/search for min/max.

[Sh0es]

I would recommend using a vector (self-modifying array) to store your data. If you want search times for min or max values of less than O:n^2, you'll want to sort your array. Considering you are concerned about time complexity for searching I would also recommend using a fast sorting algorithm (something with O:n*log(n) time complexity).

You could also use a self-modifying binary tree (like an AVL tree), but those are complex and difficult to implement. If you have the time and knowledge to implement one I would definitely say to do it since it doesn't need to be sorted.

[helios]

Sh0es: Please read the thread carefully before posting.

If you want search times for min or max values of less than O:n^2

min and max search over an unsorted array takes O(n), not O(n^2).

[helios]

Okay, I figured something out, but it only works if we assume that the values can be mapped to a bounded subset of the naturals.

Consider that the binary representation of a number can be interpreted as a path on a binary tree. E.g. "10011" could mean "take the right child, then left, left, right, right, done". Now imagine a tree where every node has two attached values: a count, which is non-zero only for leaves, and an accum, which has the property that this->accum() = this->count() + this->left->accum() + this->right->accum() (obviously, nullptr->accum() == 0).
Finding a value in this tree takes O(log n) over the distance of the value to zero, unless the value is bounded, in which case it takes O(1). E.g. finding a 32-bit value always takes 32 steps.

When a value is added to the array, its full path is constructed on the tree and the count and accum values are updated accordingly. This takes O(1).
When a value is modified, the old value is found on the tree, the count of the node is decremented and the accum values of the ancestors are updated. Then the new value is processed as if it was being added. This takes O(1).
To find the maximum or minimum, search the tree for the right-most or left-most leaf with a non-zero count value, if necessary using the accum values to quickly discard empty sub-trees. This takes O(1).