| 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)
| 
