2

Here's an interesting problem: Let's say we have a set A for which the following are permitted:

  • Insert x
  • Find-min x
  • Delete the n-th inserted element in A

Create a data structure to permit these in logarithmic time.

The most common solution is with a heap. AFAIK, heaps with decrease-key (based on a value - generally the index when an element was added) keep a table with the Pos[1...N] meaning the i-th added value is now on index Pos[i], so it can find the key to decrease in O(1). Can someone confirm this?

Another question is how we solve the problem with STL containers? i.e. with sets, maps or priority queues. A partial solution i found is to have a priority queue with indexes but ordered by the value to these indexes. I.e. A[1..N] are our added elements in order of insertion. pri-queue with 1..N based on comparison of (A[i],A[j]). Now we keep a table with the deleted indexes and verify if the min-value index was deleted. Unfortunately, Find-min becomes slightly proportional with no. of deleted values. Any alternative ideas?

Now I thought how to formulate a more general problem. Create a data structure similar to multimap with <key, value> elements. Keys are not unique. Values are. Insert, find one (based on key), find (based on value), delete one (based on key) and delete (based on value) must be permitted O(logN).

Perhaps a bit oddly, this is possible with a manually implemented Binary Search Tree with a modification: for every node operation a hash-table or a map based on value is updated with the new pointer to the node.

Similar to having a strictly ordered std::set (if equal key order by value) with a hash-table on value giving the iterator to the element containing that value.

Possible with std::set and a (std::map/hash table) as described by Chong Luo.

trincot
  • 317,000
  • 35
  • 244
  • 286
algotroll
  • 53
  • 4
  • What do you mean by `Delete the n-th inserted element in A`. Is it the element that is n-th in the sorted order of elements or is it simply the element that was inserted when there were n-1 elements? – Ivaylo Strandjev Mar 27 '12 at 06:57
  • the element that was inserted when there were n-1 elements. – algotroll Mar 27 '12 at 06:59
  • The current set of `std::` containers/algorithms doesn't include the "indexed" heap data structure you describe. Such a data structure can be used as an efficient priority queue with dynamic decrease key, delete etc. It's possible to use an "indexed" `std::set` to achieve a similar outcome, although not quite as efficiently - both options are discussed here: http://stackoverflow.com/questions/9209323/easiest-way-of-using-min-priority-queue-with-key-update-in-c/9210074#9210074 – Darren Engwirda Mar 27 '12 at 07:11
  • Yes, that's the answer i was looking for. Thank you! – algotroll Mar 27 '12 at 07:20

1 Answers1

3

You can use a combination of two containers to solve your problem - A vector in which you add each consecutive element and a set:

  • You use the set to execute find_min while
  • When you insert an element you execute push_back in the vector and insert in the set
  • When you delete the n-th element, you see it's value in the vector and erase it from the set. Here I assume the number of elements does not change after executing delete n-th element.

I think you can not solve the problem with only one container from STL. However there are some data structures that can solve your problem:

Skip list - can find the minimum in constant time and will perform the other two operations with amortized complexity O(log(n)). It is relatively easy to implement.

Tiered vector is easy to implement and will perform find_min in constant time and the other two operations in O(sqrt(n))

And of course the approach you propose - write your own heap that keeps track of where is the n-th element in it.

Ivaylo Strandjev
  • 69,226
  • 18
  • 123
  • 176