1

I'm looking for a priority queue in Racket that satisfies the following definition, especially the bit in bold (from Wikipedia):

a priority queue is an abstract data type which is like a regular queue or stack data structure, but where additionally each element has a "priority" associated with it. In a priority queue, an element with high priority is served before an element with low priority. If two elements have the same priority, they are served according to their order in the queue.

What I understand (and indeed want) by this, is that they are served according to the order that they were added to the queue.

I've tried Racket's data/heap but this doesn't maintain the correct ordering if the priorities are the same.

Test code:

#lang racket

(require data/heap)

(define h (make-heap
           (λ (p1 p2)
             (<= (car p1) (car p2)))))

(define (add! p) (heap-add! h p))

(add! '(1 a))
(add! '(2 b))
(add! '(3 c))
(add! '(3 d))
(add! '(3 e))
(add! '(3 f))
(add! '(3 g))
(add! '(3 h))
(add! '(3 i))

(for ([p (in-heap h)])
     (display p))

Output:

(1 a)(2 b)(3 h)(3 g)(3 f)(3 e)(3 d)(3 c)(3 i)

I need the following output:

(1 a)(2 b)(3 c)(3 d)(3 e)(3 f)(3 g)(3 h)(3 i)
Eric Clack
  • 1,886
  • 1
  • 15
  • 28
  • This seems to be the same problem in another language: https://stackoverflow.com/questions/6909617/how-to-preserve-the-order-of-elements-of-the-same-priority-in-a-priority-queue-i – Eric Clack Dec 12 '17 at 16:19

1 Answers1

3

Use the standard heap. Keep a counter i which is incremented for each insertion. To insert an element x into the priority queue insert (list i x) into the heap. Your order predicate can now break ties using i.

soegaard
  • 30,661
  • 4
  • 57
  • 106
  • Thanks, that worked. Code here: https://github.com/ericclack/racket-stamps/blob/z-order/private/priority-queue.rkt – Eric Clack Dec 16 '17 at 12:28