[Haskell-cafe] ONeillPrimes.hs - priority queue broken?

[Bertram Felgenhauer]

Eugene Kirpichov wrote:
> module PQ where
> 
> import Test.QuickCheck
> 
> data PriorityQ k v = Lf
>                    | Br {-# UNPACK #-} !k v !(PriorityQ k v) !(PriorityQ k v)
>                deriving (Eq, Ord, Read, Show)

For the record, we can exploit the invariant that the sizes of the left
and right subtrees have difference 0 or 1 to implement 'size' in better
than O(n) time, where n is the size of the heap:

-- Return number of elements in the priority queue.
-- /O(log(n)^2)/
size :: PriorityQ k v -> Int
size Lf = 0
size (Br _ _ t1 t2) = 2*n + rest n t1 t2 where
    n = size t2
    -- rest n p q, where n = size q, and size p - size q = 0 or 1
    -- returns 1 + size p - size q.
    rest :: Int -> PriorityQ k v -> PriorityQ k v -> Int
    rest 0 Lf _ = 1
    rest 0 _  _ = 2
    rest n (Br _ _ p1 p2) (Br _ _ q1 q2) = case r of
        0 -> rest d p1 q1 -- subtree sizes: (d or d+1), d; d, d
        1 -> rest d p2 q2 -- subtree sizes: d+1, (d or d+1); d+1, d
      where (d, r) = (n-1) `quotRem` 2

Of course we can reduce the cost to O(1) by annotating the heap with its
size, but that is less interesting, and incurs a little overhead in the
other heap operations.

Bertram