4 ms·

> I was just giving the recommendations in the context of 'Do you know any good books or resources to read up more on random algorithms?'. Not with any regard t

by maxov 6y ago

> I was just giving the recommendations in the context of 'Do you know any good books or resources to read up more on random algorithms?'. Not with any regard to practicality. Fair enough! I still think it's a good recommendation, I was also adding on some thoughts on things that might be easier to digest :-) > Chazelle also came up with the ingenious soft heaps. Yes, soft heaps are very cool! > I have an algorithmic puzzle.. Cool puzzle! Hmm, the solutions depend on exactly what you're asking. The puzzle is substantially easier if the min-pop operation is not required to return anything. In this case, you are solving the much easier problem "return the top k elements of an array in unsorted order". You can insert into an unordered list and increment a counter every time min-pop is called. Then the last step can be done with a basic quickselect. See https://www.cs.cmu.edu/~avrim/451f11/lectures/lect0908.pdf https://www.cs.cmu.edu/~avrim/451f11/lectures/lect0908.pdf page 21, the "QuickSelect" algorithm. You need to do some small modifications to give you the "top k" elements rather than just the "kth" element. This gives expected linear time, and the note describes a deterministic algorithm that makes this worst-case linear time. You can implement deterministic quick select using soft heaps, or instead you could also do a radix sort and then slice out the popped elements. If the min-pop operation is required to return the popped element, then I believe you run into the sorting linear bound that prevents a deterministic O(n) solution. (Surprisingly, this indicates the hardness of the problem is not really in the last step, it's in implementing constant-time insert and pop). I can't think of an immediate solution off the top of my head, but I don't think a soft-heap provides the right guarantees here. I also don't know of a probabilistic data structure that provides both insert and min-pop in expected amortized constant time, and it seems that this could be an area of research. There are some better, but not quite linear results outside the comparison-based model (https://cs.stackexchange.com/questions/6455/an-efficient-data-structure-supporting-insert-delete-and-mostfrequent/6462#6462 https://cs.stackexchange.com/questions/6455/an-efficient-dat...)

eru 6y ago
The min-pop is not supposed to return anything, yes. We are only interested in the final contents of the heap. So no sorting required. You can eg give the results of the whole operation as a bitmap over the inserts, so you need to return a linear number of bits. Min-pops and inserts will in generally be interleaved. The prototypical example has blocks of 2 inserts and 1 pop repeated n times. (All other interleaving patterns can be reduced to this one in linear time.) QuickSelect doesn't work for this. QuickSelect or Median-of-Medians approaches work if you only have a small constant number of interleaved blocks (of any arbitrary internal length). Like eg all the inserts first then all the min-pops is equivalent to finding the k smallest elements.

by maxov 6y ago

eru 6y ago

The min-pop is not supposed to return anything, yes. We are only interested in the final contents of the heap. So no sorting required. You can eg give the results of the whole operation as a bitmap over the inserts, so you need to return a linear number of bits. Min-pops and inserts will in generally be interleaved. The prototypical example has blocks of 2 inserts and 1 pop repeated n times. (All other interleaving patterns can be reduced to this one in linear time.) QuickSelect doesn't work for this. QuickSelect or Median-of-Medians approaches work if you only have a small constant number of interleaved blocks (of any arbitrary internal length). Like eg all the inserts first then all the min-pops is equivalent to finding the k smallest elements.