►Priority Queues
Priority Queues
1 Predicates
priority-queue?
priority-queue-empty?
2 Constructors
make-priority-queue
list->priority-queue
vector->priority-queue
priority-queue-copy
3 Mutating the queue
priority-queue-insert!
priority-queue-remove-max!
priority-queue-remove!
in-priority-queue!
4 Other operations
priority-queue-peek-max
priority-queue-length
priority-queue-ordering
priority-queue-map
priority-queue->list
priority-queue->vector
priority-queue->vector!
priority-queue->sorted-list
priority-queue->sorted-vector
priority-queue->sorted-vector!
8.12
  top  contents  ← prev  up  next → 

Priority Queues🔗ℹ

Shawn Wagner <shawnw.mobile@gmail.com>

 (require data/priority-queue) package: priority-queue

Imperative max priority queues. Currently implemented with a binary heap, but that is an internal detail that is subject to change in the future.

Two priority queues are equal? if they have equal? comparison functions, contain the same number of elements and when sorted by priority each corresponding pair of elements are equal?. This can be an expensive operation.

1 Predicates🔗ℹ

procedure

(priority-queue? obj) → boolean?

  obj : any/c
Tests if the given value is a priority queue or not.

procedure

(priority-queue-empty? pq) → boolean?

  pq : priority-queue?
Return true if the queue has no elements currently in it.

2 Constructors🔗ℹ

procedure

(make-priority-queue < elem ...) → priority-queue?

  < : (-> any/c any/c any/c)
  elem : any/c
Create a new priority queue object using the given ordering function to determine if one object has lower priority than another, populated with the initial elements given, if any.

procedure

(list->priority-queue < elems) → priority-queue?

  < : (-> any/c any/c any/c)
  elems : list?
Create a new priority queue using the given ordering function, populated by the elements of elems.

procedure

(vector->priority-queue < elems) → priority-queue?

  < : (-> any/c any/c any/c)
  elems : vector?
Create a new priority queue using the given ordering function, populated by the elements of elems.

procedure

(priority-queue-copy pq) → priority-queue?

  pq : priority-queue?
Return a copy of the given priority queue.

3 Mutating the queue🔗ℹ

procedure

(priority-queue-insert! pq elem) → void?

  pq : priority-queue?
  elem : any/c
Insert a new element into the queue.

procedure

(priority-queue-remove-max! pq) → any/c

  pq : (and/c priority-queue? (not/c priority-queue-empty?))
Remove and return the element with the highest priority. It is an error to call on an empty priority queue.

procedure

(priority-queue-remove! pq elem [=?]) → boolean?

  pq : priority-queue?
  elem : any/c
  =? : (-> any/c any/c any/c) = equal?
Remove one element of the priority queue that is equal to elem according to =?. Returns true if such an element was found and removed, and false if not.

If the queue has multiple elements that can compare equal to the given one, it is unspecified which one is removed.

procedure

(in-priority-queue! pq) → sequence?

  pq : priority-queue?
Returns a sequence that destructively returns the elements of the queue in order from highest priority to lowest. After the sequence is consumed, the priority queue will be empty.

A priority queue can be used directly as a sequence? with the same effect.

4 Other operations🔗ℹ

procedure

(priority-queue-peek-max pq) → any/c

  pq : (and/c priority-queue? (not/c priority-queue-empty?))
Return the element with the highest priority without removing it from the queue. It is an error to call on an empty priority queue.

procedure

(priority-queue-length pq) → exact-nonnegative-integer?

  pq : priority-queue?
Return the number of elements in the queue.

procedure

(priority-queue-ordering pq) → (-> any/c any/c any/c)

  pq : priority-queue?
Return the less-than ordering function used by the queue.

procedure

(priority-queue-map f pq [<]) → priority-queue?

  f : (-> any/c any/c)
  pq : priority-queue?
  < : (-> any/c any/c any/c) = (priority-queue-ordering pq)
Returns a new priority queue that’s created from the results of calling f on each element of pq in an unspecified order. The optional third argument controls the ordering of the new queue; if omitted, the same comparision function used by pq is used.

procedure

(priority-queue->list pq) → list?

  pq : priority-queue?
Return a list of the elements of the queue in an unspecified order.

procedure

(priority-queue->vector pq) → vector?

  pq : priority-queue?
Return a newly allocated vector of the elements of the queue in an unspecified order.

procedure

(priority-queue->vector! pq vec) → vector?

  pq : priority-queue?
  vec : (and/c vector? (not/c immutable?))
Fills vec with the elements of the queue in an unspecified order and returns it. vec must have a length at least equal to the number of elements currently in the queue.

procedure

(priority-queue->sorted-list pq) → list?

  pq : priority-queue?
Return a list of the elements of the queue in order from lowest to highest priority.

procedure

(priority-queue->sorted-vector pq) → vector?

  pq : priority-queue?
Return a newly allocated vector of the elements of the queue in order from lowest to highest priority.

procedure

(priority-queue->sorted-vector! pq vec) → vector?

  pq : priority-queue?
  vec : (and/c vector? (not/c immutable?))
Fills vec with the elements of the queue in order from lowest to highest priority and returns it. vec must have a length at least equal to the number of elements currently in the queue.

  top  contents  ← prev  up  next →