Arc Forumnew | comments | leaders | submitlogin
Bounded Height Priority Queues
2 points by fallintothis 2523 days ago | 4 comments
And now for something completely different...and hopefully educational!

I like being surprised by data structures that are effective but really simple to implement---so simple that you can reconstruct the operations off the top of your head with a little thought. Today's example is the bounded height priority queue. Quoth Steven Skiena:

  This array-based data structure permits constant-time insertion and find-min
  operations whenever the range of possible key values is limited. Suppose we
  know that all key values will be integers between 1 and n. We can set up an
  array of n linked lists, such that the ith list serves as a bucket containing
  all items with key i. We will maintain a top pointer to the smallest nonempty
  list. To insert an item with key k into the priority queue, add it to the kth
  bucket and set top = min(top, k). To extract the minimum, report the first
  item from bucket top, delete it, and move top down if the bucket has become
  empty. 

  Bounded height priority queues are very useful in maintaining the vertices of
  a graph sorted by degree, which is a fundamental operation in graph
  algorithms.  Still, they are not as widely known as they should be.  They are
  usually the right priority queue for any small, discrete range of keys.
Basically, it's like a chained hash table with a little extra bookkeeping. Arc doesn't have arrays, but we can still use a table for our buckets.

  ; Bounded height priority queue

  (def bhpq (h (o min/max min))
    (unless (in min/max min max)
      (err "Must use either min or max as second arg to bhpq."))
    (obj top     (if (is min/max min) (+ h 1) -1)
         height  h
         buckets (table)
         min/max min/max))

  ; O(1)
  (def bhpq-push (priority elt bhpq)
    (unless (<= 0 priority bhpq!height)
      (err (+ "Priority must be between 0 and " bhpq!height ":") priority))
    (zap [bhpq!min/max _ priority] bhpq!top)
    (push elt (bhpq!buckets priority)))

  ; O(1)
  (def bhpq-peek (bhpq)
    (car (bhpq!buckets bhpq!top)))

  ; O(h)
  (def bhpq-pop (bhpq)
    (do1 (pop (bhpq!buckets bhpq!top))
         (let step (if (is bhpq!min/max min) +1 -1)
           (until (or (bhpq!buckets bhpq!top) (~<= 0 bhpq!top bhpq!height))
             (++ bhpq!top step)))))
Simple usage:

  (def example (q)
    (repeat 10
      (let elt (rand 1000)
        (prn "push " elt)
        (bhpq-push (mod elt 2) elt q)))
    (n-of 10 (bhpq-pop q)))

  arc> (example (bhpq 1 min)) ; even numbers should come first
  push 853
  push 90
  push 765
  push 603
  push 174
  push 284
  push 240
  push 55
  push 224
  push 854
  (854 224 240 284 174 90 55 603 765 853)

  arc> (example (bhpq 1 max)) ; odd numbers should come first
  push 5
  push 848
  push 565
  push 838
  push 283
  push 391
  push 671
  push 271
  push 828
  push 139
  (139 271 671 391 283 565 5 828 838 848)


2 points by akkartik 2523 days ago | link

Interesting, passing in one of exactly two procedures. I tried to come up with a way to use compare, but it doesn't work.

Each bucket seems to act as a stack rather than a queue; elements come off in reverse order that they go in.

-----

2 points by fallintothis 2523 days ago | link

Interesting, passing in one of exactly two procedures. I tried to come up with a way to use compare, but it doesn't work.

I did find it a little ugly, but I thought it would be better than hard coding one over the other. At least the data structure itself is simple to understand, those details notwithstanding. :)

Each bucket seems to act as a stack rather than a queue; elements come off in reverse order that they go in.

Probably because each bucket is a stack, here. :P I favored -push and -pop over -enq and -deq names for that reason. It'd of course be easy to use Arc's queues instead; we'd get the same complexities.

I suppose "priority queue" is a misnomer we got stuck with. At least, Wikipedia thinks FILO v FIFO is secondary to the "priority" part: https://en.wikipedia.org/wiki/Priority_queue.

-----

2 points by akkartik 2522 days ago | link

Ah, I figured it out:

  (def bhpq (h (o < <))
    (obj top     (best ~< (list (+ h 1) -1))
         height  h
         buckets (table)
         < <))

  (def bhpq-push (priority elt bhpq)
    (unless (<= 0 priority bhpq!height)
      (err (+ "Priority must be between 0 and " bhpq!height ":") priority))
    (zap [best bhpq!< (list _ priority)] bhpq!top)
    (push elt bhpq!buckets.priority))

  (def bhpq-peek (bhpq)
    (car (bhpq!buckets bhpq!top)))

  ; still O(h), but probably does a lot more consing than the original
  (def bhpq-pop (bhpq)
    (do1 (pop (bhpq!buckets bhpq!top))
         (unless (bhpq!buckets bhpq!top)
           (= bhpq!top (best bhpq!< (keys bhpq!buckets))))))
I'm not sure it's an improvement, but it was a fun exercise to go through :)

-----

2 points by fallintothis 2522 days ago | link

Spiffy! Definitely reads a lot better.

You're right about the consing, though. It seems like there should be a lazy way of doing keys. But then, best hard-codes calls to both car and cdr upon the sequence. So, it looks like we'd be resigned to doing it by hand, and I'm not sure it's any better:

  (unless (bhpq!buckets bhpq!top)
    (= bhpq!top nil)
    (each (priority elt) bhpq!buckets
      (when (bhpq!< priority bhpq!top)
        (= bhpq!top priority))))
Ah, but this has made me notice an issue with the best keys approach to begin with: once we empty out the queue, !top will be nil, which won't compare correctly on the next bhpq-push.

  arc> (= q (bhpq 10))
  #hash((top . 11) (buckets . #hash()) (height . 10) (< . #<procedure:<>))
  arc> (bhpq-push 1 'hi q)
  (hi)
  arc> (bhpq-pop q)
  hi
  arc> (bhpq-push 1 'bye q)
  Error: "<: expects type <real number> as 2nd argument, given: nil; other arguments were: 1"
Conundrum. Suppose the answer is to factor out the (best ~< (list (+ h 1) -1)) so that we can get a fitting default value for !top:

  ; Top element of the abstract comparison operator bhpq!< (though we assume
  ; the operator compares integers!).
  (def bhpq-top (bhpq (o < bhpq!<) (o h bhpq!height))
    (best ~< (list (+ h 1) -1)))

  (def bhpq (h (o < <))
    (obj top     (bhpq-top nil < h)
         height  h
         buckets (table)
         < <))

  (def bhpq-push (priority elt bhpq)
    (unless (<= 0 priority bhpq!height)
      (err (+ "Priority must be between 0 and " bhpq!height ":") priority))
    (zap [best bhpq!< (list _ priority)] bhpq!top)
    (push elt bhpq!buckets.priority))

  (def bhpq-peek (bhpq)
    (car (bhpq!buckets bhpq!top)))

  ; Not as concise, but less consing/breaking
  (def bhpq-pop (bhpq)
    (do1 (pop (bhpq!buckets bhpq!top))
         (unless (bhpq!buckets bhpq!top)
           (= bhpq!top (bhpq-top bhpq))
           (each (priority elt) bhpq!buckets
             (when (bhpq!< priority bhpq!top)
               (= bhpq!top priority))))))

-----