How can I implement an optimal, purely functional, double-ended priority queue?

user_1477667 0
Viewed 251

Okasaki shows how to write purely functional priority queues with O(1) insert and O(log n) minView (some versions also offer O(log n) or even O(1) merge. Can any of these ideas be extended to double-ended priority queues? Khoong and Leong (in a paper I don't have access to) offer an ephemeral implementation based on binomial heaps, but from what I can see of their paper, that approach doesn't seem easy to make persistent, as it uses parent and sibling pointers.

priority-queue data-structures persistence functional-programming haskell
1 Answers

As leftaroundabout points out, this can be done with a 2–3 finger tree. In particular, one annotated with the semigroup

data MinMax k = MinMax
  { smallest :: !k
  , largest :: !k }

instance Ord k => Semigroup (MinMax k) where
  MinMax min1 max1 <> MinMax min2 max2 = MinMax (min min1 min2) (max max1 max2)

Such an annotated finger tree can be made a double-ended priority queue in basically the same way that the fingertree package defines priority queues (but adjusted slightly to avoid needing a Monoid). minView and maxView can be improved using the same implementation technique as Data.Sequence.deleteAt.

Why use a Semigroup and not add a neutral element to make it a Monoid? This way, we can unpack MinMax annotations into tree nodes and avoid an extra indirection at every step, along with extra allocation.

Performance bounds

  • insert: Amortized O(1) (note: this bound will hold up even in the face of persistence, thanks to careful use of laziness). Worst-case O(log n). Note that the fingertree package only claims O(log n) for insertion; this is a documentation bug which I have reported and which will be corrected in the next version.
  • minView/maxView: Worst-case O(1) to see the minimum/maximum; worst-case O(log n) to remove it.
  • meld: Worst-case O(log (min (m, n)), where m and n are the sizes of the queues.

Hinze-Paterson style 2–3 finger trees are actually a bit more than necessary. A one-fingered version will do the trick, with fewer digit sizes.

{-# options_ghc -funbox-strict-fields #-}

data Node k a
  = Node2 !(MinMax k) !a !a
  | Node3 !(MinMax k) !a !a !a

data Tree k a
  = Empty
    -- the child of a Zero node may
    -- not be empty
  | Zero !(MinMax k) (Tree k (Node k a))
  | One !(MinMax k) !a (Tree k (Node k a))

I've been working on fleshing this out for the last few days. Fortunately, it's mostly quite straightforward. Unfortunately, it requires an awful lot of code. The fundamental challenge is that deletion in 2–3 trees is fairly involved. The version for finger trees adds another layer of complexity. And then the whole thing has to be written twice to deal with both minView and maxView.

user_14776670
Related