Rosetta Code

Priority queue: Difference between revisions

Page Discussion

Priority queue (view source)

Revision as of 08:07, 30 January 2024

22,610 bytes added ,  3 months ago
m
Remove DYNAM compiler option from PROCESS compiler directives leading each program.
imported>Pjfarley3
m (Remove DYNAM compiler option from PROCESS compiler directives leading each program.)
(26 intermediate revisions by 12 users not shown)
Line 567:
with Ada.Containers.Unbounded_Priority_Queues;
with Ada.Strings.Unbounded;
with Ada.Text_IO;
 
procedure Priority_Queues is
Line 608 ⟶ 609:
 
{{out}}
<pre></pre>
5 => Make tea
4 => Feed cat
3 => Clear drains
2 => Tax return
1 => Solve RC tasks
</pre>
 
=={{header|ARM Assembly}}==
Line 1,048 ⟶ 1,055:
Priority : 5 : Make tea
</pre>
 
=={{header|Arturo}}==
 
<syntaxhighlight lang="arturo">define :item [priority, value][
print: [
~"(|this\priority|, |this\value|)"
]
]
define :queue [items][
init: [
this\items: arrange this\items 'it -> it\priority
]
]
 
empty?: function [this :queue][
zero? this\items
]
 
push: function [this :queue, item][
this\items: this\items ++ item
this\items: arrange this\items 'it -> it\priority
]
 
pop: function [this :queue][
ensure -> not? empty? this
result: this\items\0
this\items: remove.index this\items 0
return result
]
 
Q: to :queue @[to [:item] [
[3 "Clear drains"]
[4 "Feed cat"]
[5 "Make tea"]
[1 "Solve RC tasks"]
]]
 
push Q to :item [2 "Tax return"]
 
print ["queue is empty?" empty? Q]
print ""
 
while [not? empty? Q]->
print ["task:" pop Q]
 
print ""
print ["queue is empty?" empty? Q]</syntaxhighlight>
 
{{out}}
 
<pre>queue is empty? false
 
task: (1, Solve RC tasks)
task: (2, Tax return)
task: (3, Clear drains)
task: (4, Feed cat)
task: (5, Make tea)
 
queue is empty? true</pre>
 
=={{header|ATS}}==
Line 1,483 ⟶ 1,550:
[1,"Solve RC tasks"]]
Type: List(OrderedKeyEntry(Integer,String))</pre>
 
=={{header|BASIC}}==
==={{header|FreeBASIC}}===
{{trans|VBA}}
<syntaxhighlight lang="freebasic">Type Tupla
Prioridad As Integer
Tarea As String
End Type
Dim Shared As Tupla a()
Dim Shared As Integer n 'número de eltos. en la matriz, el último elto. es n-1
 
Function Izda(i As Integer) As Integer
Izda = 2 * i + 1
End Function
 
Function Dcha(i As Integer) As Integer
Dcha = 2 * i + 2
End Function
 
Function Parent(i As Integer) As Integer
Parent = (i - 1) \ 2
End Function
 
Sub Intercambio(i As Integer, j As Integer)
Dim t As Tupla
t = a(i)
a(i) = a(j)
a(j) = t
End Sub
 
Sub bubbleUp(i As Integer)
Dim As Integer p = Parent(i)
Do While i > 0 And a(i).Prioridad < a(p).Prioridad
Intercambio i, p
i = p
p = Parent(i)
Loop
End Sub
 
Sub Annadir(fPrioridad As Integer, fTarea As String)
n += 1
If n > Ubound(a) Then Redim Preserve a(2 * n)
a(n - 1).Prioridad = fPrioridad
a(n - 1).Tarea = fTarea
bubbleUp (n - 1)
End Sub
 
Sub trickleDown(i As Integer)
Dim As Integer j, l, r
Do
j = -1
r = Dcha(i)
If r < n And a(r).Prioridad < a(i).Prioridad Then
l = Izda(i)
If a(l).Prioridad < a(r).Prioridad Then
j = l
Else
j = r
End If
Else
l = Izda(i)
If l < n And a(l).Prioridad < a(i).Prioridad Then j = l
End If
If j >= 0 Then Intercambio i, j
i = j
Loop While i >= 0
End Sub
 
Function Remove() As Tupla
Dim As Tupla x = a(0)
a(0) = a(n - 1)
n = n - 1
trickleDown 0
If 3 * n < Ubound(a) Then Redim Preserve a(Ubound(a) \ 2)
Remove = x
End Function
 
 
Redim a(4)
Annadir (3, "Clear drains")
Annadir (4, "Feed cat")
Annadir (5, "Make tea")
Annadir (1, "Solve RC tasks")
Annadir (2, "Tax return")
Dim t As Tupla
Do While n > 0
t = Remove
Print t.Prioridad; " "; t.Tarea
Loop
Sleep</syntaxhighlight>
{{out}}
<pre>
Igual que la entrada de VBA.
</pre>
 
=={{header|Batch File}}==
Line 1,631 ⟶ 1,792:
#include <stdlib.h>
#include "pairheap.h"
 
/* ---------------------------------------------------------------------------
* Pairing heap implementation
* --------------------------------------------------------------------------- */
 
static heap_t add_child(heap_t h, heap_t g) {
if (h->down != NULL)
g->next = h->down;
h->down = g;
}
Line 1,642 ⟶ 1,807:
if (b == NULL) return a;
if (a->key < b->key) {
add_child(a, b);
return a;
} else {
add_child(b, a);
return b;
}
}
Line 1,655 ⟶ 1,820:
heap_t two_pass_merge(heap_t h) {
if (h == NULL || h->next == NULL)
return h;
else {
pq_node_t
*a = h,
*b = h->next,
*rest = b->next;
a->next = b->next = NULL;
return heap_merge(heap_merge(a, b), two_pass_merge(rest));
}
}
Line 1,702 ⟶ 1,867:
 
while (heap != NULL) {
struct task *top = (struct task *) heap;
printf("%s\n", top->task);
heap = heap_pop(heap);
free(top);
}
}
Line 2,227 ⟶ 2,392:
4: Feed cat
5: Make tea</pre>
 
=={{header|COBOL}}==
 
===IBM Enterprise COBOL solution===
 
Note that the logic of this implementation follows the C solution above for "Pairing heap w/ generic data types" except that the "generic type" (the TASK record defintion) is sized and allocated in the calling test program instead of in the priority queue subroutines.
 
Note also that each subroutine is declared RECURSIVE though they do not all need it.
 
The subroutines each pass back a return value in their last parameter. The most recent release of the IBM Enterprise COBOL compiler (V6.4 as of the date of this contribution) does, in fact, support user-defined functions, which would make some of this implementation a little easier to write and read, but since many IBM shops are not yet up to the most recent level, this version is offered as one that will work with down-level compiler versions.
 
In the "two pass merge" subroutine (PTYQ2PMG), the final three lines are needed because the COBOL CALL statement does not allow for expressions as arguments, so the arguments to the outer call to the "merge" subroutine must be executed first, and the results of those two calls become the arguments to the final "merge" call.
 
Note also that the subroutines call each other using "PIC X(8)" pseudonyms because the actually recursive subroutines cannot use the "same name" as both the PROGRAM-ID and as a variable name. This could be resolved by simply using "constant" calls (like <code>CALL "PTYQ2PMG" USING . . . </code> but using the pseudonyms allows each of the subroutines to also be separately compiled into an executable module and then dynamically loaded at run time. Many IBM shops will prefer that method to this purely "static" solution.
 
<syntaxhighlight lang="COBOL">
PROCESS NOSEQ,DS(S),AR(E),TEST(SO),CP(1047)
IDENTIFICATION DIVISION.
PROGRAM-ID. PTYQTEST
ENVIRONMENT DIVISION.
CONFIGURATION SECTION.
* UNCOMMENT WITH DEBUGGING CLAUSE FOR DEBUG LINES TO EXECUTE.
SOURCE-COMPUTER.
Z-SYSTEM
* WITH DEBUGGING MODE
.
 
DATA DIVISION.
WORKING-STORAGE SECTION.
01 PTYQ-PGMNAMES.
05 PTYQPUSH PIC X(8) VALUE "PTYQPUSH".
05 PTYQPOP PIC X(8) VALUE "PTYQPOP".
 
01 TASK-PTR POINTER.
 
01 TOP-PTR POINTER.
 
01 LINK-KEY PIC S9(8) COMP-5.
 
01 HEAP-PTR POINTER VALUE NULL.
 
01 PUSHD-PTR POINTER VALUE NULL.
 
01 POPPD-PTR POINTER VALUE NULL.
 
LINKAGE SECTION.
01 TASK.
05 TASK-NODE.
10 TASK-KEY PIC S9(8) COMP-5.
10 TASK-NEXT POINTER.
10 TASK-DOWN POINTER.
05 TASK-NAME PIC X(40).
 
PROCEDURE DIVISION.
ALLOCATE TASK RETURNING TASK-PTR
MOVE "EAT SCONES." TO TASK-NAME
MOVE +6 TO LINK-KEY
CALL PTYQPUSH USING TASK-PTR, LINK-KEY, HEAP-PTR, PUSHD-PTR
SET HEAP-PTR TO PUSHD-PTR
 
ALLOCATE TASK RETURNING TASK-PTR
MOVE "CLEAR DRAINS." TO TASK-NAME
MOVE +3 TO LINK-KEY
CALL PTYQPUSH USING TASK-PTR, LINK-KEY, HEAP-PTR, PUSHD-PTR
SET HEAP-PTR TO PUSHD-PTR
 
ALLOCATE TASK RETURNING TASK-PTR
MOVE "FEED CAT." TO TASK-NAME
MOVE +4 TO LINK-KEY
CALL PTYQPUSH USING TASK-PTR, LINK-KEY, HEAP-PTR, PUSHD-PTR
SET HEAP-PTR TO PUSHD-PTR
 
ALLOCATE TASK RETURNING TASK-PTR
MOVE "MAKE TEA." TO TASK-NAME
MOVE +5 TO LINK-KEY
CALL PTYQPUSH USING TASK-PTR, LINK-KEY, HEAP-PTR, PUSHD-PTR
SET HEAP-PTR TO PUSHD-PTR
 
ALLOCATE TASK RETURNING TASK-PTR
MOVE "SOLVE RC TASKS." TO TASK-NAME
MOVE +1 TO LINK-KEY
CALL PTYQPUSH USING TASK-PTR, LINK-KEY, HEAP-PTR, PUSHD-PTR
SET HEAP-PTR TO PUSHD-PTR
 
ALLOCATE TASK RETURNING TASK-PTR
MOVE "TAX RETURN." TO TASK-NAME
MOVE +2 TO LINK-KEY
CALL PTYQPUSH USING TASK-PTR, LINK-KEY, HEAP-PTR, PUSHD-PTR
SET HEAP-PTR TO PUSHD-PTR
 
PERFORM WITH TEST BEFORE UNTIL HEAP-PTR = NULL
SET TOP-PTR TO HEAP-PTR
SET ADDRESS OF TASK TO TOP-PTR
DISPLAY TASK-KEY " " TASK-NAME
CALL PTYQPOP USING HEAP-PTR, POPPD-PTR
SET HEAP-PTR TO POPPD-PTR
FREE TOP-PTR
END-PERFORM
GOBACK.
END PROGRAM PTYQTEST.
PROCESS NOSEQ,DS(S),AR(E),TEST(SO),CP(1047)
IDENTIFICATION DIVISION.
PROGRAM-ID. PTYQMERG RECURSIVE.
ENVIRONMENT DIVISION.
CONFIGURATION SECTION.
* UNCOMMENT WITH DEBUGGING CLAUSE FOR DEBUG LINES TO EXECUTE.
SOURCE-COMPUTER.
Z-SYSTEM
* WITH DEBUGGING MODE
.
 
DATA DIVISION.
 
LINKAGE SECTION.
01 HEAP-PTRA POINTER.
 
01 HEAP-PTRB POINTER.
 
01 MERGD-PTR POINTER.
 
01 HEAPA.
05 HEAPA-KEY PIC S9(8) COMP-5 VALUE +0.
05 HEAPA-NEXT POINTER.
05 HEAPA-DOWN POINTER.
 
01 HEAPB.
05 HEAPB-KEY PIC S9(8) COMP-5 VALUE +0.
05 HEAPB-NEXT POINTER.
05 HEAPB-DOWN POINTER.
 
PROCEDURE DIVISION USING HEAP-PTRA, HEAP-PTRB, MERGD-PTR.
EVALUATE TRUE
WHEN HEAP-PTRA = NULL
SET MERGD-PTR TO HEAP-PTRB
WHEN HEAP-PTRB = NULL
SET MERGD-PTR TO HEAP-PTRA
WHEN OTHER
SET ADDRESS OF HEAPA TO HEAP-PTRA
SET ADDRESS OF HEAPB TO HEAP-PTRB
IF HEAPA-KEY < HEAPB-KEY
IF HEAPA-DOWN NOT = NULL
SET HEAPB-NEXT TO HEAPA-DOWN
END-IF
SET HEAPA-DOWN TO HEAP-PTRB
SET MERGD-PTR TO HEAP-PTRA
ELSE
IF HEAPB-DOWN NOT = NULL
SET HEAPA-NEXT TO HEAPB-DOWN
END-IF
SET HEAPB-DOWN TO HEAP-PTRA
SET MERGD-PTR TO HEAP-PTRB
END-IF
END-EVALUATE
GOBACK.
END PROGRAM PTYQMERG.
PROCESS NOSEQ,DS(S),AR(E),TEST(SO),CP(1047)
IDENTIFICATION DIVISION.
PROGRAM-ID. PTYQ2PMG RECURSIVE.
ENVIRONMENT DIVISION.
CONFIGURATION SECTION.
* UNCOMMENT WITH DEBUGGING CLAUSE FOR DEBUG LINES TO EXECUTE.
SOURCE-COMPUTER.
Z-SYSTEM
* WITH DEBUGGING MODE
.
 
DATA DIVISION.
WORKING-STORAGE SECTION.
01 PGMQMERG PIC X(8) VALUE "PTYQMERG".
01 PGMQ2PMG PIC X(8) VALUE "PTYQ2PMG".
 
LOCAL-STORAGE SECTION.
01 HEAP-PTRA POINTER.
 
01 HEAP-PTRB POINTER.
 
01 HEAP-REST POINTER.
 
01 MERG1-PTR POINTER.
 
01 MERG2-PTR POINTER.
 
LINKAGE SECTION.
01 HEAP-PTR POINTER.
 
01 MERGD-PTR POINTER.
 
01 HEAP.
05 HEAP-KEY PIC S9(8) COMP-5 VALUE +0.
05 HEAP-NEXT POINTER.
05 HEAP-DOWN POINTER.
 
01 HEAPA.
05 HEAPA-KEY PIC S9(8) COMP-5 VALUE +0.
05 HEAPA-NEXT POINTER.
05 HEAPA-DOWN POINTER.
 
01 HEAPB.
05 HEAPB-KEY PIC S9(8) COMP-5 VALUE +0.
05 HEAPB-NEXT POINTER.
05 HEAPB-DOWN POINTER.
 
01 REST.
05 REST-KEY PIC S9(8) COMP-5 VALUE +0.
05 REST-NEXT POINTER.
05 REST-DOWN POINTER.
 
PROCEDURE DIVISION USING HEAP-PTR, MERGD-PTR.
SET ADDRESS OF HEAP TO HEAP-PTR
EVALUATE TRUE
WHEN HEAP-PTR = NULL
SET MERGD-PTR TO HEAP-PTR
WHEN HEAP-NEXT = NULL
SET MERGD-PTR TO HEAP-PTR
WHEN OTHER
SET HEAP-PTRA TO HEAP-PTR
SET ADDRESS OF HEAPA TO HEAP-PTRA
SET HEAP-PTRB TO HEAP-NEXT
SET ADDRESS OF HEAPB TO HEAP-PTRB
SET HEAP-REST TO HEAPB-NEXT
SET ADDRESS OF REST TO HEAP-REST
SET HEAPA-NEXT TO NULL
SET HEAPB-NEXT TO NULL
CALL PGMQMERG USING HEAP-PTRA, HEAP-PTRB, MERG1-PTR
CALL PGMQ2PMG USING HEAP-REST, MERG2-PTR
CALL PGMQMERG USING MERG1-PTR, MERG2-PTR, MERGD-PTR
END-EVALUATE
GOBACK.
END PROGRAM PTYQ2PMG.
PROCESS NOSEQ,DS(S),AR(E),TEST(SO),CP(1047)
IDENTIFICATION DIVISION.
PROGRAM-ID. PTYQPUSH RECURSIVE.
ENVIRONMENT DIVISION.
CONFIGURATION SECTION.
* UNCOMMENT WITH DEBUGGING CLAUSE FOR DEBUG LINES TO EXECUTE.
SOURCE-COMPUTER.
Z-SYSTEM
* WITH DEBUGGING MODE
.
 
DATA DIVISION.
WORKING-STORAGE SECTION.
01 PTYQMERG PIC X(8) VALUE "PTYQMERG".
 
LINKAGE SECTION.
01 NODE-PTR POINTER.
 
01 LINK-KEY PIC S9(8) COMP-5.
 
01 HEAP-PTR POINTER.
 
01 PUSHD-PTR POINTER.
 
01 HEAP.
05 HEAP-KEY PIC S9(8) COMP-5.
05 HEAP-NEXT POINTER.
05 HEAP-DOWN POINTER.
 
01 NODE.
05 NODE-KEY PIC S9(8) COMP-5.
05 NODE-NEXT POINTER.
05 NODE-DOWN POINTER.
 
PROCEDURE DIVISION USING NODE-PTR, LINK-KEY, HEAP-PTR, PUSHD-PTR.
SET ADDRESS OF NODE TO NODE-PTR
SET ADDRESS OF HEAP TO HEAP-PTR
SET NODE-NEXT TO NULL
SET NODE-DOWN TO NULL
MOVE LINK-KEY TO NODE-KEY
CALL PTYQMERG USING NODE-PTR, HEAP-PTR, PUSHD-PTR
GOBACK.
END PROGRAM PTY2PUSH.
PROCESS NOSEQ,DS(S),AR(E),TEST(SO),CP(1047)
IDENTIFICATION DIVISION.
PROGRAM-ID. PTYQPOP RECURSIVE.
ENVIRONMENT DIVISION.
CONFIGURATION SECTION.
* UNCOMMENT WITH DEBUGGING CLAUSE FOR DEBUG LINES TO EXECUTE.
SOURCE-COMPUTER.
Z-SYSTEM
* WITH DEBUGGING MODE
.
 
DATA DIVISION.
WORKING-STORAGE SECTION.
01 PTYQ2PMG PIC X(8) VALUE "PTYQ2PMG".
 
LINKAGE SECTION.
01 HEAP-PTR POINTER.
 
01 POPPD-PTR POINTER.
 
01 HEAP.
05 HEAP-KEY PIC S9(8) COMP-5 VALUE +0.
05 HEAP-NEXT POINTER.
05 HEAP-DOWN POINTER.
 
PROCEDURE DIVISION USING HEAP-PTR, POPPD-PTR.
SET ADDRESS OF HEAP TO HEAP-PTR
CALL PTYQ2PMG USING HEAP-DOWN, POPPD-PTR
GOBACK.
END PROGRAM PTYQPOP.
</syntaxhighlight>
 
{{out}}
<pre>
+0000000001 SOLVE RC TASKS.
+0000000002 TAX RETURN.
+0000000003 CLEAR DRAINS.
+0000000004 FEED CAT.
+0000000005 MAKE TEA.
+0000000006 EAT SCONES.
</pre>
 
=={{header|CoffeeScript}}==
Line 3,393 ⟶ 3,871:
! 1 -> Solve RC tasks
</syntaxhighlight>
 
 
=={{header|FreeBASIC}}==
{{trans|VBA}}
<syntaxhighlight lang="freebasic">Type Tupla
Prioridad As Integer
Tarea As String
End Type
Dim Shared As Tupla a()
Dim Shared As Integer n 'número de eltos. en la matriz, el último elto. es n-1
 
Function Izda(i As Integer) As Integer
Izda = 2 * i + 1
End Function
 
Function Dcha(i As Integer) As Integer
Dcha = 2 * i + 2
End Function
 
Function Parent(i As Integer) As Integer
Parent = (i - 1) \ 2
End Function
 
Sub Intercambio(i As Integer, j As Integer)
Dim t As Tupla
t = a(i)
a(i) = a(j)
a(j) = t
End Sub
 
Sub bubbleUp(i As Integer)
Dim As Integer p = Parent(i)
Do While i > 0 And a(i).Prioridad < a(p).Prioridad
Intercambio i, p
i = p
p = Parent(i)
Loop
End Sub
 
Sub Annadir(fPrioridad As Integer, fTarea As String)
n += 1
If n > Ubound(a) Then Redim Preserve a(2 * n)
a(n - 1).Prioridad = fPrioridad
a(n - 1).Tarea = fTarea
bubbleUp (n - 1)
End Sub
 
Sub trickleDown(i As Integer)
Dim As Integer j, l, r
Do
j = -1
r = Dcha(i)
If r < n And a(r).Prioridad < a(i).Prioridad Then
l = Izda(i)
If a(l).Prioridad < a(r).Prioridad Then
j = l
Else
j = r
End If
Else
l = Izda(i)
If l < n And a(l).Prioridad < a(i).Prioridad Then j = l
End If
If j >= 0 Then Intercambio i, j
i = j
Loop While i >= 0
End Sub
 
Function Remove() As Tupla
Dim As Tupla x = a(0)
a(0) = a(n - 1)
n = n - 1
trickleDown 0
If 3 * n < Ubound(a) Then Redim Preserve a(Ubound(a) \ 2)
Remove = x
End Function
 
 
Redim a(4)
Annadir (3, "Clear drains")
Annadir (4, "Feed cat")
Annadir (5, "Make tea")
Annadir (1, "Solve RC tasks")
Annadir (2, "Tax return")
Dim t As Tupla
Do While n > 0
t = Remove
Print t.Prioridad; " "; t.Tarea
Loop
Sleep</syntaxhighlight>
{{out}}
<pre>
Igual que la entrada de VBA.
</pre>
 
=={{header|Frink}}==
Line 4,290 ⟶ 4,674:
{{out}}
<pre>Hello!</pre>
 
=={{header|Logtalk}}==
 
Logtalk comes with a [https://github.com/LogtalkDotOrg/logtalk3/tree/master/library/heaps heap implementation] out of the box. As such it by definition also has a priority queue. It can be used at the toplevel like this (with some formatting changes for clarity, and <code>%</code> marking comments that would not be in the output):
 
<syntaxhighlight lang="logtalk">?- logtalk_load(heaps(loader)). % also `{heaps(loader)}.` on most back-ends
% output varies by settings and what's already been loaded
?- heap(<)::new(H0), % H0 contains an empty heap
heap(<)::insert(3, 'Clear drains', H0, H1), % as with Prolog, variables are in the mathematical
% sense: immutable, so we make a new heap from the empty one
heap(<)::insert(4, 'Feed cat',H1, H2), % with each insertion a new heap
heap(<)::top(H2, K2, V2), % K2=3, V2='Clear drains',
% H2=t(2, [], t(3, 'Clear drains', t(4, 'Feed cat', t, t), t))
heap(<)::insert_all(
[
5-'Make tea',
1-'Solve RC tasks',
2-'Tax return'
], H2, H3), % it's easier and more efficient to add items in K-V pairs
heap(<)::top(H3, K3, V3), % K3=1, V3='Solve RC tasks',
% H3=t(5, [], t(1, 'Solve RC tasks', t(3, 'Clear drains',
% t(4, 'Feed cat', t, t), t), t(2, 'Tax return',
% t(5, 'Make tea', t, t), t))),
heap(<)::delete(H3, K3, V3, H4), % K3=1, V3='Solve RC tasks',
% H4=t(4, [5], t(2, 'Tax return', t(3, 'Clear drains',
% t(4, 'Feed cat', t, t), t), t(5, 'Make tea', t, t))),
heap(<)::top(H4, K4, V4). % K4=2, V4='Tax return'</syntaxhighlight>
 
Since <code>heap(Ordering)</code> is a parametrized object in Logtalk, with the parameter being the ordering predicate, we actually use <code>heap(<)</code> object to get min ordering. There are two objects provided in Logtalk that eliminate the unnecessary replication of the two most common orderings:
 
<syntaxhighlight lang="logtalk">:- object(minheap,
extends(heap(<))).
 
:- info([
version is 1:0:0,
author is 'Paulo Moura.',
date is 2010-02-19,
comment is 'Min-heap implementation. Uses standard order to compare keys.'
]).
 
:- end_object.
 
 
:- object(maxheap,
extends(heap(>))).
 
:- info([
version is 1:0:0,
author is 'Paulo Moura.',
date is 2010-02-19,
comment is 'Max-heap implementation. Uses standard order to compare keys.'
]).
 
:- end_object.</syntaxhighlight>
 
Given the presence of these two objects, all of the example code above could have <code>heap(<)</code> replaced with <code>minheap</code> for identical results (including identical performance). It also illustrates how quickly and easily other orderings could be provided at need.
 
=={{header|Lua}}==
Line 4,676 ⟶ 5,116:
</syntaxhighlight>
 
===Using a stack with pointers to Groups as elements (with Merge Function)===
Now we use pointer to group, and use of Subs and simple Functions (called using @ prefix). Also we have a global countmany (is a long type, see 0&) to check how many objects exist. We have use "as *obj" to declare a parameter to stay as pointer and to check the type (here is obj). The remove method of object called when object has to be removed. The constructor module obj called once and not exist in the final object obj (it is a part under Class: label, and this part define things for construction time only). Property toString$ is a group which return value (a string value), and we can use it with or without parameter. Because it is a group, we have to link parent properties/functions (but not modules) to get access.
 
Added Merge function. We can choose if we leave the second queue untouched or erase each item as we merge it to the first queue, using the third parameter.
 
<syntaxhighlight lang="m2000 interpreter">
Line 4,689 ⟶ 5,130:
value$=format$("{0::-5}"+string$(" ", sp)+"{1:20}", x, s$)
}
}
function Copy {
countmany++
z=this
=pointer((z))
}
remove {
Line 4,705 ⟶ 5,151:
Flush ' empty current stack
Data g(3, "Clear drains"),g(4 ,"Feed cat"), g( 5 , "Make tea")
Data g( 1 ,"Solve RC tasks"), g( 2 , "Tax return")
ObjectCount()
bpq=stack
zz=stack
while not empty
InsertPQ(bpq) // top of stack is bpq then objects follow
end while
Pen 15 {
data g(2 , "Tax return"), g(1 ,"Solve RC tasks#2")
while not empty: InsertPq(zz): End While
n1=each(zz,-1,1)
Header()
while n1
Print @Peek$(stackitem(n1))
end while
}
MergePq(pq, zz, false)
InsertPq(pq, g(1 ,"Solve RC tasks#3"))
ObjectCount()
Print "Using Peek to Examine Priority Queue"
n1=each(bpq,-1, 1)
Header()
while n1
Print @Peek$(stackitem(n1))
end while
ObjectCount()
Header()
while not @isEmpty(bpq)
Print @Pop(bpq)=>tostring$
end while
ObjectCount()
Header()
while not @isEmpty(zz)
Print @Pop(zz)=>tostring$
end while
ObjectCount()
Line 4,732 ⟶ 5,195:
sub ObjectCount()
Print "There are ";countmany;" objects of type obj"
end sub
sub MergePq(a, pq, emptyqueue)
local n1=each(pq, -1, 1), z=pointer()
while n1
if emptyqueue then
stack pq {
shiftback len(pq)
InsertPQ(a, Group)
}
else
z=stackitem(n1)
InsertPQ(a, z=>copy())
end if
end while
end sub
sub InsertPQ(a, n as *obj)
Line 4,739 ⟶ 5,216:
stack a {
push n
local t=2, bpq=len(a), t1=0
local m=bpq
while t<=bpq
t1=m
m=(bpq+t) div 2
if m=0 then m=t1 : exit
If @comp(stackitem(m),n) then t=m+1: continue
bpq=m-1
m=bpq
end while
if m>1 then shiftback m
}
end sub
function comp(a as *obj, bpq as *obj)
=a=>x<b>pq=>x
end function
function Peek$(a as stack*obj)
=stackitem(a)=>toString$
end function
function IsEmpty(a)
Line 4,763 ⟶ 5,240:
function Pop(a)
// Group make a copy (but here is a pointer of group)
stack a {=Group}shift stack.size
=Group}
end function
}
PriorityQueueForGroups
</syntaxhighlight>
 
===Using ordered list (plus merge function)===
<syntaxhighlight lang="m2000 interpreter">
form 80, 42
Module OrdrerQueue (filename$) {
// f=-2 or use empty filename for screen
open filename$ for output as #f
zz=list
pq=List
flush
// subs can read from module's stack
println("Add items to pq queue")
Data 4 ,"Feed cat",5 , "Make tea", 3, "Clear drains",1 , "Solve RC tasks"
AddItems(pq)
println("Add items to zz queue")
AddItems(zz, 2 , "Tax return", 1 ,"Solve RC tasks#2")
println("Peek top from zz queue")
PeekTop(zz) // Solve RC tasks#2
println("Merge two priority lists")
merge(pq, zz, false)
println("Peek top from pq queue")
PeekTop(pq) // Solve RC tasks
println("Add items to pq queue")
AddItems(pq, 1 ,"Solve RC tasks#3")
println("Peek top from pq queue")
PeekTop(pq) // Solve RC tasks
println("Pop one from pq until empty queue")
while len(pq)>0
PopOne(pq)
end while
println("Pop one from zz until empty queue")
while len(zz)>0
PopOne(zz)
end while
close #f
sub AddItems(pq)
local s, z
while not empty
read z
if not exist(pq, z) then s=stack:append pq, z:=s else s=eval(pq)
read what$: stack s {data what$}
stack new {println( "add item",z,what$)}
end while
sort descending pq as number
Println()
end sub
sub merge(pq, qp, emptyqueue)
local needsort=false
local kqp=each(qp, -1, 1), k$, t, p
while kqp
t=eval(kqp)
k$= eval$(kqp!)
if not exist(pq, eval$(kqp!)) then
p=stack
append pq, val(eval$(kqp!)):=p
needsort=true
else
p=eval(pq)
end if
stack p {
if emptyqueue then
data !t
delete qp,eval$(kqp!)
else
data !stack(t)
end if
}
end while
if needsort then sort descending pq as number
end sub
sub PeekTop(pq)
Local k=len(pq)
if k=0 then exit sub
k=val(eval$(pq, k-1))
if exist(pq, k) then local s=eval(pq): println( k,stackitem$(s, 1))
End sub
Sub PopOne(pq)
Local k=len(pq)
if k<0 then exit sub
k=val(eval$(pq, k-1))
if exist(pq, k) then
local s=eval(pq)
println( k,stackitem$(s, 1))
if len(s)=1 then
delete pq, k
else
stack s {drop}
end if
end if
end sub
Sub println()
if empty then print #f, "": exit sub
while not empty
if islet then print #f, letter$;
if empty else print #f, " ";
if isnum then print #f, number;
if empty else print #f, " ";
end while
if f=-2 and pos=0 then exit sub
print #f, ""
end sub
}
OrdrerQueue ""
</syntaxhighlight>
 
{{out}}
<pre>Add items to pq queue
add item 4 Feed cat
add item 5 Make tea
add item 3 Clear drains
add item 1 Solve RC tasks
 
Add items to zz queue
add item 2 Tax return
add item 1 Solve RC tasks#2
 
Peek top from zz queue
1 Solve RC tasks#2
Merge two priority lists
Peek top from pq queue
1 Solve RC tasks
Add items to pq queue
add item 1 Solve RC tasks#3
 
Peek top from pq queue
1 Solve RC tasks
Pop one from pq until empty queue
1 Solve RC tasks
1 Solve RC tasks#2
1 Solve RC tasks#3
2 Tax return
3 Clear drains
4 Feed cat
5 Make tea
Pop one from zz until empty queue
1 Solve RC tasks#2
2 Tax return
</pre>
 
=={{header|Mathematica}}/{{header|Wolfram Language}}==
Line 5,734 ⟶ 6,350:
 
=={{header|Perl}}==
===Using a Module===
There are a few implementations on CPAN. Following uses <code>Heap::Priority</code>[http://search.cpan.org/~fwojcik/Heap-Priority-0.11/Priority.pm]
<syntaxhighlight lang="perl">use 5.10.0strict;
use strictwarnings;
use feature 'say';
use Heap::Priority;
 
my $h = new Heap::Priority->new;
 
$h->highest_first(); # higher or lower number is more important
Line 5,748 ⟶ 6,366:
["Tax return", 2];
 
say while ($_ = $h->pop);</syntaxhighlight>output<syntaxhighlight lang="text">Make tea
{{out}}
<pre>
Make tea
Feed cat
Clear drains
Tax return
Solve RC tasks</syntaxhighlight>
</pre>
===IBM card sorter version===
<syntaxhighlight lang="perl">#!/usr/bin/perl
 
===IBM card sorter version===
use strict; # https://rosettacode.org/wiki/Priority_queue
<syntaxhighlight lang="perl">use strict;
use warnings; # in homage to IBM card sorters :)
 
Line 7,853 ⟶ 8,474:
Print
 
Proc _Insert(3, Dup("Clear drains")) ' insert the whole bunch
Proc _Insert(4, Dup("Feed cat"))
Proc _Insert(5, Dup("Make tea"))
Proc _Insert(1, Dup("Solve RC tasks"))
Proc _Insert(2, Dup("Tax return"))
 
For x = 0 To b: Proc _List(x) : Next ' list all entries
Line 7,873 ⟶ 8,494:
Local (2)
' return dummy on error
If b < 0 Then Return (Dup("0No such entry"))
a@ = @(0)) ' save the top entry
For b@ = 0 To Set(b, b - 1) : @(b@) = @(b@+1): Next
Line 8,140 ⟶ 8,761:
{{libheader|Wren-queue}}
The above module contains a PriorityQueue class. Unlike some other languages here, the higher the number, the higher the priority. So the 'Make tea' task has the highest priority and, thankfully, the cat has a good chance of being fed!
<syntaxhighlight lang="ecmascriptwren">import "./queue" for PriorityQueue
 
var tasks = PriorityQueue.new()
Line 8,267 ⟶ 8,888:
 
()</syntaxhighlight>
 
=={{header|XPL0}}==
The highest priority item is the one with the minimum number, as in 1st priority.
<syntaxhighlight lang "XPL0">def PQSize = 10; \Maximum number of items priority queue can hold
int PQ(PQSize*2), PQI;
 
func Remove; \Remove and return item with highest priority
int Min, I, MinI, Item;
[if PQI <= 0 then return 0;
Min:= -1>>1; I:= PQI;
while I > 0 do
[I:= I-2;
if PQ(I) < Min then
[Min:= PQ(I);
MinI:= I;
];
];
Item:= PQ(MinI+1); \get highest priority Item
PQI:= PQI-2;
PQ(MinI):= PQ(PQI); \replace that Item with last item
PQ(MinI+1):= PQ(PQI+1);
return Item;
];
 
proc Insert(Priority, Item); \Insert item into priority queue
int Priority, Item;
[if PQI >= PQSize*2 then return;
PQ(PQI):= Priority;
PQ(PQI+1):= Item;
PQI:= PQI+2;
];
 
int Items, I;
[Items:= [
[3, "Clear drains"],
[4, "Feed cat"],
[5, "Make tea"],
[1, "Solve RC tasks"],
[2, "Tax return"] ];
PQI:= 0;
for I:= 0 to 5-1 do
Insert(Items(I,0), Items(I,1));
while PQI > 0 do
[Text(0, Remove); CrLf(0)];
]</syntaxhighlight>
{{out}}
<pre>
Solve RC tasks
Tax return
Clear drains
Feed cat
Make tea
</pre>
 
=={{header|Zig}}==
Anonymous user
Retrieved from "https://rosettacode.org/wiki/Special:MobileDiff/333908...351062"