Priority queue: Difference between revisions

Content added Content deleted
(Add CLU)
Line 5,445: Line 5,445:
=={{header|Quackery}}==
=={{header|Quackery}}==


For more examples uf usage, see [[Sorting algorithms/Heapsort#Quackery]] and [[Huffman coding#Quackery]]
The task [[Sorting algorithms/Heapsort#Quackery]] implements a priority queue. Here we reuse the words <code>comparison</code>, <code>toheap</code>, and <code>fromheap</code> from that task and adapt them to this task. <code>p</code> in the stack comments denotes a priority queue.


<lang Quackery>( ***** priotity queue ***** )
(I presume 1 to be the highest priority, and 5 the lowest.)


⚫
[ stack ] is heap.pq ( [ --> [ )
⚫
<lang Quackery> [ ' [ 0 peek swap 0 peek > ]
⚫
comparison put [] ] is new-pq ( --> p )


[ nested join toheap ] is insert ( p n $ --> p )
[ stack ] is comp.pq ( [ --> [ )


[ unpack
⚫
[ fromheap 1 peek ] is remove ( p --> p $ )
comp.pq put heap.pq put ] is pq->stacks ( [ --> )


[ heap.pq take comp.pq take
⚫
[ drop comparison release ] is end-pq ( p --> )
2 pack ] is stacks->pq ( --> [ )

⚫
[ heap.pq share swap peek ] is heapeek ( n --> x )

[ heap.pq take
swap poke heap.pq put ] is heapoke ( n x --> )

[ 1+ 2 / 1 - ] is parent ( n --> n )

[ 0 > ] is has-parent ( n --> b )

[ 2 * 1+ ] is child ( n --> n )

[ child heap.pq share size < ] is has-child ( n --> b )

[ 1+ ] is sibling ( n --> n )

[ sibling
⚫
heap.pq share size < ] is has-sibling ( n --> b )

[ comp.pq share do ] is compare ( x x --> b )

[ 0 peek size ] is pqsize ( p --> b )

[ swap pq->stacks
heap.pq take tuck size
rot 0 join heap.pq put
[ dup has-parent while
dup parent
rot over heapeek
2dup compare iff
[ 2swap unrot heapoke ]
again
rot 2drop swap ]
heapoke
stacks->pq ] is topq ( p x --> p )

[ dup heapeek swap
[ dup has-child while
dup child
dup has-sibling if
[ dup sibling heapeek
over heapeek
compare if sibling ]
dip over dup heapeek
rot dip dup compare iff
[ rot heapoke ]
again
2drop ]
heapoke ] is heapify.pq ( n --> )

[ dup pqsize 0 = if
[ $ "Unexpectedly empty priority queue."
fail ]
pq->stacks heap.pq share
behead
over [] = iff
[ swap heap.pq replace ]
else
[ swap -1 split
swap join heap.pq put
0 heapify.pq ]
stacks->pq swap ] is frompq ( p --> p x )

[ ]'[ 2 pack pq->stacks
heap.pq share
size 2 / times
[ i heapify.pq ]
stacks->pq ] is pqwith ( [ --> p )

( ***** task ***** )

[ nested join topq ] is insert ( p n $ --> p )

⚫
[] pqwith [ 0 peek swap 0 peek > ]


new-pq
3 $ "Clear drains" insert
3 $ "Clear drains" insert
4 $ "Feed cat" insert
4 $ "Feed cat" insert
Line 5,465: Line 5,538:
1 $ "Solve RC tasks" insert
1 $ "Solve RC tasks" insert
2 $ "Tax return" insert
2 $ "Tax return" insert

5 times [ remove echo$ cr ]
5 times [ frompq unpack
swap echo say ": "
echo$ cr ]
end-pq</lang>
drop</lang>


{{out}}
{{out}}


<pre>Solve RC tasks
<pre>1: Solve RC tasks
Tax return
2: Tax return
Clear drains
3: Clear drains
Feed cat
4: Feed cat
Make tea
5: Make tea
</pre>
</pre>


Retrieved from "https://rosettacode.org/wiki/Priority_queue"