[GHC] #3909: Priority queues in containers

[GHC]

#3909: Priority queues in containers
-------------------------------------------+--------------------------------
    Reporter:  LouisWasserman              |        Owner:  LouisWasserman
        Type:  feature request             |       Status:  assigned      
    Priority:  normal                      |    Milestone:                
   Component:  libraries (other)           |      Version:  6.12.1        
    Keywords:  containers, priority queue  |   Difficulty:                
          Os:  Unknown/Multiple            |     Testcase:                
Architecture:  Unknown/Multiple            |      Failure:  None/Unknown  
-------------------------------------------+--------------------------------

Comment(by LouisWasserman):

 Sounds good.  I'm uploading a quickie implementation of skew heaps, which
 Wikipedia says should beat leftist heaps, but which is beaten by my
 binomial heaps.

 I'd be interested to help with the proof that lazy pairing heaps are
 amortized O(log n), and I certainly believe the claim, but I'm still
 inclined to use binomial heaps in containers, and then the two of us
 should co-release a lazy pairing heap implementation that we recommend in
 the containers documentation.

 Look forward to seeing your results.

-- 
Ticket URL: <http://hackage.haskell.org/trac/ghc/ticket/3909#comment:30>
GHC <http://www.haskell.org/ghc/>
The Glasgow Haskell Compiler