Proposal: priority queues in containers

[Stephan Friedrichs]

On 16/03/10 17:56, Jim Apple wrote:
>> I do wonder how this implementation
>> compares to packages on hackage, e.g.:
> 
> Also:
> 
> http://hackage.haskell.org/package/heap

Let me speak for this one, as I happen to know it. Unfortunately I don't
have much time for a thorough performance comparison (Maybe someone can
come up with general testcases? It should be possible to quickly rewrite
them for each package!), but I did two tests an heap was twice as fast
as the proposition (containers-pqueue):

*Data.PQueue.Min> takeWhile (<= 5) $ (fromList [1..100000]) `union`
(fromList [100001..200000])
[1,2,3,4,5]

and

*Data.PQueue.Min> takeWhile (<= 5) $ (fromAscList [1..100000]) `union`
(fromAscList [100001..200000])
[1,2,3,4,5]

    =====
     vs.
    =====

*Data.Heap> takeWhile (<=5) $ (fromList [1..100000]) `Data.Heap.union`
(fromList [100001..200000] :: MinHeap Int)
[1,2,3,4,5]

and

*Data.Heap> takeWhile (<=5) $ (fromAscList [1..100000])
`Data.Heap.union` (fromAscList [100001..200000] :: MinHeap Int)
[1,2,3,4,5]

In both cases, heap was about twice as fast as containers-pqueue. I
don't know if theses test cases are representative, please comment on
that :)

Regards,
Stephan