Priority queue example in Chapter 2 of the manual

Ecosystem
1

Apologies if this is a stupid question; if it is, I haven’t figured it out yet.

I’ve pasted the PrioQueue module from Chapter 2 of the manual into an editor, leading to the following interaction in the REPL.

# #use "PrioQueue.ml";;
module PrioQueue :
  sig
    type priority = int
    type 'a queue = Empty | Node of priority * 'a * 'a queue * 'a queue
    val empty : 'a queue
    val insert : 'a queue -> priority -> 'a -> 'a queue
    exception Queue_is_empty
    val remove_top : 'a queue -> 'a queue
    val extract : 'a queue -> priority * 'a * 'a queue
  end
# open PrioQueue;;
# let q = empty;;
val q : 'a PrioQueue.queue = Empty
# let q = insert q 0 "first";;
val q : string PrioQueue.queue = Node (0, "first", Empty, Empty)
# let q = insert q 0 "last";;
val q : string PrioQueue.queue =
  Node (0, "last", Node (0, "first", Empty, Empty), Empty)
# extract q;;
- : PrioQueue.priority * string * string PrioQueue.queue =
(0, "last", Node (0, "first", Empty, Empty))

In my understanding, this acts as a priority stack, not a priority queue. As far as I can tell, "first" and "last" have the same priority, and "first" gets enqueued first, but "last" gets dequeued first.

If my understanding is correct, then the comparisons in the functions insert and remove_top should be with < and not <=, but I assume someone checked this before it went into the manual…so what am I missing? Have I forgotten the definition of a queue?

2

(It’s also a bit confusing that lower priority numbers correspond to higher priorities, but maybe that’s standard.)

3

I’m not sure I’ve ever heard the term “priority stack” before. I think most people just use “priority queue” to refer to a data structure that allows you to query for a highest-priority item. If there’s a tie, they might break the tie via insertion order, or they might leave it undefined. But typically they call this a “priority queue” no matter what, and just say in the documentation if there are additional guarantees about tiebreaks.

I think it’s fairly common; see Java’s standard library for example. This is another thing I’d normally expect to see clarified in docs, rather than assumed as a universal terminological standard of computer science.

1 Like
4

I had a vague suspicion that someone would say something like this. I guess you’re right; Wikipedia says

In some implementations, if two elements have the same priority, they are served according to the order in which they were enqueued, while in other implementations, ordering of elements with the same priority is undefined.

I still find it odd that something called a “queue” would act as a stack rather than a queue in a particular degenerate case, but I think I’ve just been unduly influenced by an assignment in an undergrad class that specifically mentioned that a certain data structure almost, but not quite, implemented a priority queue because it didn’t guarantee that elements with the same priority would be dequeued in insertion order.

Thanks for the clarification.

5

Maybe I’m the author of this example. But it was 25 years ago…

I agree the example would be nicer if 1- highest priority elements are returned first, and 2- it degenerates into a queue rather than into a stack.

Feel free to submit a pull request. The file to change is ocaml/moduleexamples.etex at trunk · ocaml/ocaml · GitHub

1 Like