[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):

 Interesting.

 I'm starting to feel, though, that I can't justify putting pairing heaps
 in containers, because of the possibility that even under normal usage
 that O(n^2) work could be done when O(n log n) was expected.  The worst
 case for delete-min of a pairing heap is O(n), and if that operation is
 performed several times in that worst case, it'd get ugly.  It makes me
 sad, because like your benchmark shows, pairing heaps are so effective in
 the single-threaded case.  For the same reason, I'd prefer a strict data
 structure, because we have to have an implementation that's suitable for
 *everybody,* including the people with serious real-time speed
 requirements.

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