Bounded Height Priority Queues 2 points by fallintothis 2685 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 2684 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 2684 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) (< . #)) arc> (bhpq-push 1 'hi q) (hi) arc> (bhpq-pop q) hi arc> (bhpq-push 1 'bye q) Error: "<: expects type 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))))))``````-----