Priority queue: Difference between revisions
Content added Content deleted
Not a robot (talk | contribs) (Add CLU) |
(→{{header|Quackery}}: revamped) |
||
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 comp.pq ( [ --> [ ) |
||
[ unpack |
|||
⚫ | |||
comp.pq put heap.pq put ] is pq->stacks ( [ --> ) |
|||
[ heap.pq take comp.pq take |
|||
⚫ | |||
2 pack ] is stacks->pq ( --> [ ) |
|||
⚫ | |||
[ 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 |
|||
⚫ | |||
[ 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 ) |
|||
⚫ | |||
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 [ |
5 times [ frompq unpack |
||
swap echo say ": " |
|||
echo$ cr ] |
|||
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> |
||