Proposal: Tidy up and export PSQ from base

[wren ng thornton]

On 5/5/11 2:31 AM, Brandon Moore wrote:
>> 2011-5-4 8:53:50 PM, wren ng thornton
>> On 5/1/11 7:58 PM, Edward Z. Yang wrote:
>>> OK, to summarize the current  discussion:
>>> - It would be nice to have a general-purpose priority queue  in containers.
>>>     I'm not interested in this goal per se, but  I do view it as the
>>>     cleanest way to get what I  want.
>>
>> With regards to this point, is there any reason why the following  does
>> not suffice (albeit not in base)?
>>
>>        http://code.google.com/p/priority-queues/
>>
>> They're not priority *search*  queues, but I'm not sure how much to read
>> into your leaving out that  word...
>
> That word is pretty significant. In a priority queue every element also
> has a key, which can be used to efficiently remove it or adjust the
> priority.
>
> That package wouldn't support cancelling a timeout, for example.

Yes, I know it's important. Which is why I brought up the question about 
whether the omission in ezyang's summary was intentional or an 
unfortunate oversight.

If the goal is only to provide general-purpose priority queues, then I 
argue that we should be promoting that package. Algorithmically, they're 
asymptotically optimal; practically, they come with proofs of 
correctness; and, in practice, I've been quite happy with them. The only 
reason to promote something else is as a special case, if someone has a 
PQ which has better constant factors (for folks whose data is small 
enough not to care about asymptotics).

However, if the goal in question is to provide general-purpose priority 
search queues, then clearly that project is irrelevant.

-- 
Live well,
~wren