In a previous post, I talked about FIFO queues and gave an implementation. Now I want to talk about another type of queue: the priority queue. In these queues every element has a priority and elements are removed from the queue in order of their priority. Thus the element with the lowest (or highest) priority is removed first regardless of the order in which it was inserted. A naïve way to implement a priority queue is simply to sort it by priority after the elements are inserted. The problem with that implementation is that sorting can be a heavyweight operation. That would be OK if you only had to do it once, but usually items are being popped off and pushed on the queue repeatedly so that it would have to be resorted every time a new element is added.
The traditional way of implementing priority queues is with a binary heap. This has the advantage that removal and insertion are O(log n). Here’s an implementation of a binary heap from my standard library.
1: ;; Make a heap. Size is the total number of entries that the heap will 2: ;; hold, less? is a function to compare the values of two entries, and 3: ;; move-hook is a function that will be called everytime an object is 4: ;; moved in the heap. It is called with the arguments object and slot-number. 5: ;; Arguments to the resulting heap are: 6: ;; 'push obj -- Push obj onto the heap and move it to its correct position 7: ;; 'pop -- pop off the top object and fix the heap 8: ;; 'recalc slot -- the object in slot slot has changed its value. Move it to 9: ;; its correct position 10: ;; 'map f -- Apply f to (slot . object) for every entry in the heap 11: ;; 'show -- dump the current size of the heap and the heap array 12: 13: (define make-heap 14: (lambda (size less? . move-hook) 15: (let ((h (make-vector (1+ size))) (used 0) 16: (hook (if (null? move-hook) (lambda x #t) (car move-hook)))) 17: (letrec ((up-heap (lambda (c t) 18: (let ((p (quotient c 2))) 19: (if (or (= c 1) 20: (less? (vector-ref h p) t)) 21: (begin 22: (vector-set! h c t) 23: (hook t c)) 24: (begin 25: (vector-set! h c (vector-ref h p)) 26: (hook (vector-ref h p) c) 27: (up-heap p t)))))) 28: (down-heap (lambda (p t) 29: (let ((lc (* p 2))) 30: (if (> lc used) 31: (begin 32: (vector-set! h p t) 33: (hook t p)) 34: (let ((rc (1+ lc))) 35: (if (and (<= rc used) 36: (less? (vector-ref h rc) 37: (vector-ref h lc))) 38: (set! lc rc)) 39: (if (less? t (vector-ref h lc)) 40: (begin 41: (vector-set! h p t) 42: (hook t p)) 43: (begin 44: (vector-set! h p (vector-ref h lc)) 45: (hook (vector-ref h lc) p) 46: (down-heap lc t))))))))) 47: (lambda (cmd . data) 48: (case cmd 49: ((push) (set! used (1+ used)) 50: (if (> used size) 51: (error #f "HEAP: heap full") 52: (up-heap used (car data)))) 53: ((pop) (let ((result (vector-ref h 1))) 54: (set! used (1- used)) 55: (if (negative? used) 56: #f 57: (begin 58: (down-heap 1 (vector-ref h (1+ used))) 59: result)))) 60: ((recalc) (let ((i (car data))) 61: (cond 62: ((= i 1) (down-heap 1 (vector-ref h 1))) 63: ((= i used) (up-heap used (vector-ref h used))) 64: ((less? (vector-ref h i) (vector-ref h (quotient i 2))) 65: (up-heap i (vector-ref h i))) 66: (else (down-heap i (vector-ref h i)))))) 67: ((map) (let ((f (car data))) 68: (let mapper ((ix 1) (result '())) 69: (if (> ix used) 70: (reverse result) 71: (mapper (1+ ix) 72: (cons (f (cons ix (vector-ref h ix))) 73: result)))))) 74: ((show) (list used h)) 75: (else (error "HEAP: illegal command:" cmd))))))))
Sometimes events external to the queue will cause the priority of one of its entries to change—this happens with the Dijkstra’s shortest path algorithm, for example. To handle these cases, you can specify a function to be called whenever an object moves in the heap. That way you can keep track of its position in case you need to adjust its priority. The recalc method will move an entry whose priority has been changed to its new correct position in the heap.
Despite its name, less? can be written to choose the element with the larger priority instead of the smaller. In that case, entries with the higher priority are removed first.
All of the real work is done in up-heap (lines 17–27) and down-heap (lines 28–46). Items are inserted into the queue with the push command (line 49) by putting them at the end of the queue and calling up-heap to move it into its final position. The next item to be removed is popped off the queue with the pop command (line 53) by returning the entry in slot 1 of the queue (slot 0 is not used) and then putting the entry in the last slot into slot 1 and calling down-heap to move it to its correct position.
The push and pop commands are the standard heap operations familiar from any basic algorithms book or course. This implementation also has the afore mentioned recalc command and a map command. For debugging, the show command will display the size of the queue and the vector that holds the queue entries.
In my next post, I will give an example that uses a priority queue.