Data.Queue.SoftHeap

A soft heap is a comparison-based priority queue that provides amortized constant-time performance for every one of its operations by corrupting at most a fixed percentage (by default, 1/128) of keys, possibly increasing them. At this time, that means that not every element put in will come out again -- instead, a duplicate of a greater key might be returned. This is a highly experimental implementation.

• The author believes that every element that goes in can be returned, just possibly not in the correct order (but this will happen for at most an epsilon proportion)
• The author believes that a truly functional implementation with the same time performance isn't possible; part of this implementation uses Data.Sequence. As a result, every operation takes O(log log n) amortized time in this implementation, with a very low constant factor.
• This implementation is based on the one described in H. Kaplan, U. Zwick: A simpler implementation and analysis of Chazelle's soft heaps. In Proceedings of the Nineteenth Annual ACM -SIAM Symposium on Discrete Algorithms, 2009, 477-485.
• An IO-backed implementation supporting true amortized constant-time operations is in progress.

Documentation

data SoftHeap e

Instances

Ord e => Queuelike (SoftHeap e)

empty' :: (Ord e, RealFrac b) => b -> SoftHeap e

singleton' :: (Ord e, RealFrac b) => b -> e -> SoftHeap e

fromList' :: (Ord e, RealFrac b) => b -> [e] -> SoftHeap e