How to resolve the algorithm Priority queue step by step in the Maxima programming language
How to resolve the algorithm Priority queue step by step in the Maxima programming language
Table of Contents
Problem Statement
A priority queue is somewhat similar to a queue, with an important distinction: each item is added to a priority queue with a priority level, and will be later removed from the queue with the highest priority element first. That is, the items are (conceptually) stored in the queue in priority order instead of in insertion order.
Create a priority queue. The queue must support at least two operations:
Optionally, other operations may be defined, such as peeking (find what current top priority/top element is), merging (combining two priority queues into one), etc.
To test your implementation, insert a number of elements into the queue, each with some random priority. Then dequeue them sequentially; now the elements should be sorted by priority. You can use the following task/priority items as input data:
The implementation should try to be efficient. A typical implementation has O(log n) insertion and extraction time, where n is the number of items in the queue.
You may choose to impose certain limits such as small range of allowed priority levels, limited capacity, etc. If so, discuss the reasons behind it.
Let's start with the solution:
Step by Step solution about How to resolve the algorithm Priority queue step by step in the Maxima programming language
Source code in the maxima programming language
/* Naive implementation using a sorted list of pairs [key, [item[1], ..., item[n]]].
The key may be any number (integer or not). Items are extracted in FIFO order. */
defstruct(pqueue(q = []))$
/* Binary search */
find_key(q, p) := block(
[i: 1, j: length(q), k, c],
if j = 0 then false
elseif (c: q[i][1]) >= p then
(if c = p then i else false)
elseif (c: q[j][1]) <= p then
(if c = p then j else false)
else catch(
while j >= i do (
k: quotient(i + j, 2),
if (c: q[k][1]) = p then throw(k)
elseif c < p then i: k + 1 else j: k - 1
),
false
)
)$
pqueue_push(pq, x, p) := block(
[q: pq@q, k],
k: find_key(q, p),
if integerp(k) then q[k][2]: endcons(x, q[k][2])
else pq@q: sort(cons([p, [x]], q)),
'done
)$
pqueue_pop(pq) := block(
[q: pq@q, v, x],
if emptyp(q) then 'fail else (
p: q[1][1],
v: q[1][2],
x: v[1],
if length(v) > 1 then q[1][2]: rest(v) else pq@q: rest(q),
x
)
)$
pqueue_print(pq) := block([t], while (t: pqueue_pop(pq)) # 'fail do disp(t))$
/* An example */
a: new(pqueue)$
pqueue_push(a, "take milk", 4)$
pqueue_push(a, "take eggs", 4)$
pqueue_push(a, "take wheat flour", 4)$
pqueue_push(a, "take salt", 4)$
pqueue_push(a, "take oil", 4)$
pqueue_push(a, "carry out crepe recipe", 5)$
pqueue_push(a, "savour !", 6)$
pqueue_push(a, "add strawberry jam", 5 + 1/2)$
pqueue_push(a, "call friends", 5 + 2/3)$
pqueue_push(a, "go to the supermarket and buy food", 3)$
pqueue_push(a, "take a shower", 2)$
pqueue_push(a, "get dressed", 2)$
pqueue_push(a, "wake up", 1)$
pqueue_push(a, "serve cider", 5 + 3/4)$
pqueue_push(a, "buy also cider", 3)$
pqueue_print(a);
"wake up"
"take a shower"
"get dressed"
"go to the supermarket and buy food"
"buy also cider"
"take milk"
"take butter"
"take flour"
"take salt"
"take oil"
"carry out recipe"
"add strawberry jam"
"call friends"
"serve cider"
"savour !"
You may also check:How to resolve the algorithm Death Star step by step in the Racket programming language
You may also check:How to resolve the algorithm Random number generator (included) step by step in the Java programming language
You may also check:How to resolve the algorithm Fibonacci sequence step by step in the Phix programming language
You may also check:How to resolve the algorithm Bitmap step by step in the Java programming language
You may also check:How to resolve the algorithm Sparkline in unicode step by step in the S-lang programming language