4

I am self studying for an algorithms course, and I am trying to solve the following problem:

Describe a data structure to store a set of real numbers, which can perform each of the following operations in O(1) amortized time:

Insert(x) : Deletes all elements not greater than x, and adds x to the set.
FindMin() : Find minimum value of set.

I realize that findmin kind of becomes trivial once you have Insert, and see how with a linked list implementation, you could delete multiple elements simultaneously (ie O(1)), but finding out which link to delete (aka where x goes) seems like an O(n) or O(log n) operation, not O(1). The problem gave the hint: Consider using a stack, but I don't see how this is helpful.

Any help is appreciated.

The original question is below:

Original Problem

Improve this question
8
  • O(1) is constant time. I'm assuming the set doesn't have a constant number of elements. Commented May 29, 2014 at 16:58
  • Yes, that's why I am having difficulties. Commented May 29, 2014 at 16:59
  • @Daniel obviously yes, so what are you getting at? Commented May 29, 2014 at 17:04
  • I just wanted to confirm that I'm understanding the question correctly, as my first reaction was that this data structure sounds like something I've never heard of & it seemed plausible that O(1) meant "O(1) per element deleted" or something like that. Commented May 29, 2014 at 17:07
  • 1
    @Daniel Hopefully the original question clears things up? Commented May 29, 2014 at 17:49

2 Answers 2

Reset to default
6

Note that your goal is to get O(1) amortized time, not O(1) time. This means that you can do as much work as you'd like per operation as long as n operations don't take more than O(n) time.

Here's a simple solution. Store the elements in a stack in ascending order. To insert an element, keep popping the stack until it's empty or until the top element is greater than x, then push x onto the stack. To do a find-min, read the top of the stack.

Find-min clearly runs in time O(1). Let now look at insert. Intuitively, each element is pushed and popped at most once, so we can spread the work of an expensive insert across cheaper inserts. More formally, let the potential be n, the number of elements on the stack. Each time you do an insert, you'll do some number of pops (say, k) and the potential increases by 1 - k (one new element added, k removed). The amortized cost is then k + 1 + 1 - k, which is 2. Therefore, insert is amortized O(1).

Hope this helps!

Improve this answer
Sign up to request clarification or add additional context in comments.

3 Comments

+1 for actually solving the problem as stated, not creatively reading the requirements to avoid doing any real work at all ;-)
@delnan That doesn't make any sense. If the data structure requirements include "list the elements of the set" then the question should say that. My answer solves the problem exactly as stated and is more efficient in that it uses O(1) space and non-amortized O(1) time per operation. This implementation uses O(n) space and insert is O(n) worst case (though O(1) amortized).
+1 for you! I had the same intuitive feeling about the amortization of the Insert over a sequence of operations but I could not really explain it!
2

double is the data structure! In the methods below, ds represents the data structure that the operation is being performed on.

void Insert(ref double ds, double x) { ds = x; } double FindMin(double ds) { return ds; }

The only way to ever observe the state of the data structure is to query its minimum element (FindMin). The only way to modify the state of the data structure is to set its new minimum element (Insert). So the data structure is simply the minimum element of the set.

Improve this answer

7 Comments

Shoudn't insert return the minimum?
@templatetypedef "Insert(x): first delete from X all numbers not larger than x and then insert x into X." This description indicates that x becomes the new minimum element of X.
Are you sure? If the former min is 50 and we insert 137, we wouldn't delete 50 and the min would remain as-is.
@templatetypedef "first delete from X all numbers not larger than (<=) x" If we insert 137 we delete everything less than it, which includes 50.
You're right. That's a very unusual requirement. I wonder if that's a typo in the source?
|

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.