anchor.diff:            (control (sort items #'< :key #'second)))
         (is-false (mismatch queue control :key #'second)))))
   
  -(test update
  +(test random-delete
     (let ((q (make-queue (lambda (a b) (< (second a) (second b)))))
           (items (loop for i from 0 below *test-queue-size* collecting (list i (random 999)))))
       (dolist (item items)
         (queue-insert q item))
  -    (loop repeat 5 do
  +    (loop repeat 15 do
  +      (let* ((random-index (random (length items)))
  +             (random-item (nth random-index items)))
  +        (is (eq q (queue-delete q random-item)))
  +        (setf items (delete random-item items))))
  +    ;; Note that we only compare the second value because the
  +    ;; priority queue is not a stable sort.
  +    (let ((queue (loop while (not (queue-empty-p q)) collecting (queue-pop q)))
  +          (control (sort items #'< :key #'second)))
  +      (is-false (mismatch queue control :key #'second)))))
  +
  +(test update
  +  (let ((q (make-queue (lambda (a b) (< (second a) (second b))))))
  +    (signals item-not-found-error (queue-update q nil))
  +    (let ((item (list 0 200)))
  +      (queue-insert q item)
  +      (queue-insert q (list 1 100))
  +      (queue-insert q (list 2 300))
  +      ;; move up
  +      (setf (second item) 0)
  +      (is (eq q (queue-update q item)))
  +      (is (eq (queue-peek q) item))
  +      ;; move down
  +      (setf (second item) 400)
  +      (is (eq q (queue-update q item)))
  +      (queue-pop q)
  +      (queue-pop q)
  +      (is (eq (queue-peek q) item)))))
  +
  +(test random-update
  +  (let ((q (make-queue (lambda (a b) (< (second a) (second b)))))
  +        (items (loop for i from 0 below *test-queue-size* collecting (list i (random 999)))))
  +    (dolist (item items)
  +      (queue-insert q item))
  +    (loop repeat 15 do
        (let ((random-item (nth (random (length items)) items)))
          (setf (second random-item) (random 999))
          (is (eq q (queue-update q random-item)))))
  
positive.code:       (is-false (mismatch queue control :key #'second)))))
  
  (test replace
    (let ((q (make-queue (lambda (a b) (< (second a) (second b)))))
          (items (loop for i from 0 below *test-queue-size* collecting (list i (random 999)))))
      (dolist (item items)
        (queue-insert q item))
      (loop for i from 0 below 5 do
        (let ((random-item (nth (random (length items)) items))
              (new-item (list (+ *test-queue-size* i) (random 999))))
          (is (eq q (queue-replace q random-item new-item)))
  
negative.code:     (is (queue-empty-p q))
      (signals empty-queue-error (queue-pop q))
      (signals empty-queue-error (queue-peek q))
      (is (eq q (queue-insert q 2)))
      (is (eq q (queue-insert q 3)))
      (is (eq q (queue-insert q 1)))
      (is (eq q (queue-insert q 4)))
      (is (eq q (queue-insert q 0)))
      (is-false (queue-empty-p q))
      (is (= 0 (queue-peek q)))
      (is (= 0 (queue-pop q)))
      (is (= 1 (queue-pop q)))
      (is (= 2 (queue-pop q)))
      (is (= 3 (queue-pop q)))
      (is (= 4 (queue-pop q)))
      (is (queue-empty-p q))
      (signals empty-queue-error (queue-pop q))
      (signals empty-queue-error (queue-peek q))))
  
  (test delete
    (let ((q (make-queue #'<)))
      (signals item-not-found-error (queue-delete q nil))
      (queue-insert q 1)
      (is (eq q (queue-delete q 1)))
      (is (queue-empty-p q))
      (queue-insert q 1)
      (queue-insert q 2)
      ;; delete first
      (queue-delete q 1)
      (is (= (queue-peek q) 2))
      ;; delete last
      (queue-insert q 1)
      (queue-delete q 2)
      (is (= (queue-peek q) 1))))
  
  (test delete2
    ;; This test case exposed a bug in heap-delete where we were
  