ekmett/heaps

Asymptotically optimal Brodal/Okasaki heaps

heaps

This package provides Brodal/Okasaki heaps. These are asymptotically optimal purely functional heaps.

Contact Information

Contributions and bug reports are welcome!

Please feel free to contact me through github or on the #haskell IRC channel on irc.freenode.net.

-Edward Kmett

heaps's Issues

mapMonotonic documentation error?

https://github.com/ekmett/heaps/blob/master/src/Data/Heap.hs#L443

example uses map, but function is mapMonotonic

Use a separate key instead?

Would it make more sense to provide a separate key rather than use the ordering on elements?

Release to Hackage

This package hasn't been released to Hackage in over a year. The current GitHub version has some helpful updates that we could use downstream.

Split module

I haven't read through the full details of this implementation, but since these heaps are bootstrapped off skew binomial heaps, it would seem to make sense to split the skew binomial heaps into a separate module. This would allow them to be used in applications that don't need O(1) meld, where they are likely to be faster than the bootstrapped version. Some INLINABLE pragmas may be necessary. I don't know if the Foldable cruft would interfere with a split.

Can't be used to bootstrap GHC

In the most recent version of Shake, I added heaps as a dependency. Unfortunately, while heaps has no problematic actual dependencies, the Setup.hs file depends on Cabal and cabal-doctest. The latest cabal-doctest is no longer compatible with Cabal HEAD as used to build GHC. There are a few ways around this issue:

1. Stop using cabal-doctest as a setup dependency.
2. Have me inline the parts of Heap I need into Shake itself. I'm going to do that as a temporary step anyway.
3. Upgrade cabal-doctest to work with HEAD Cabal, but that's will need to be done going forward too.

CC @snowleopard

Functional Soft Heaps

Chazelle-style Soft Heaps would be a great addition to this library. They are asymptotically optimal for a different class of problems than the Brodal/Okasaki heaps, and while a functional implementation cannot delete non-minimum nodes with the same O(1/epsilon) guarantee, you don't need that functionality for many of the algorithms that this structure is suited to. (soft minimal spanning trees, near sorting, exact selection with soft heaps, etc.)

Lazy binomial versions

The lazy binomial version should be rather simpler and more compact. I suspect it will be more efficient in practice too. Does it belong in this package or elsewhere? I don't want the nasty Foldable trick.

module Plain where

-- Binomial queues strict in both key and value
-- These support:
-- insertion in amortized O(1) time, worst case O(log n) time
-- deletion in O(log n) (amortized and worst case) time
-- merge in amortized O(log (min (m, n))) time and worst case O(log (max (m, n))) time
newtype Plain k a = Plain (Forest Zero k a)
data Forest rk k a
  = Nil
  | Skip (Forest (Succ rk) k a)
  | Cons {-# UNPACK #-} !(Tree rk k a) (Forest (Succ rk) k a)
  -- Note: Cons is allowed to be strict in its second field, but
  -- I don't think that's actually good in practice

-- A binomial tree. The value associated with the key is
-- stored as its rightmost child.
data Tree rk k a = Tree !k !(rk k a)

newtype Zero k a = Zero a
data Succ rk k a = Succ {-# UNPACK #-} !(Tree rk k a) !(rk k a)

tip :: k -> a -> Tree Zero k a
tip k a = Tree k (Zero a)

mergeTrees :: Ord k => Tree rk k a -> Tree rk k a -> Tree (Succ rk) k a
mergeTrees t1@(Tree k1 ts1) t2@(Tree k2 ts2)
  | k1 <= k2
  = Tree k1 (Succ t2 ts1)
  | otherwise
  = Tree k2 (Succ t1 ts2)

incr :: Ord k => Tree rk k a -> Forest rk k a -> Forest rk k a
incr t Nil = Cons t Nil
incr t (Skip ts) = Cons t ts
-- force ts when cascading to
-- maintain worst-case bounds
incr t1 (Cons t2 !ts) = Skip $ incr t ts
  where
    !t = mergeTrees t1 t2

-- ----

module Bootstrapped where
import qualified Plain as P
import Plain (Plain)

newtype Loop a = Loop (Plain a (Loop a))
data Queue a
  = Empty
  | Queue !Int !a !(Plain a (Loop a))

merge (Queue sz1 a1 qs1) (Queue sz2 a2 qs2)
  | a1 <= a2 = Queue (sz1 + sz2) a1 $ P.insert a2 (Loop qs2) qs1
...

`heaps` seems slower than `pqueue` and `psqueues` at inserting/popping

Hi, I just thought I'd share this small benchmark I wrote while investigating the speed of various priority queue libraries. Perhaps there's something wrong with the methodology, but if not, heaps appears to be ~1.4-1.5x slower than pqueue/psqueue at inserting 100 random elements (each with one of 10 distinct priorities), then popping them all.

Link to another issue that contains the benchmark: HeinrichApfelmus/reactive-banana#214