Priority queue: Difference between revisions
m
→{{header|Zig}}
Nima.trueway (talk | contribs) m (→{{header|Zig}}) |
|||
| (86 intermediate revisions by 36 users not shown) | |||
Line 2:
A [[wp:Priority queue|priority queue]] is somewhat similar to a [[Queue|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.
;Task:
Create a priority queue. The queue must support at least two operations:
:# Insertion. An element is added to the queue with a priority (a numeric value).
:# Top item removal. Deletes the element or one of the elements with the current top priority and return it.
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:
'''Priority''' '''Task'''
══════════ ════════════════
3 Clear drains
4 Feed cat
5 Make tea
1 Solve RC tasks
2 Tax return
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.
<br><br>
=={{header|11l}}==
{{trans|Python}}
<syntaxhighlight lang="11l">V items = [(3, ‘Clear drains’), (4, ‘Feed cat’), (5, ‘Make tea’), (1, ‘Solve RC tasks’), (2, ‘Tax return’)]
minheap:heapify(&items)
L !items.empty
print(minheap:pop(&items))</syntaxhighlight>
{{out}}
<pre>
(1, Solve RC tasks)
(2, Tax return)
(3, Clear drains)
(4, Feed cat)
(5, Make tea)
</pre>
=={{header|AArch64 Assembly}}==
{{works with|as|Raspberry Pi 3B version Buster 64 bits}}
<syntaxhighlight lang="aarch64 assembly">
/* ARM assembly AARCH64 Raspberry PI 3B */
/* program priorQueue64.s */
/*******************************************/
/* Constantes file */
/*******************************************/
/* for this file see task include a file in language AArch64 assembly*/
.include "../includeConstantesARM64.inc"
.equ NBMAXIELEMENTS, 100
/*******************************************/
/* Structures */
/********************************************/
/* example structure item */
.struct 0
item_priority: // priority
.struct item_priority + 8
item_address: // string address
.struct item_address + 8
item_fin:
/* example structure heap */
.struct 0
heap_size: // heap size
.struct heap_size + 8
heap_items: // structure of items
.struct heap_items + (item_fin * NBMAXIELEMENTS)
heap_fin:
/*********************************/
/* Initialized data */
/*********************************/
.data
szMessEmpty: .asciz "Empty queue. \n"
szMessNotEmpty: .asciz "Not empty queue. \n"
szMessError: .asciz "Error detected !!!!. \n"
szMessResult: .asciz "Priority : @ : @ \n" // message result
szString1: .asciz "Clear drains"
szString2: .asciz "Feed cat"
szString3: .asciz "Make tea"
szString4: .asciz "Solve RC tasks"
szString5: .asciz "Tax return"
szCarriageReturn: .asciz "\n"
/*********************************/
/* UnInitialized data */
/*********************************/
.bss
.align 4
sZoneConv: .skip 24
Queue1: .skip heap_fin // queue memory place
/*********************************/
/* code section */
/*********************************/
.text
.global main
main: // entry of program
ldr x0,qAdrQueue1 // queue structure address
bl isEmpty
cbz x0,1f
ldr x0,qAdrszMessEmpty
bl affichageMess // display message empty
b 2f
1:
ldr x0,qAdrszMessNotEmpty
bl affichageMess // display message not empty
2:
// init item 1
ldr x0,qAdrQueue1 // queue structure address
mov x1,#3 // priority
ldr x2,qAdrszString1
bl pushQueue // add item in queue
cmp x0,#-1 // error ?
beq 99f
ldr x0,qAdrQueue1 // queue structure address
bl isEmpty
cbz x0,3f // not empty
ldr x0,qAdrszMessEmpty
bl affichageMess // display message empty
b 4f
3:
ldr x0,qAdrszMessNotEmpty
bl affichageMess // display message not empty
4:
// init item 2
ldr x0,qAdrQueue1 // queue structure address
mov x1,#4 // priority
ldr x2,qAdrszString2
bl pushQueue // add item in queue
cmp x0,#-1 // error ?
beq 99f
// init item 3
ldr x0,qAdrQueue1 // queue structure address
mov x1,#5 // priority
ldr x2,qAdrszString3
bl pushQueue // add item in queue
cmp x0,#-1 // error ?
beq 99f
// init item 4
ldr x0,qAdrQueue1 // queue structure address
mov x1,#1 // priority
ldr x2,qAdrszString4
bl pushQueue // add item in queue
cmp x0,#-1 // error ?
beq 99f
// init item 5
ldr x0,qAdrQueue1 // queue structure address
mov x1,#2 // priority
ldr x2,qAdrszString5
bl pushQueue // add item in queue
cmp x0,#-1 // error ?
beq 99f
5:
ldr x0,qAdrQueue1 // queue structure address
bl popQueue // return item
cmp x0,#-1 // end ?
beq 100f
mov x2,x1 // save string address
ldr x1,qAdrsZoneConv // conversion priority
bl conversion10 // decimal conversion
ldr x0,qAdrszMessResult
ldr x1,qAdrsZoneConv
bl strInsertAtCharInc
mov x1,x2 // string address
bl strInsertAtCharInc
bl affichageMess // display message
b 5b // loop
99: // error
ldr x0,qAdrszMessError
bl affichageMess
100: // standard end of the program
mov x0, #0 // return code
mov x8, #EXIT // request to exit program
svc #0 // perform the system call
qAdrQueue1: .quad Queue1
qAdrszString1: .quad szString1
qAdrszString2: .quad szString2
qAdrszString3: .quad szString3
qAdrszString4: .quad szString4
qAdrszString5: .quad szString5
qAdrszMessError: .quad szMessError
qAdrszMessEmpty: .quad szMessEmpty
qAdrszMessNotEmpty: .quad szMessNotEmpty
qAdrszMessResult: .quad szMessResult
qAdrszCarriageReturn: .quad szCarriageReturn
//qAdrsMessPriority: .quad sMessPriority
qAdrsZoneConv: .quad sZoneConv
/******************************************************************/
/* test if queue empty */
/******************************************************************/
/* x0 contains the address of queue structure */
isEmpty:
stp x1,lr,[sp,-16]! // save registres
ldr x1,[x0,#heap_size] // heap size
cmp x1,#0
cset x0,eq
ldp x1,lr,[sp],16 // restaur des 2 registres
ret
/******************************************************************/
/* add item in queue */
/******************************************************************/
/* x0 contains the address of queue structure */
/* x1 contains the priority of item */
/* x2 contains the string address */
pushQueue:
stp x1,lr,[sp,-16]! // save registres
stp x2,x3,[sp,-16]! // save registres
stp x4,x5,[sp,-16]! // save registres
stp x6,x7,[sp,-16]! // save registres
stp x8,x9,[sp,-16]! // save registres
ldr x3,[x0,#heap_size] // heap size
cbnz x3,1f // heap empty ?
add x4,x0,#heap_items // address of item structure
str x1,[x4,#item_priority] // store in first item
str x2,[x4,#item_address]
mov x3,#1 // heap size
str x3,[x0,#heap_size] // new heap size
b 100f
1:
mov x4,x3 // maxi index
lsr x5,x4,#1 // current index = maxi / 2
mov x8,x1 // save priority
mov x9,x2 // save string address
2: // insertion loop
cmp x4,#0 // end loop ?
ble 3f
mov x6,#item_fin // item size
madd x6,x5,x6,x0 // item shift
add x6,x6,#heap_items // compute address item
ldr x7,[x6,#item_priority] // load priority
cmp x7,x8 // compare priority
ble 3f // <= end loop
mov x1,x4 // last index
mov x2,x5 // current index
bl exchange
mov x4,x5 // last index = current index
lsr x5,x5,#1 // current index / 2
b 2b
3: // store item at last index find
mov x6,#item_fin // item size
madd x6,x4,x6,x0 // item shift
add x6,x6,#heap_items // item address
str x8,[x6,#item_priority]
str x9,[x6,#item_address]
add x3,x3,#1 // increment heap size
cmp x3,#NBMAXIELEMENTS // maxi ?
bge 99f // yes -> error
str x3,[x0,#heap_size] // store new size
b 100f
99:
mov x0,#-1 // error
100:
ldp x8,x9,[sp],16 // restaur des 2 registres
ldp x6,x7,[sp],16 // restaur des 2 registres
ldp x4,x5,[sp],16 // restaur des 2 registres
ldp x2,x3,[sp],16 // restaur des 2 registres
ldp x1,lr,[sp],16 // restaur des 2 registres
ret
/******************************************************************/
/* swap two elements of table */
/******************************************************************/
/* x0 contains the address of table */
/* x1 contains the first index */
/* x2 contains the second index */
exchange:
stp x1,lr,[sp,-16]! // save registres
stp x2,x3,[sp,-16]! // save registres
stp x4,x5,[sp,-16]! // save registres
stp x6,x7,[sp,-16]! // save registres
add x5,x0,#heap_items // address items begin
mov x3,#item_fin // item size
madd x4,x1,x3,x5 // compute item 1 address
madd x6,x2,x3,x5 // compute item 2 address
ldr x5,[x4,#item_priority] // exchange
ldr x3,[x6,#item_priority]
str x3,[x4,#item_priority]
str x5,[x6,#item_priority]
ldr x5,[x4,#item_address]
ldr x3,[x6,#item_address]
str x5,[x6,#item_address]
str x3,[x4,#item_address]
100:
ldp x6,x7,[sp],16 // restaur des 2 registres
ldp x4,x5,[sp],16 // restaur des 2 registres
ldp x2,x3,[sp],16 // restaur des 2 registres
ldp x1,lr,[sp],16 // restaur des 2 registres
ret
/******************************************************************/
/* move one element of table */
/******************************************************************/
/* x0 contains the address of table */
/* x1 contains the origin index */
/* x2 contains the destination index */
moveItem:
stp x1,lr,[sp,-16]! // save registres
stp x2,x3,[sp,-16]! // save registres
stp x4,x5,[sp,-16]! // save registres
stp x6,x7,[sp,-16]! // save registres
add x5,x0,#heap_items // address items begin
mov x3,#item_fin // item size
madd x4,x1,x3,x5 // compute item 1 address
madd x6,x2,x3,x5 // compute item 2 address
ldr x5,[x4,#item_priority] // exchange
str x5,[x6,#item_priority]
ldr x5,[x4,#item_address]
str x5,[x6,#item_address]
100:
ldp x6,x7,[sp],16 // restaur des 2 registres
ldp x4,x5,[sp],16 // restaur des 2 registres
ldp x2,x3,[sp],16 // restaur des 2 registres
ldp x1,lr,[sp],16 // restaur des 2 registres
ret
/******************************************************************/
/* pop queue */
/******************************************************************/
/* x0 contains the address of queue structure */
/* x0 return priority */
/* x1 return string address */
popQueue:
stp x10,lr,[sp,-16]! // save registres
stp x2,x3,[sp,-16]! // save registres
stp x4,x5,[sp,-16]! // save registres
stp x6,x7,[sp,-16]! // save registres
stp x8,x9,[sp,-16]! // save registres
mov x1,x0 // save address queue
bl isEmpty // control if empty queue
cmp x0,#1 // yes -> error
beq 99f
mov x0,x1 // restaur address queue
add x4,x0,#heap_items // address of item structure
ldr x8,[x4,#item_priority] // save priority first item
ldr x9,[x4,#item_address] // save address string first item
ldr x3,[x0,#heap_size] // heap size
sub x7,x3,#1 // last item
mov x1,x7
mov x2,#0 // first item
bl moveItem // move last item in first item
cmp x7,#1 // one only item ?
beq 10f // yes -> end
mov x4,#0 // first index
1:
cmp x4,x7 // = last index
bge 10f // yes -> end
mov x5,x7 // last index
cmp x4,#0 // init current index
mov x6,#1 // = 1
lsl x1,x4,#1 // else = first index * 2
csel x6,x6,x1,eq
cmp x6,x7 // current index > last index
bgt 2f // yes
// no compar priority current item last item
mov x1,#item_fin
madd x1,x6,x1,x0
add x1,x1,#heap_items // address of current item structure
ldr x1,[x1,#item_priority]
mov x10,#item_fin
madd x10,x5,x10,x0
add x10,x10,#heap_items // address of last item structure
ldr x10,[x10,#item_priority]
cmp x1,x10
csel x5,x6,x5,lt
2:
add x10,x6,#1 // increment current index
cmp x10,x7 // end ?
bgt 3f // yes
mov x1,#item_fin // no compare priority
madd x1,x10,x1,x0
add x1,x1,#heap_items // address of item structure
ldr x1,[x1,#item_priority]
mov x2,#item_fin
madd x2,x5,x2,x0
add x2,x2,#heap_items // address of item structure
ldr x2,[x2,#item_priority]
cmp x1,x2
csel x5,x10,x5,lt
3:
mov x1,x5 // move item
mov x2,x4
bl moveItem
mov x4,x5
b 1b // and loop
10:
sub x3,x3,#1
str x3,[x0,#heap_size] // new heap size
mov x0,x8 // return priority
mov x1,x9 // return string address
b 100f
99:
mov x0,#-1 // error
100:
ldp x8,x9,[sp],16 // restaur des 2 registres
ldp x6,x7,[sp],16 // restaur des 2 registres
ldp x4,x5,[sp],16 // restaur des 2 registres
ldp x2,x3,[sp],16 // restaur des 2 registres
ldp x10,lr,[sp],16 // restaur des 2 registres
ret
/********************************************************/
/* File Include fonctions */
/********************************************************/
/* for this file see task include a file in language AArch64 assembly */
.include "../includeARM64.inc"
</syntaxhighlight>
{{Output}}
<pre>
Empty queue.
Not empty queue.
Priority : 1 : Solve RC tasks
Priority : 2 : Tax return
Priority : 3 : Clear drains
Priority : 4 : Feed cat
Priority : 5 : Make tea
</pre>
=={{header|Action!}}==
The user must type in the monitor the following command after compilation and before running the program!<pre>SET EndProg=*</pre>
{{libheader|Action! Tool Kit}}
<syntaxhighlight lang="action!">CARD EndProg ;required for ALLOCATE.ACT
INCLUDE "D2:ALLOCATE.ACT" ;from the Action! Tool Kit. You must type 'SET EndProg=*' from the monitor after compiling, but before running this program!
DEFINE PTR="CARD"
DEFINE NODE_SIZE="5"
TYPE QueueNode=[
BYTE priority
PTR data ;CHAR ARRAY
PTR nxt]
QueueNode POINTER queueFront,queueRear
BYTE FUNC IsEmpty()
IF queueFront=0 THEN
RETURN (1)
FI
RETURN (0)
PROC Push(BYTE p CHAR ARRAY d)
QueueNode POINTER node,curr,prev
node=Alloc(NODE_SIZE)
node.priority=p
node.data=d
node.nxt=0
IF IsEmpty() THEN
queueFront=node
queueRear=node
RETURN
FI
curr=queueFront
prev=0
WHILE curr#0 AND curr.priority<=p
DO
prev=curr
curr=curr.nxt
OD
IF prev=0 THEN
queueFront=node
ELSEIF curr=0 THEN
queueRear.nxt=node
queueRear=node
ELSE
prev.nxt=node
FI
node.nxt=curr
RETURN
PTR FUNC Pop()
QueueNode POINTER node
IF IsEmpty() THEN
PrintE("Error: queue is empty!")
Break()
FI
node=queueFront
queueFront=node.nxt
RETURN (node)
PROC TestIsEmpty()
IF IsEmpty() THEN
PrintE("Queue is empty")
ELSE
PrintE("Queue is not empty")
FI
RETURN
PROC TestPush(BYTE p CHAR ARRAY d)
PrintF("Push priority=%B task=%S%E",p,d)
Push(p,d)
RETURN
PROC TestPop()
QueueNode POINTER node
node=Pop()
PrintF("Pop priority=%B task=%S%E",node.priority,node.data)
Free(node,NODE_SIZE)
RETURN
PROC Main()
AllocInit(0)
queueFront=0
queueRear=0
Put(125) PutE() ;clear screen
TestIsEmpty()
TestPush(3,"Clear drains")
TestPush(4,"Feed cat")
TestPush(5,"Make tea")
TestPush(1,"Solve RC tasks")
TestPush(2,"Tax return")
TestIsEmpty()
TestPop()
TestPop()
TestPop()
TestPop()
TestPop()
TestIsEmpty()
RETURN</syntaxhighlight>
{{out}}
[https://gitlab.com/amarok8bit/action-rosetta-code/-/raw/master/images/Priority_queue.png Screenshot from Atari 8-bit computer]
<pre>
Queue is empty
Push priority=3 task=Clear drains
Push priority=4 task=Feed cat
Push priority=5 task=Make tea
Push priority=1 task=Solve RC tasks
Push priority=2 task=Tax return
Queue is not empty
Pop priority=1 task=Solve RC tasks
Pop priority=2 task=Tax return
Pop priority=3 task=Clear drains
Pop priority=4 task=Feed cat
Pop priority=5 task=Make tea
Queue is empty
</pre>
=={{header|Ada}}==
Line 22 ⟶ 564:
Ada 2012 includes container classes for priority queues.
<
with Ada.Containers.Unbounded_Priority_Queues;
with Ada.Strings.Unbounded;
with Ada.Text_IO;
procedure Priority_Queues is
Line 63 ⟶ 606:
end loop;
end;
end Priority_Queues;</
{{out}}
<
5 => Make tea
4 => Feed cat
3 => Clear drains
2 => Tax return
1 => Solve RC tasks
</pre>
=={{header|ARM Assembly}}==
{{works with|as|Raspberry Pi}}
<syntaxhighlight lang="arm assembly">
/* ARM assembly Raspberry PI */
/* program priorqueue.s */
Line 495 ⟶ 1,044:
pop {r2-r4}
bx lr @ return
</syntaxhighlight>
{{out}}
<pre>
Line 505 ⟶ 1,054:
Priority : 4 : Feed cat
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}}==
I am treating more positive numbers as higher in priority, because that way the list of "Tasks" comes out in a plausible order. It is simple to reverse that order. (In fact, the direction of priorities could easily be made configurable by the template mechanism.)
Any value of type '''int''' may be used as a priority number.
<syntaxhighlight lang="ats">
(* NOTE: Others are treating more negative numbers as the higher
priority, but I think it is pretty clear that making tea and
feeding the cat are higher in priority than solving RC tasks.
So I treat more positive numbers as higher priority.
But see a note below on how easy it is to reverse that. *)
#include "share/atspre_staload.hats"
staload UN = "prelude/SATS/unsafe.sats"
(* For the sake of the task, use a heap implementation that comes with
the ATS distribution. *)
staload H = "libats/ATS1/SATS/funheap_binomial.sats"
(* #include instead of anonymous staload, to work around an
inconvenience in the distributed code: funheap_is_empty and
funheap_isnot_empty are functions rather than template
functions. One could instead compile funheap_binomial.dats
separately. Or one could copy and modify the distributed code to
one's own taste. (The heap code is GPL-3+) *)
#include "libats/ATS1/DATS/funheap_binomial.dats"
#define NIL list_nil ()
#define :: list_cons
abstype pqueue (a : t@ype+) = ptr
extern fn {}
pqueue_make_empty :
{a : t@ype}
() -<> pqueue a
extern fn {}
pqueue_is_empty :
{a : t@ype}
pqueue (INV(a)) -<> [b : bool] bool
extern fn {}
pqueue_isnot_empty :
{a : t@ype}
pqueue (INV(a)) -<> [b : bool] bool
extern fn {a : t@ype}
pqueue_size :
pqueue (INV(a)) -<> [n : nat] size_t n
extern fn {a : t@ype}
pqueue_insert :
(&pqueue (INV(a)) >> _, int, a) -< !wrt > void
extern fn {a : t@ype}
pqueue_delete :
(&pqueue (INV(a)) >> _) -< !wrt > Option a
extern fn {a : t@ype}
pqueue_peek :
(pqueue (INV(a))) -< !wrt > Option a
extern fn {a : t@ype}
pqueue_merge :
(pqueue (INV(a)), pqueue a) -< !wrt > pqueue a
local
typedef heap_elt (a : t@ype+) =
'{
(* The "priority" field must come first. We take advantage of
the layout of a '{..} being that of a C struct. *)
priority = int,
value = a
}
fn {a : t@ype}
heap_elt_get_priority (elt : heap_elt a)
:<> int =
let
typedef prio_t = '{ priority = int }
val prio = $UN.cast{prio_t} elt
in
prio.priority
end
extern castfn
pqueue2heap :
{a : t@ype}
pqueue a -<> $H.heap (heap_elt a)
extern castfn
heap2pqueue :
{a : t@ype}
$H.heap (heap_elt a) -<> pqueue a
macdef p2h = pqueue2heap
macdef h2p = heap2pqueue
macdef comparison_cloref =
lam (x, y) =<cloref>
let
val px = heap_elt_get_priority x
and py = heap_elt_get_priority y
in
(* NOTE: Reverse the order of the arguments, if you want more
negative numbers to represent higher priorities. *)
compare (py, px)
end
fn {a : t@ype}
funheap_getmin_opt (heap : $H.heap (INV(a)),
cmp : $H.cmp a)
:<!wrt> Option_vt a =
let
var result : a?
val success = $H.funheap_getmin<a> (heap, cmp, result)
in
if success then
let
prval () = opt_unsome{a} result
in
Some_vt{a} result
end
else
let
prval () = opt_unnone{a} result
in
None_vt{a} ()
end
end
in
implement {}
pqueue_make_empty {a} () =
h2p{a} ($H.funheap_make_nil {heap_elt a} ())
implement {}
pqueue_is_empty {a} pq =
$H.funheap_is_empty {heap_elt a} (p2h{a} pq)
implement {}
pqueue_isnot_empty {a} pq =
$H.funheap_isnot_empty {heap_elt a} (p2h{a} pq)
implement {a}
pqueue_size pq =
$H.funheap_size<heap_elt a> (p2h{a} pq)
implement {a}
pqueue_insert (pq, priority, x) =
let
val elt =
'{
priority = priority,
value = x
} : heap_elt a
and compare = comparison_cloref
var heap = p2h{a} pq
val () = $H.funheap_insert (heap, elt, compare)
in
pq := h2p{a} heap
end
implement {a}
pqueue_delete pq =
let
typedef t = heap_elt a
val compare = comparison_cloref
var heap = p2h{a} pq
val elt_opt = $H.funheap_delmin_opt<heap_elt a> (heap, compare)
in
pq := h2p{a} heap;
case+ elt_opt of
| ~ Some_vt elt => Some (elt.value)
| ~ None_vt () => None ()
end
implement {a}
pqueue_peek pq =
let
typedef t = heap_elt a
val compare = comparison_cloref
and heap = p2h{a} pq
val elt_opt = funheap_getmin_opt<heap_elt a> (heap, compare)
in
case+ elt_opt of
| ~ Some_vt elt => Some (elt.value)
| ~ None_vt () => None ()
end
implement {a}
pqueue_merge (pq1, pq2) =
let
val heap1 = p2h{a} pq1
and heap2 = p2h{a} pq2
and compare = comparison_cloref
in
h2p{a} ($H.funheap_merge<heap_elt a> (heap1, heap2, compare))
end
overload iseqz with pqueue_is_empty
overload isneqz with pqueue_isnot_empty
overload size with pqueue_size
overload insert with pqueue_insert
overload delete with pqueue_delete
overload peek with pqueue_peek
overload merge with pqueue_merge
end
implement
main0 () =
let
var pq = pqueue_make_empty{string} ()
val () = print! (" ", iseqz pq)
val () = print! (" ", isneqz pq)
val () = print! (" ", "size:", size pq)
val () = insert (pq, 3, "3")
val () = insert (pq, 4, "4")
val () = insert (pq, 2, "2")
val () = insert (pq, 5, "5")
val () = insert (pq, 1, "1")
val () = print! (" ", iseqz pq)
val () = print! (" ", isneqz pq)
val () = print! (" ", "size:", size pq)
var pq2 = pqueue_make_empty{string} ()
val () = insert (pq, 6, "6")
val () = insert (pq, 4, "4a")
val () = pq := merge (pq, pq2)
val () = print! (" ", iseqz pq)
val () = print! (" ", isneqz pq)
val () = print! (" ", "size:", size pq)
val- Some x = peek pq
val () = print! (" ", x)
val- Some x = peek pq
val () = print! (" ", x)
val- Some x = peek pq
val () = print! (" ", x)
val- Some x = peek pq
val () = print! (" ", x)
val- Some x = delete pq
val () = print! (" ", x)
val- Some x = delete pq
val () = print! (" ", x)
val- Some x = peek pq
val () = print! (" ", x)
val- Some x = peek pq
val () = print! (" ", x)
val- Some x = delete pq
val () = print! (" ", x)
val- Some x = peek pq
val () = print! (" ", x)
val- Some x = peek pq
val () = print! (" ", x)
val- Some x = peek pq
val () = print! (" ", x)
val- Some x = peek pq
val () = print! (" ", x)
val- Some x = delete pq
val () = print! (" ", x)
val- Some x = delete pq
val () = print! (" ", x)
val- Some x = delete pq
val () = print! (" ", x)
val- Some x = delete pq
val () = print! (" ", x)
val- None () = delete pq
val () = println! ()
var pq2 = pqueue_make_empty{string} ()
val () = insert (pq2, 3, "Clear drains")
val () = insert (pq2, 4, "Feed cat")
val () = insert (pq2, 5, "Make tea")
val () = insert (pq2, 1, "Solve RC tasks")
val () = insert (pq2, 2, "Tax return")
val- Some x = delete pq2
val () = println! ("|", x, "|")
val- Some x = delete pq2
val () = println! ("|", x, "|")
val- Some x = delete pq2
val () = println! ("|", x, "|")
val- Some x = delete pq2
val () = println! ("|", x, "|")
val- Some x = delete pq2
val () = println! ("|", x, "|")
in
end
</syntaxhighlight>
{{out}}
<pre>$ patscc -O3 -DATS_MEMALLOC_GCBDW priority-queue.dats -lgc && ./a.out
true false size:0 false true size:5 false true size:7 6 6 6 6 6 5 4a 4a 4a 4 4 4 4 4 3 2 1
|Make tea|
|Feed cat|
|Clear drains|
|Tax return|
|Solve RC tasks|
</pre>
=={{header|AutoHotkey}}==
<
PQ_TopItem(Queue,Task:=""){ ; remove and return top priority item
TopPriority := PQ_TopPriority(Queue)
Line 567 ⟶ 1,485:
TopPriority := TopPriority?TopPriority:P , TopPriority := TopPriority<P?TopPriority:P
return, TopPriority
}</
Examples:<
(
3 Clear drains
Line 589 ⟶ 1,507:
MsgBox, 262208,, % (Task:="Feed cat") " priority = " PQ_Check(PQ,task)"`n`n" PQ_View(PQ)
^Esc::
ExitApp</
=={{header|Axiom}}==
Axiom already has a heap domain for ordered sets.
We define a domain for ordered key-entry pairs and then define a priority queue using the heap domain over the pairs:
<
OrderedKeyEntry(Key:OrderedSet,Entry:SetCategory): Exports == Implementation where
Exports == OrderedSet with
Line 620 ⟶ 1,538:
setelt(x:%,key:Key,entry:Entry) ==
insert!(construct(key,entry)$S,x)
entry</
pq(3):="Clear drains";
pq(4):="Feed cat";
Line 626 ⟶ 1,544:
pq(1):="Solve RC tasks";
pq(2):="Tax return";
[extract!(pq) for i in 1..#pq]</
{{out}}
<pre>
Line 632 ⟶ 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}}==
Batch has only a data structure, the environment that incidentally sorts itself automatically by key. The environment has a limit of 64K
<syntaxhighlight lang="batch file">
@echo off
setlocal enabledelayedexpansion
Line 664 ⟶ 1,676:
:next
set order= %order:~-3%
goto:eof</
{{out}}
<pre>
Line 676 ⟶ 1,688:
=={{header|C}}==
Using a dynamic array as a binary heap. Stores integer priority and a character pointer. Supports push and pop.
<
#include <stdlib.h>
Line 747 ⟶ 1,759:
return 0;
}
</syntaxhighlight>
{{output}}
<pre>Solve RC tasks
Line 756 ⟶ 1,768:
=== Pairing heap w/ generic data types ===
header file:
<syntaxhighlight lang="c">
typedef struct _pq_node_t {
long int key;
Line 775 ⟶ 1,787:
NEW_PQ_ELE(p, k); \
*(h) = heap_merge(((pq_node_t *) (p)), *(h))
</syntaxhighlight>
implementation:
<syntaxhighlight lang="c">
#include <stdlib.h>
#include "pairheap.h"
/* ---------------------------------------------------------------------------
* Pairing heap implementation
* --------------------------------------------------------------------------- */
static heap_t add_child(heap_t h, heap_t g) {
if (h->down != NULL)
h->down = g;
}
Line 791 ⟶ 1,807:
if (b == NULL) return a;
if (a->key < b->key) {
} else {
}
}
Line 804 ⟶ 1,820:
heap_t two_pass_merge(heap_t h) {
if (h == NULL || h->next == NULL)
else {
}
}
Line 818 ⟶ 1,834:
return two_pass_merge(h->down);
}
</syntaxhighlight>
usage:
<syntaxhighlight lang="c">
#include <stdio.h>
#include <string.h>
Line 851 ⟶ 1,867:
while (heap != NULL) {
}
}
</syntaxhighlight>
{{Out}}
<pre>
Line 868 ⟶ 1,884:
=={{header|C sharp}}==
===.NET 6 solution===
<syntaxhighlight lang="csharp">using System;
using System.Collections.Generic;
namespace PriorityQueueExample
{
class Program
{
static void Main(string[] args)
{
// Starting with .NET 6.0 preview 2 (released March 11th, 2021), there's a built-in priority queue
var p = new PriorityQueue<string, int>();
p.Enqueue("Clear drains", 3);
p.Enqueue("Feed cat", 4);
p.Enqueue("Make tea", 5);
p.Enqueue("Solve RC tasks", 1);
p.Enqueue("Tax return", 2);
while (p.TryDequeue(out string task, out int priority))
{
Console.WriteLine($"{priority}\t{task}");
}
}
}
}
/* Output:
1 Solve RC tasks
2 Tax return
3 Clear drains
4 Feed cat
5 Make tea
*/</syntaxhighlight>
===Pre-.NET 6 solution===
<syntaxhighlight lang="csharp">using System;
namespace PriorityQueue
Line 927 ⟶ 1,980:
}
}
}</
'''Min Heap Priority Queue'''
Line 933 ⟶ 1,986:
{{works with|C sharp|C#|3.0+/DotNet 3.5+}}
The above code is not really a true Priority Queue as it does not allow duplicate keys; also, the SortedList on which it is based does not have O(log n) insertions and removals for random data as a true Priority Queue does. The below code implements a true Min Heap Priority Queue:
<
using KeyT = UInt32;
using System;
Line 1,053 ⟶ 2,106:
return toSeq(fromSeq(sq)); }
}
}</
The above class code offers a full set of static methods and properties:
Line 1,075 ⟶ 2,128:
The above code can be tested as per the page specification by the following code:
<
Tuple<uint, string>[] ins = { new Tuple<uint,string>(3u, "Clear drains"),
new Tuple<uint,string>(4u, "Feed cat"),
Line 1,097 ⟶ 2,150:
foreach (var e in MinHeapPQ<string>.toSeq(MinHeapPQ<string>.adjust((k, v) => new Tuple<uint,string>(6u - k, v), npq)))
Console.WriteLine(e); Console.WriteLine();
}</
It tests building the queue the slow way using repeated "push"'s - O(n log n), the faster "fromSeq" (included in the "sort") - O(n), and also tests the "merge" and "adjust" methods.
Line 1,135 ⟶ 2,188:
The C++ standard library contains the <code>std::priority_queue</code> opaque data structure. It implements a max-heap.
<
#include <string>
#include <queue>
Line 1,154 ⟶ 2,207:
return 0;
}</
{{out}}
Line 1,168 ⟶ 2,221:
and use the heap operations to manipulate it:
<
#include <string>
#include <vector>
Line 1,197 ⟶ 2,250:
return 0;
}</
{{out}}
Line 1,210 ⟶ 2,263:
=={{header|Clojure}}==
<
; priority-map can be used as a priority queue
Line 1,228 ⟶ 2,281:
; Merge priority-maps together
user=> (into p [["Wax Car" 4]["Paint Fence" 1]["Sand Floor" 3]])
{"Solve RC tasks" 1, "Paint Fence" 1, "Clear drains" 3, "Sand Floor" 3, "Wax Car" 4, "Feed cat" 4, "Make tea" 5}</
=={{header|CLU}}==
This is a priority queue based on a binary heap. It uses CLU's dynamic
array to store the data.
There are no intrinsic limits on what kind of data can be used for the
priority or the values themselves, except that the priority datatype
must support the less-than operator.
<syntaxhighlight lang="clu">prio_queue = cluster [P, T: type] is new, empty, push, pop
where P has lt: proctype (P,P) returns (bool)
item = struct[prio: P, val: T]
rep = array[item]
new = proc () returns (cvt)
return (rep$create(0))
end new
empty = proc (pq: cvt) returns (bool)
return (rep$empty(pq))
end empty
parent = proc (k: int) returns (int)
return ((k-1)/2)
end parent
left = proc (k: int) returns (int)
return (2*k + 1)
end left
right = proc (k: int) returns (int)
return (2*k + 2)
end right
swap = proc (pq: rep, a: int, b: int)
temp: item := pq[a]
pq[a] := pq[b]
pq[b] := temp
end swap
min_heapify = proc (pq: rep, k: int)
l: int := left(k)
r: int := right(k)
smallest: int := k
if l < rep$size(pq) cand pq[l].prio < pq[smallest].prio then
smallest := l
end
if r < rep$size(pq) cand pq[r].prio < pq[smallest].prio then
smallest := r
end
if smallest ~= k then
swap(pq, k, smallest)
min_heapify(pq, smallest)
end
end min_heapify
push = proc (pq: cvt, prio: P, val: T)
rep$addh(pq, item${prio: prio, val: val})
i: int := rep$high(pq)
while i ~= 0 cand pq[i].prio < pq[parent(i)].prio do
swap(pq, i, parent(i))
i := parent(i)
end
end push
pop = proc (pq: cvt) returns (P, T) signals (empty)
if empty(up(pq)) then signal empty end
if rep$size(pq) = 1 then
i: item := rep$remh(pq)
return (i.prio, i.val)
end
root: item := pq[0]
pq[0] := rep$remh(pq)
min_heapify(pq, 0)
return (root.prio, root.val)
end pop
end prio_queue
start_up = proc ()
% use ints for priority and strings for data
prioq = prio_queue[int,string]
% make the priority queue
pq: prioq := prioq$new()
% add some tasks
prioq$push(pq, 3, "Clear drains")
prioq$push(pq, 4, "Feed cat")
prioq$push(pq, 5, "Make tea")
prioq$push(pq, 1, "Solve RC tasks")
prioq$push(pq, 2, "Tax return")
% print them all out in order
po: stream := stream$primary_output()
while ~prioq$empty(pq) do
prio: int task: string
prio, task := prioq$pop(pq)
stream$putl(po, int$unparse(prio) || ": " || task)
end
end start_up</syntaxhighlight>
{{out}}
<pre>1: Solve RC tasks
2: Tax return
3: Clear drains
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}}==
<
PriorityQueue = ->
# Use closure style for object creation (so no "new" required).
Line 1,310 ⟶ 2,786:
v = new_v
console.log "Final random element was #{v}"
</syntaxhighlight>
output
<syntaxhighlight lang="text">
> coffee priority_queue.coffee
Solve RC tasks
Line 1,323 ⟶ 2,799:
First random element was 0.00002744467929005623
Final random element was 0.9999718656763434
</syntaxhighlight>
=={{header|Common Lisp}}==
In this task were implemented to versions of the functions, the non-destructive ones that will not change the state of the priority queue and the destructive ones that will change. The destructive ones work very similarly to the 'pop' and 'push' functions.
<
;priority-queue's are implemented with association lists
(defun make-pq (alist)
Line 1,360 ⟶ 2,836:
(format t "~a~&" (remove-pq a))
(format t "~a~&" a)
</syntaxhighlight>
{{out}}
<pre>
Line 1,373 ⟶ 2,849:
=={{header|Component Pascal}}==
BlackBox Component Builder
<
MODULE PQueues;
IMPORT StdLog,Boxes;
Line 1,462 ⟶ 2,938:
END PQueues.
</syntaxhighlight>
Interface extracted from the implementation
<
DEFINITION PQueues;
Line 1,487 ⟶ 2,963:
END PQueues.
</syntaxhighlight>
Execute: ^Q PQueues.Test<br/>
Output:
Line 1,499 ⟶ 2,975:
=={{header|D}}==
<
void main() {
Line 1,513 ⟶ 2,989:
heap.removeFront();
}
}</
{{out}}
<pre>Tuple!(int,string)(5, "Make tea")
Line 1,520 ⟶ 2,996:
Tuple!(int,string)(2, "Tax return")
Tuple!(int,string)(1, "Solve RC tasks")</pre>
=={{header|Delphi}}==
{{libheader| System.SysUtils}}
{{libheader| Boost.Generics.Collection}}
Boost.Generics.Collection is part of [https://github.com/MaiconSoft/DelphiBoostLib DelphiBoostLib]
<syntaxhighlight lang="delphi">program Priority_queue;
{$APPTYPE CONSOLE}
uses
System.SysUtils, Boost.Generics.Collection;
var
Queue: TPriorityQueue<String>;
begin
Queue := TPriorityQueue<String>.Create(['Clear drains', 'Feed cat',
'Make tea', 'Solve RC tasks', 'Tax return'], [3, 4, 5, 1, 2]);
while not Queue.IsEmpty do
with Queue.DequeueEx do
Writeln(Priority, ', ', value);
end.</syntaxhighlight>
{{out}}
<pre>1, Solve RC tasks
2, Tax return
3, Clear drains
4, Feed cat
5, Make tea</pre>
=={{header|EchoLisp}}==
We use the built-in binary tree library. Each tree node has a datum (key . value). The functions (bin-tree-pop-first tree) and (bin-tree-pop-last tree) allow to extract the node with highest or lowest priority.
<
(lib 'tree)
(define tasks (make-bin-tree 3 "Clear drains"))
Line 1,542 ⟶ 3,046:
(bin-tree-pop-last tasks) → (4 . "Feed 🐡")
; etc.
</syntaxhighlight>
=={{header|Elixir}}==
{{trans|Erlang}}
<
def create, do: :gb_trees.empty
Line 1,575 ⟶ 3,079:
end
Priority.task</
{{out}}
Line 1,589 ⟶ 3,093:
=={{header|Erlang}}==
Using built in gb_trees module, with the suggested interface for this task.
<syntaxhighlight lang="erlang">
-module( priority_queue ).
Line 1,618 ⟶ 3,122:
io:fwrite( "top priority: ~p~n", [Element] ),
New_queue.
</syntaxhighlight>
{{out}}
<pre>
Line 1,638 ⟶ 3,142:
The following Binomial Heap Priority Queue code has been adapted [http://cs.hubfs.net/topic/None/56608 from a version by "DeeJay"] updated for changes in F# over the intervening years, and implementing the O(1) "peekMin" mentioned in that post; in addition to the above standard priority queue functions, it also implements the "merge" function for which the Binomial Heap is particularly suited, taking O(log n) time rather than the usual O(n) (or worse) time:
<
module PriorityQ =
Line 1,740 ⟶ 3,244:
let sort sq = sq |> fromSeq |> toSeq
let adjust f pq = pq |> toSeq |> Seq.map (fun (k, v) -> f k v) |> fromSeq</
"isEmpty", "empty", and "peekMin" all have O(1) performance, "push" is O(1) amortized performance with O(log n) worst case, and the rest are O(log n) except for "fromSeq" (and thus "sort" and "adjust") which have O(n log n) performance since they use repeated "deleteMin" with one per entry.
Line 1,753 ⟶ 3,257:
The following code implementing a Min Heap Priority Queue is adapted from the [http://www.cl.cam.ac.uk/~lp15/MLbook/programs/sample4.sml ML PRIORITY_QUEUE code by Lawrence C. Paulson] including separating the key/value pairs as separate entries in the data structure for better comparison efficiency; it implements an efficient "fromSeq" function using reheapify for which the Min Heap is particularly suited as it has only O(n) instead of O(n log n) computational time complexity, which method is also used for the "adjust" and "merge" functions:
<
module PriorityQ =
Line 1,885 ⟶ 3,389:
let toSeq pq = Seq.unfold popMin pq
let sort sq = sq |> fromSeq |> toSeq</
The above code implements a "merge" function so that no internal sequence generation is necessary as generation of sequence iterators is quite inefficient in F# for a combined O(n) computational time complexity but a considerable reduction in the constant factor overhead.
Line 1,896 ⟶ 3,400:
As the Min Heap is usually implemented as a [http://opendatastructures.org/versions/edition-0.1e/ods-java/10_1_BinaryHeap_Implicit_Bi.html mutable array binary heap] after a genealogical tree based model invented by [https://en.wikipedia.org/wiki/Michael_Eytzinger Michael Eytzinger] over 400 years ago, the following "ugly imperative" code implements the Min Heap Priority Queue this way; note that the code could be implemented not using "ugly" mutable state variables other than the contents of the array (DotNet List which implements a growable array) but in this case the code would be considerably slower as in not much faster or slower than the functional version since using mutable side effects greatly reduces the number of operations:
<
module PriorityQ =
Line 1,979 ⟶ 3,483:
let toSeq pq = Seq.unfold popMin pq
let sort sq = sq |> fromSeq |> toSeq</
The comments for the above code are the same as for the functional version; the main difference is that the imperative code takes about two thirds of the time on average.
All of the above codes can be tested under the F# REPL using the following:
<
(4u, "Feed cat");
(5u, "Make tea");
Line 2,002 ⟶ 3,506:
printfn ""
testpq |> MinHeap.adjust (fun k v -> uint32 (MinHeap.size testpq) - k, v)
|> MinHeap.toSeq |> Seq.iter (printfn "%A") // test adjust;;</
to produce the following output:
Line 2,048 ⟶ 3,552:
=={{header|Factor}}==
Factor has priority queues implemented in the library: documentation is available at http://docs.factorcode.org/content/article-heaps.html (or by typing "heaps" help interactively in the listener).
<
{ 3 "Clear drains" }
{ 4 "Feed cat" }
Line 2,057 ⟶ 3,561:
] [
[ print ] slurp-heap
] bi</
output:
<
Tax return
Clear drains
Feed cat
Make tea</
=={{header|Forth}}==
{{works with|gforth|0.7.3}}
<br>
<syntaxhighlight lang="forth">#! /usr/bin/gforth
\ Priority queue
10 CONSTANT INITIAL-CAPACITY
\ creates a new empty queue
: new-queue ( -- addr )
2 INITIAL-CAPACITY 3 * + cells allocate throw
INITIAL-CAPACITY over !
0 over cell + !
;
\ deletes a queue
: delete-queue ( addr -- )
free throw
;
: queue-capacity ( addr -- n )
@
;
\ the number of elements in the queue
: queue-size ( addr -- n )
cell + @
;
: resize-queue ( addr -- addr )
dup queue-capacity 2 * dup >r 3 * 2 + cells resize throw
r> over !
;
: ix->addr ( addr ix -- addr )
3 * 2 + cells +
;
: ix! ( p x y addr ix -- )
ix->addr
tuck 2 cells + !
tuck cell + !
!
;
: ix@ ( addr ix -- p x y )
ix->addr
dup @ swap
cell + dup @ swap
cell + @
;
: ix->priority ( addr ix -- p )
ix->addr @
;
: ix<->ix ( addr ix ix' -- )
-rot over swap ( ix' addr addr ix ) ( )
2over swap 2>r ( ix' addr addr ix ) ( addr ix' )
2dup ix@ 2>r >r ( ix' addr addr ix ) ( addr ix' x y p )
2>r ( ix' addr ) ( addr ix' x y p addr ix )
swap ix@ ( p' x' y' ) ( addr ix' x y p addr ix )
2r> ix! ( ) ( addr ix' x y p )
r> 2r> 2r> ix! ( ) ( )
;
: ix-parent ( ix -- ix' )
dup 0> IF
1- 2/
THEN
;
: ix-left-son ( ix -- ix' )
2* 1+
;
: ix-right-son ( ix -- ix' )
2* 2 +
;
: swap? ( addr ix ix' -- f )
rot >r ( ix ix' ) ( addr )
2dup ( ix ix' ix ix' ) ( addr )
r> tuck swap ( ix ix' ix addr addr ix' ) ( )
ix->priority >r ( ix ix' ix addr ) ( p' )
tuck swap ( ix ix' addr addr ix ) ( p' )
ix->priority r> ( ix ix' addr p p' ) ( )
> IF
-rot ix<->ix
true
ELSE
2drop drop
false
THEN
;
: ix? ( addr ix -- f )
swap queue-size <
;
: bubble-up ( addr ix -- )
2dup dup ix-parent swap ( addr ix addr ix' ix )
swap? IF ( addr ix )
ix-parent recurse
ELSE
2drop
THEN
;
: bubble-down ( addr ix -- )
2dup ix-right-son ix? IF
2dup ix-left-son ix->priority >r
2dup ix-right-son ix->priority r> < IF
2dup dup ix-right-son swap? IF
ix-right-son recurse
ELSE
2drop
THEN
ELSE
2dup dup ix-left-son swap? IF
ix-left-son recurse
ELSE
2drop
THEN
THEN
ELSE
2dup ix-left-son ix? IF
2dup dup ix-left-son swap? IF
ix-left-son recurse
ELSE
2drop
THEN
ELSE
2drop
THEN
THEN
;
\ enqueues an element with priority p and payload x y into queue addr
: >queue ( p x y addr -- addr )
dup queue-capacity over queue-size =
IF
resize-queue
THEN
dup >r
dup queue-size
ix!
r>
1 over cell + +!
dup dup queue-size 1- bubble-up
;
\ dequeues the element with highest priority
: queue> ( addr -- p x y )
dup queue-size 0= IF
1 throw
THEN
dup 0 ix@ 2>r >r dup >r
dup dup queue-size 1- ix@ r> 0 ix!
dup cell + -1 swap +!
0 bubble-down
r> 2r>
;
\ dequeues elements and prints them until the queue is empty
: drain-queue ( addr -- )
dup queue-size 0> IF
dup queue>
rot
. ." - " type cr
recurse
ELSE
drop
THEN
;
\ example
new-queue
>r 3 s" Clear drains" r> >queue
>r 4 s" Feed cat" r> >queue
>r 5 s" Make tea" r> >queue
>r 1 s" Solve RC tasks" r> >queue
>r 2 s" Tax return" r> >queue
drain-queue</syntaxhighlight>
{{out}}
<pre>
1 - Solve RC tasks
2 - Tax return
3 - Clear drains
4 - Feed cat
5 - Make tea
</pre>
=={{header|Fortran}}==
<
implicit none
Line 2,168 ⟶ 3,870:
! 2 -> Tax return
! 1 -> Solve RC tasks
</syntaxhighlight>
=={{header|Frink}}==
This uses Frink's ability to call arbitrary Java code and uses Java's PriorityQueue implementation, defining our own comparator function.
<syntaxhighlight lang="frink">pq = newJava["java.util.PriorityQueue", new Comparator[byColumn[0]]]
pq.add[[3, "Clear Drains"]]
pq.add[[4, "Feed cat"]]
pq.add[[5, "Make tea"]]
pq.add[[1, "Solve RC tasks"]]
pq.add[[2, "Tax return"]]
while ! pq.isEmpty[]
println[pq.poll[]]</syntaxhighlight>
{{out}}
<pre>
[1, Solve RC tasks]
[2, Tax return]
[3, Clear Drains]
[4, Feed cat]
[5, Make tea]
</pre>
=={{header|FunL}}==
<
native scala.collection.mutable.PriorityQueue
Line 2,192 ⟶ 3,915:
while not q.isEmpty()
println( q.dequeue() )</
{{out}}
Line 2,207 ⟶ 3,930:
Go's standard library contains the <code>container/heap</code> package, which which provides operations to operate as a heap any data structure that contains the <code>Push</code>, <code>Pop</code>, <code>Len</code>, <code>Less</code>, and <code>Swap</code> methods.
<
import (
Line 2,249 ⟶ 3,972:
fmt.Println(heap.Pop(pq))
}
}</
output:
Line 2,262 ⟶ 3,985:
=={{header|Groovy}}==
Groovy can use the built in java PriorityQueue class
<
@Canonical
Line 2,279 ⟶ 4,002:
while (!empty) { println remove() }
}</
Output:
Line 2,290 ⟶ 4,013:
=={{header|Haskell}}==
One of the best Haskell implementations of priority queues (of which there are many) is [http://hackage.haskell.org/package/pqueue pqueue], which implements a binomial heap.
<
main = print (toList (fromList [(3, "Clear drains"),(4, "Feed cat"),(5, "Make tea"),(1, "Solve RC tasks"), (2, "Tax return")]))</
Although Haskell's standard library does not have a dedicated priority queue structure, one can (for most purposes) use the built-in <code>Data.Set</code> data structure as a priority queue, as long as no two elements compare equal (since Set does not allow duplicate elements). This is the case here since no two tasks should have the same name. The complexity of all basic operations is still O(log n) although that includes the "elemAt 0" function to retrieve the first element of the ordered sequence if that were required; "fromList" takes O(n log n) and "toList" takes O(n) time complexity. Alternatively, a <code>Data.Map.Lazy</code> or <code>Data.Map.Strict</code> can be used in the same way with the same limitations.
<
main = print (S.toList (S.fromList [(3, "Clear drains"),(4, "Feed cat"),(5, "Make tea"),(1, "Solve RC tasks"), (2, "Tax return")]))</
{{out}}
<pre>[(1,"Solve RC tasks"),(2,"Tax return"),(3,"Clear drains"),(4,"Feed cat"),(5,"Make tea")]</pre>
Alternatively, a homemade min heap implementation:
<
deriving (Show, Eq)
Line 2,344 ⟶ 4,067:
(5, "Make tea"),
(1, "Solve RC tasks"),
(2, "Tax return")]</
The above code is a Priority Queue but isn't a [https://en.wikipedia.org/wiki/Binary_heap Min Heap based on a Binary Heap] for the following reasons: 1) it does not preserve the standard tree structure of the binary heap and 2) the tree balancing can be completely destroyed by some combinations of "pop" operations. The following code is a true purely functional Min Heap implementation and as well implements the extra optional features of Min Heap's that it can build a new Min Heap from a list in O(n) amortized time rather than the O(n log n) amortized time (for a large number of randomly ordered entries) by simply using repeated "push" operations; as well as the standard "push", "peek", "delete" and "pop" (combines the previous two). As well as the "fromList", "toList", and "sort" functions (the last combines the first two), it also has an "isEmpty" function to test for the empty queue, an "adjust" function that applies a function to every entry in the queue and reheapifies in O(n) amortized time and also the "replaceMin" function which is about twice as fast on the average as combined "delete" followed by "push" operations:
<
| MinHeapLeaf !kv
| MinHeapNode !kv {-# UNPACK #-} !Int !(MinHeap a) !(MinHeap a)
Line 2,470 ⟶ 4,193:
sortPQ :: (Ord kv) => [kv] -> [kv]
sortPQ ls = toListPQ $ fromListPQ ls</
If one is willing to forgo the fast O(1) "size" function and to give up strict conformance to the Heap tree structure (where rather than building each new level until each left node is full to that level before increasing level to the right, a new level is built by promoting leaves to branches only containing left leaves until all branches have left leaves before filling any right leaves of that level) although having even better tree balancing and therefore at least as high efficiency, one can use the following code adapted from the [http://www.cl.cam.ac.uk/~lp15/MLbook/programs/sample4.sml ''ML'' PRIORITY_QUEUE code by Lawrence C. Paulson] including separating the key/value pairs as separate entries in the data structure for better comparison efficiency; as noted in the code comments, a "size" function to output the number of elements in the queue (fairly quickly in O((log n)^2)), an "adjust" function to apply a function to all elements and reheapify in O(n) time, and a "merge" function to merge two queues has been added to the ML code:
<
| Br !k v !(PriorityQ k v) !(PriorityQ k v)
deriving (Eq, Ord, Read, Show)
Line 2,576 ⟶ 4,299:
sortPQ :: (Ord k) => [(k, v)] -> [(k, v)]
sortPQ ls = toListPQ $ fromListPQ ls</
The above codes compile but do not run with GHC Haskell version 7.8.3 using the LLVM back end with LLVM version 3.4 and full optimization turned on under Windows 32; they were tested under Windows 64 and 32 using the Native Code Generator back end with full optimization. With GHC Haskell version 7.10.1 they compile and run with or without LLVM 3.5.1 for 32-bit Windows (64-bit GHC Haskell under Windows does not run with LLVM for version 7.10.1), with a slight execution speed advantage to using LLVM.
Line 2,585 ⟶ 4,308:
The above codes when tested with the following "main" function (with a slight modification for the first test when the combined kv entry is used):
<
(4, "Feed cat"),
(5, "Make tea"),
Line 2,602 ⟶ 4,325:
mapM_ print $ toListPQ $ mergePQ testPQ testPQ
putStrLn "" -- test adjust
mapM_ print $ toListPQ $ adjustPQ (\x y -> (x * (-1), y)) testPQ</
has the output as follows:
Line 2,648 ⟶ 4,371:
<tt>Closure</tt> is used to allow the queue to order lists based on
their first element. The solution only works in Unicon.
<
import Collections # For Heap (dense priority queue) class
Line 2,661 ⟶ 4,384:
while task := pq.get() do write(task[1]," -> ",task[2])
end
</syntaxhighlight>
Output when run:
<pre>
Line 2,675 ⟶ 4,398:
Implementation:
<
PRI=: ''
Line 2,697 ⟶ 4,420:
QUE=: y}.QUE
r
)</
Efficiency is obtained by batching requests. Size of batch for insert is determined by size of arguments. Size of batch for topN is its right argument.
Line 2,703 ⟶ 4,426:
Example:
<
3 4 5 1 2 insert__Q 'clear drains';'feed cat';'make tea';'solve rc task';'tax return'
>topN__Q 1
Line 2,711 ⟶ 4,434:
clear drains
tax return
solve rc task</
=={{header|Java}}==
Java has a <code>PriorityQueue</code> class. It requires either the elements implement <code>Comparable</code>, or you give it a custom <code>Comparator</code> to compare the elements.
<
class Task implements Comparable<Task> {
Line 2,746 ⟶ 4,469:
System.out.println(pq.remove());
}
}</
{{out}}
<pre>
Line 2,761 ⟶ 4,484:
The special key "priorities" is used to store the priorities in a sorted array. Since "sort" is fast we will use that rather than optimizing insertion in the priorities array.
We assume that if an item of a given priority is already in the priority queue, there is no need to add it again.<
# Add an item with the given priority (an integer,
Line 2,810 ⟶ 4,533:
def prioritize:
. as $list | {} | pq_add_tasks($list) | pq_pop_tasks ;
</syntaxhighlight>
The specific task:
<syntaxhighlight lang="jq">
[ [3, "Clear drains"],
[4, "Feed cat"],
Line 2,819 ⟶ 4,542:
[2, "Tax return"]
] | prioritize
</syntaxhighlight>
{{Out}}
"Solve RC tasks"
Line 2,829 ⟶ 4,552:
=={{header|Julia}}==
Julia has built-in support for priority queues, though the <code>PriorityQueue</code> type is not exported by default. Priority queues are a specialization of the <code>Dictionary</code> type having ordered values, which serve as the priority. In addition to all of the methods of standard dictionaries, priority queues support: <code>enqueue!</code>, which adds an item to the queue, <code>dequeue!</code> which removes the lowest priority item from the queue, returning its key, and <code>peek</code>, which returns the (key, priority) of the lowest priority entry in the queue. The ordering behavior of the queue, which by default is its value sort order (typically low to high), can be set by passing an order directive to its constructor. For this task, <code>Base.Order.Reverse</code> is used to set-up the <code>task</code> queue to return tasks from high to low priority.
<syntaxhighlight lang="julia">
using Base.Collections
Line 2,848 ⟶ 4,571:
dequeue!(task)
println(" \"", t, "\" has priority ", p)
end</
{{out}}
Line 2,861 ⟶ 4,584:
=={{header|Kotlin}}==
{{trans|Java}}
<
internal data class Task(val priority: Int, val name: String) : Comparable<Task> {
Line 2,880 ⟶ 4,603:
"Tax return" priority 2))
while (q.any()) println(q.remove())
}</
{{out}}
<pre>Task(priority=1, name=Solve RC tasks)
Line 2,889 ⟶ 4,612:
=={{header|Lasso}}==
<
data
store = map,
Line 2,947 ⟶ 4,670:
while(not #test->isEmpty) => {
stdout(#test->pop)
}</
{{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 2,956 ⟶ 4,735:
This implementation uses a table with priorities as keys and queues as values. Queues for each priority are created when putting items as needed and are shrunk as necessary when popping items and removed when they are empty. Instead of using a plain array table for each queue, the technique shown in the Lua implementation from the [[Queue/Definition#Lua | Queue]] task is used. This avoids having to use <code>table.remove(t, 1)</code> to get and remove the first queue element, which is rather slow for big tables.
<
__index = {
put = function(self, p, v)
Line 3,005 ⟶ 4,784:
for prio, task in pq.pop, pq do
print(string.format("Popped: %d - %s", prio, task))
end</
'''Output:'''
Line 3,022 ⟶ 4,801:
The implementation is faster than the Python implementations below using <code>queue.PriorityQueue</code> or <code>heapq</code>, even when comparing the standard Lua implementation against [[PyPy]] and millions of tasks are added to the queue. With LuaJIT it is yet faster. The following code measures the time needed to add 10<sup>7</sup> tasks with a random priority between 1 and 1000 and to retrieve them from the queue again in order.
<
-- since it has millisecond precision on most systems
local socket = require("socket")
Line 3,061 ⟶ 4,840:
end
print(string.format("Elapsed: %.3f ms.", (socket.gettime() - start) * 1000))</
=={{header|M2000 Interpreter}}==
Line 3,067 ⟶ 4,846:
===Using unordered array===
<syntaxhighlight lang="m2000 interpreter">
Module UnOrderedArray {
Class PriorityQueue {
Line 3,076 ⟶ 4,855:
Module Reduce {
if .many<.first*2 then exit
}
Public:
Module Clear {
Dim .Item() \\ erase all
.many<=0 \\ default
.Level<=0
}
Module Add {
Dim .Item(.many*2)
.many*=2
Read Item
.Item(0)=Item
.Item(.level)=Item
swap .Item(0), .Item(.level)
.Item(.level)=Item
end if
.level++
}
Function Peek {
=.Item(0)
}
Function Poll {
=.Item(0)
swap .Item(0), .Item(1)
.Item(1)=0
.Level<=1
.Level--
Swap .Item(.level), .Item(0)
.Item(.level)=0
.level<=0 : .Item(0)=0
end if
.Reduce
}
Module Remove {
Read Item
k=true
Item=.Poll()
K~ \\ k=false
I2=.Level-1
.Item(I2)=0
k=false
end if
next
.Level--
.Reduce
}
Function Size {
=.Level
}
Class:
Module PriorityQueue {
if .many>0 then Error "Clear List First"
Read .many, .cmp
.first<=.many
Dim .Item(.many)
}
}
Class Item { X, S$
Class: // constructor as temporary definition
Module Item {Read .X, .S$}
}
Queue=PriorityQueue(100, Lambda -> {Read A,B : =Compare(A.X,B.X)})
Queue.Add Item(3, "Clear drains") : Gosub PrintTop()
Queue.Add Item(4 ,"Feed cat") : PrintTop()
Queue.Add Item(1 ,"Solve RC tasks") : PrintTop()
Queue
Print "remove items"
While true
MM=Queue.Poll() :Print MM.X, MM.S$,,"Size="; Queue.Size()
End While
End Sub
}
UnOrderedArray
</syntaxhighlight>
===Using a stack with arrays as elements===
Every insertion push item using binary search in proper position. Pop is very fast. Cons() used for demo purposes, make a new array from a series of arrays (a=cons(a,a) add to a an a . Variable a is a pointer to array (a tuple)
<syntaxhighlight lang="m2000 interpreter">
Module PriorityQueue {
a= (
a=cons(a, ((1 ,"Solve RC tasks"), ( 2 , "Tax return")))
b=stack
comp=lambda (a, b) ->
module InsertPQ (a, n, &comp) {
if len(a)=0 then stack a {data n} : exit
Line 3,202 ⟶ 4,980:
t=2: b=len(a)
m=b
while t<=b
t1=m
m=(b+t) div 2
Line 3,209 ⟶ 4,987:
b=m-1
m=b
if m>1 then shiftback m
}
Line 3,215 ⟶ 4,993:
n=each(a)
while n
InsertPq b, array(n), &comp
n1=each(b)
while n1
m=stackitem(n1)
\\ Peek topitem (without popping)
\\ Pop item
Stack b {
Read old
}
Function Pop$(a) {
stack a {
Line 3,239 ⟶ 5,017:
}
}
while not
}
PriorityQueue
</syntaxhighlight>
===Using a stack with Groups as elements===
This is the same as previous but now we use a group (a user object for M2000). InsertPQ is the same as before. Lambda comp has change only. We didn't use pointers to groups. All groups here works as values, so when we get a peek we get a copy of group in top position. All members of a group may not values, so if we have a pointer to group then we get a copy of that pointer, but then we can make changes and that changes happen for the group which we get the copy.
<syntaxhighlight lang="m2000 interpreter">
// class definitions are global
// if there aren't defintions in a class
global countmany=0&
class obj {
property toString$ {
value (sp=8) {
link parent x, s$ to x, s$
value$=format$("{0::-5}"+string$(" ", sp)+"{1:20}", x, s$)
}
}
remove {
countmany--
}
class:
module obj (.x, .s$) {countmany++}
}
Module PriorityQueueForGroups {
Flush ' empty current stack
Data obj(3, "Clear drains"), obj(4 ,"Feed cat"), obj( 5 , "Make tea
Data obj( 1 ,"Solve RC tasks"), obj( 2 , "Tax return")
ObjectCount()
b=stack
InsertPQ(b) // top of stack is
Print "Using Peek to Examine Priority Queue"
n1=each(b)
while n1
Print @Peek$(n1)
end while
ObjectCount()
Header()
while not @isEmpty(b)
Print @Pop(b)=>tostring$
end while
ObjectCount()
// here are the subs/simple functions
// these are static parts of module
sub Header()
Print " Priority Task"
Print "========== ================"
end sub
sub ObjectCount()
Print "There are ";countmany;" objects of type obj"
end sub
sub InsertPQ(a, n)
Print "Insert:";n.tostring$(1)
if len(a)=0 then stack a {data n} : exit sub
if @comp(n, stackitem(a)) then stack a {push n} : exit sub
stack a {
push n
local t=2
local m=b
m=(b+t) div 2
if m=0 then m=t1 : exit
If @comp(stackitem(m),n) then t=m+1: continue
b=m-1
m=b
if m>1 then shiftback m
}
end sub
function comp(a, b)
=a.x<b.x
end function
function Peek$(a as stack)
=stackitem(a)=>toString$
countmany++
end function
function IsEmpty(a)
=len(a)=0
end function
Function Pop(a)
// Group make a copy
stack a {=Group:countmany++}
end function
}
PriorityQueueForGroups
</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">
global countmany=0&
class obj {
x, s$
property toString$ {
value (sp=8) {
link parent x, s$ to x, s$
value$=format$("{0::-5}"+string$(" ", sp)+"{1:20}", x, s$)
}
}
z=this
=pointer((z))
}
remove
}
class:
module obj (.x, .s$) {countmany++}
}
// obj() return object as value (using a special pointer)
function global g(priority, task$) {
// here we return an object using nonrmal pointer
// try to change -> to = to see the error
->obj(priority, task$)
}
Module PriorityQueueForGroups {
Flush ' empty current stack
Data g(3, "Clear drains"),g(4 ,"Feed cat"), g( 5 , "Make tea")
Data g( 1 ,"Solve RC tasks")
ObjectCount()
pq=stack
zz=stack
while not empty
InsertPQ(pq) // top of stack is pq 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
}
InsertPq(pq, g(1 ,"Solve RC
Print "Using Peek to Examine Priority Queue"
n1=each(pq,-1,
while n1
Print @Peek$(stackitem(n1))
end while
ObjectCount()
Header()
while not @isEmpty(pq)
Print @Pop(pq)=>tostring$
end while
ObjectCount()
Header()
while not @isEmpty(zz)
Print @Pop(zz)=>tostring$
end while
ObjectCount()
// here are the subs/simple functions
// these are static parts of module
sub Header()
Print " Priority Task"
Print "========== ================"
end sub
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)
Print "Insert:";n=>tostring$(1)
if len(a)=0 then stack a {data n} : exit sub
if @comp(n, stackitem(a)) then stack a {push n} : exit sub
stack a {
push n
local t=2, pq=len(a), t1=0
local m=pq
while t<=pq
t1=m
m=(pq+t) div 2
if m=0 then m=t1 : exit
If @comp(stackitem(m),n) then t=m+1: continue
pq=m-1
m=pq
end while
if m>1 then shiftback m
}
end sub
function comp(a as *obj, pq as *obj)
=a=>x>pq=>x
end function
function Peek$(a as *obj)
=a=>toString$
end function
function IsEmpty(a)
=len(a)=0
end function
function Pop(a)
// Group make a copy (but here is a pointer of group)
stack a {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}}==
<
queue = SortBy[Append[queue, {priority, item}], First], HoldFirst];
pop = Function[queue,
Line 3,325 ⟶ 5,395:
If[Length@queue == 0, Null, Max[queue[[All, 1]]]], HoldFirst];
merge = Function[{queue1, queue2},
SortBy[Join[queue1, queue2], First], HoldAll];</
Example:
<
push[queue, 3, "Clear drains"];
push[queue, 4, "Feed cat"];
Line 3,339 ⟶ 5,409:
queue1 = {};
push[queue1, 6, "Drink tea"];
Print[merge[queue, queue1]];</
Output:
Line 3,350 ⟶ 5,420:
=={{header|Maxima}}==
<
The key may be any number (integer or not). Items are extracted in FIFO order. */
Line 3,431 ⟶ 5,501:
"call friends"
"serve cider"
"savour !"</
=={{header|Mercury}}==
Mercury comes with an efficient, albeit simple, priority queue in its standard library. The build_pqueue/2 predicate in the code below inserts the test data in arbitrary order. display_pqueue/3, in turn, removes one K/V pair at a time, displaying the value. Compiling and running the supplied program results in all tasks being displayed in priority order as expected.
<
:- interface.
Line 3,470 ⟶ 5,540:
main(!IO) :-
build_pqueue(pqueue.init, PQO),
display_pqueue(PQO, !IO).</
=={{header|Nim}}==
{{trans|C}}
<
PriElem[T] = tuple
data: T
Line 3,533 ⟶ 5,603:
while p.count > 0:
echo p.pop()</
{{out}}
<pre>(data: Solve RC tasks, pri: 1)
Line 3,542 ⟶ 5,612:
''' Using Nim HeapQueue'''
<
var pq = newHeapQueue[(int, string)]()
Line 3,553 ⟶ 5,623:
while pq.len() > 0:
echo pq.pop()</
{{out}}
Line 3,563 ⟶ 5,633:
''' Using Nim tables'''
<
var
Line 3,580 ⟶ 5,650:
pq.del(i)
main()</
{{out}}
<pre>1: Solve RC tasks
Line 3,592 ⟶ 5,662:
The priority queue used in this example is not actually written in Objective-C. It is part of Apple's (C-based) Core Foundation library, which is included with in Cocoa on Mac OS X and iOS. Its interface is a C function interface, which makes the code very ugly. Core Foundation is not included in GNUStep or other Objective-C APIs.
<
const void *PQRetain(CFAllocatorRef allocator, const void *ptr) {
Line 3,655 ⟶ 5,725:
}
return 0;
}</
log:
Line 3,670 ⟶ 5,740:
Holger Arnold's [http://holgerarnold.net/software/ OCaml base library] provides a [http://holgerarnold.net/software/ocaml/doc/base/PriorityQueue.html PriorityQueue] module.
<
let () =
Line 3,686 ⟶ 5,756:
PQ.remove_first pq;
print_endline task
done</
testing:
Line 3,698 ⟶ 5,768:
Although OCaml's standard library does not have a dedicated priority queue structure, one can (for most purposes) use the built-in Set data structure as a priority queue, as long as no two elements compare equal (since Set does not allow duplicate elements). This is the case here since no two tasks should have the same name. Note that Set is a functional, persistent data structure, so we derive new priority queues from the old ones functionally, rather than modifying them imperatively; the complexity is still O(log n).
{{works with|OCaml|4.02+}}
<
(struct
type t = int * string (* pair of priority and task name *)
Line 3,719 ⟶ 5,789:
aux (PQSet.remove task pq')
end
in aux pq</
{{out}}
<pre>
Line 3,727 ⟶ 5,797:
4, Feed cat
5, Make tea
</pre>
=={{header|OxygenBasic}}==
<syntaxhighlight lang="text">
'PRIORITY QUEUE WITH 16 LEVELS
uses console
% pl 16 'priority levels
===================
Class PriorityQueue
===================
indexbase 1
bstring buf[pl] 'buffers to hold priority queues content
int bg[pl] 'buffers base offset
int i[pl] 'indexers
int le[pl] 'length of buffer
method constructor()
====================
int p
for p=1 to pl
buf[p]=""
le[p]=0
bg[p]=0
i=[p]=0
next
end method
method destructor()
===================
int p
for p=1 to pl
del (buf[p])
le[p]=0
bg[p]=0
i=[p]=0
next
end method
method Encodelength(int ls,p)
=============================
int ll at i[p]+strptr(buf[p])
ll=ls
i[p]+=sizeof int
end method
method limit(int*p)
===================
if p>pl
p=pl
endif
if p<1
p=1
endif
end method
method push(string s,int p)
=============================
limit p
int ls
ls=len s
if i[p]+ls+8 > le[p] then
int e=8000+(ls*2) 'extra buffer bytes
buf[p]=buf[p]+nuls e 'extend buf
le[p]=len buf[p]
end if
EncodeLength ls,p 'length of input s
mid buf[p],i[p]+1,s 'patch in s
i[p]+=ls
end method
method popLength(int p) as int
==============================
if bg[p]>=i[p]
return -1 'buffer empty
endif
int ll at (bg[p]+strptr buf[p])
bg[p]+=sizeof int
return ll
end method
method pop(string *s, int *p=1, lpl=0) as int
=============================================
limit p
int ls
do
ls=popLength p
if ls=-1
if not lpl 'lpl: lock priority level
p++ 'try next priority level
if p<=pl
continue do
endif
endif
s=""
return ls 'empty buffers
endif
exit do
loop
s=mid buf[p],bg[p]+1,ls
bg[p]+=ls
'cleanup buffer
if bg[p]>1e6 then
buf[p]=mid buf[p],bg[p]+1 'remove old popped data
le[p]=len buf[p]
i[p]-=bg[p] 'shrink buf
bg[p]=0
end if
end method
method clear()
==============
constructor
end method
end class 'PriorityQueue
'====
'DEMO
'====
new PriorityQueue medo()
string s
def inp
medo.push %2,%1
end def
' Priority Task
' ══════════ ════════════════
inp 3 "Clear drains"
inp 4 "Feed cat"
inp 5 "Make tea"
inp 1 "Solve RC tasks"
inp 2 "Tax return"
inp 4 "Plant beans"
'
int er
int p
print "Priority Task" cr
print "=================" cr
do
er=medo.pop s,p
if er=-1
print "(buffer empty)"
exit do
endif
print p tab s cr
loop
pause
del medo
/*
RESULTS:
Priority Task
=================
1 Solve RC tasks
2 Tax return
3 Clear drains
4 Feed cat
4 Plant beans
5 Make tea
(buffer empty)
*/
</syntaxhighlight>
=={{header|Pascal}}==
<syntaxhighlight lang="pascal">
program PriorityQueueTest;
uses Classes;
Type
TItem = record
Priority:Integer;
Value:string;
end;
PItem = ^TItem;
TPriorityQueue = class(Tlist)
procedure Push(Priority:Integer;Value:string);
procedure SortPriority();
function Pop():String;
function Empty:Boolean;
end;
{ TPriorityQueue }
procedure TPriorityQueue.Push(Priority:Integer;Value:string);
var
Item: PItem;
begin
new(Item);
Item^.Priority := Priority;
Item^.Value := Value;
inherited Add(Item);
SortPriority();
end;
procedure TPriorityQueue.SortPriority();
var
i,j:Integer;
begin
if(Count < 2) Then Exit();
for i:= 0 to Count-2 do
for j:= i+1 to Count-1 do
if ( PItem(Items[i])^.Priority > PItem(Items[j])^.Priority)then
Exchange(i,j);
end;
function TPriorityQueue.Pop():String;
begin
if count = 0 then
Exit('');
result := PItem(First)^.value;
Dispose(PItem(First));
Delete(0);
end;
function TPriorityQueue.Empty:Boolean;
begin
Result := Count = 0;
end;
var
Queue : TPriorityQueue;
begin
Queue:= TPriorityQueue.Create();
Queue.Push(3,'Clear drains');
Queue.Push(4,'Feed cat');
Queue.Push(5,'Make tea');
Queue.Push(1,'Solve RC tasks');
Queue.Push(2,'Tax return');
while not Queue.Empty() do
writeln(Queue.Pop());
Queue.free;
end.
</syntaxhighlight>
====Advanced version====
{{works with|FPC}}
A maximizing priority queue based on a binary heap with the ability to update keys using a special handle. User is responsible for keeping track of when the handle becomes invalid. Comparing elements requires a regular boolean function of the form:
<syntaxhighlight lang="pascal">
type
TComparer<T> = function(const L, R: T): Boolean;
</syntaxhighlight>
which should return True if the first argument is less than the second. It seems that all operations should be performed in O(LogN).
<syntaxhighlight lang="pascal">
unit PQueue;
{$mode objfpc}{$h+}{$b-}
interface
uses
SysUtils;
type
EPqError = class(Exception);
generic TPriorityQueue<T> = class
public
type
TComparer = function(const L, R: T): Boolean;
THandle = type SizeInt;
const
NULL_HANDLE = THandle(-1);
strict private
type
TNode = record
Data: T;
HeapIndex: SizeInt;
end;
const
INIT_SIZE = 16;
NULL_INDEX = SizeInt(-1);
SEUndefComparer = 'Undefined comparer';
SEInvalidHandleFmt = 'Invalid handle value(%d)';
SEAccessEmpty = 'Cannot access an empty queue item';
var
FNodes: array of TNode;
FHeap: array of SizeInt;
FCount,
FStackTop: SizeInt;
FCompare: TComparer;
procedure CheckEmpty;
procedure Expand;
function NodeAdd(const aValue: T; aIndex: SizeInt): SizeInt;
function NodeRemove(aIndex: SizeInt): T;
function StackPop: SizeInt;
procedure StackPush(aIdx: SizeInt);
procedure PushUp(Idx: SizeInt);
procedure SiftDown(Idx: SizeInt);
function DoPop: T;
public
constructor Create(c: TComparer);
function IsEmpty: Boolean;
procedure Clear;
function Push(const v: T): THandle;
function Pop: T;
function TryPop(out v: T): Boolean;
function Peek: T;
function TryPeek(out v: T): Boolean;
function GetValue(h: THandle): T;
procedure Update(h: THandle; const v: T);
property Count: SizeInt read FCount;
end;
implementation
procedure TPriorityQueue.CheckEmpty;
begin
if Count = 0 then raise EPqError.Create(SEAccessEmpty);
end;
procedure TPriorityQueue.Expand;
begin
if Length(FHeap) < INIT_SIZE then begin
SetLength(FHeap, INIT_SIZE);
SetLength(FNodes, INIT_SIZE)
end
else begin
SetLength(FHeap, Length(FHeap) * 2);
SetLength(FNodes, Length(FNodes) * 2);
end;
end;
function TPriorityQueue.NodeAdd(const aValue: T; aIndex: SizeInt): SizeInt;
begin
if FStackTop <> NULL_INDEX then
Result := StackPop
else
Result := FCount;
FNodes[Result].Data := aValue;
FNodes[Result].HeapIndex := aIndex;
Inc(FCount);
end;
function TPriorityQueue.NodeRemove(aIndex: SizeInt): T;
begin
StackPush(aIndex);
Result := FNodes[aIndex].Data;
end;
function TPriorityQueue.StackPop: SizeInt;
begin
Result := FStackTop;
if Result <> NULL_INDEX then begin
FStackTop := FNodes[Result].HeapIndex;
FNodes[Result].HeapIndex := NULL_INDEX;
end;
end;
procedure TPriorityQueue.StackPush(aIdx: SizeInt);
begin
FNodes[aIdx].HeapIndex := FStackTop;
FStackTop := aIdx;
end;
procedure TPriorityQueue.PushUp(Idx: SizeInt);
var
Prev, Curr: SizeInt;
begin
Prev := (Idx - 1) shr 1;
Curr := FHeap[Idx];
while(Idx > 0) and FCompare(FNodes[FHeap[Prev]].Data, FNodes[Curr].Data) do begin
FHeap[Idx] := FHeap[Prev];
FNodes[FHeap[Prev]].HeapIndex := Idx;
Idx := Prev;
Prev := (Prev - 1) shr 1;
end;
FHeap[Idx] := Curr;
FNodes[Curr].HeapIndex := Idx;
end;
procedure TPriorityQueue.SiftDown(Idx: SizeInt);
var
Next, Sifted: SizeInt;
begin
if Count < 2 then exit;
Next := Idx*2 + 1;
Sifted := FHeap[Idx];
while Next < Count do begin
if(Next+1 < Count)and FCompare(FNodes[FHeap[Next]].Data, FNodes[FHeap[Next+1]].Data)then Inc(Next);
if not FCompare(FNodes[Sifted].Data, FNodes[FHeap[Next]].Data) then break;
FHeap[Idx] := FHeap[Next];
FNodes[FHeap[Next]].HeapIndex := Idx;
Idx := Next;
Next := Next*2 + 1;
end;
FHeap[Idx] := Sifted;
FNodes[Sifted].HeapIndex := Idx;
end;
function TPriorityQueue.DoPop: T;
begin
Result := NodeRemove(FHeap[0]);
Dec(FCount);
if Count > 0 then begin
FHeap[0] := FHeap[Count];
SiftDown(0);
end;
end;
constructor TPriorityQueue.Create(c: TComparer);
begin
if c = nil then raise EPqError.Create(SEUndefComparer);
FCompare := c;
FStackTop := NULL_INDEX;
end;
function TPriorityQueue.IsEmpty: Boolean;
begin
Result := Count = 0;
end;
procedure TPriorityQueue.Clear;
begin
FNodes := nil;
FHeap := nil;
FCount := 0;
FStackTop := NULL_INDEX;
end;
function TPriorityQueue.Push(const v: T): THandle;
var
InsertPos: SizeInt;
begin
if Count = Length(FHeap) then Expand;
InsertPos := Count;
Result := NodeAdd(v, InsertPos);
FHeap[InsertPos] := Result;
if InsertPos > 0 then PushUp(InsertPos);
end;
function TPriorityQueue.Pop: T;
begin
CheckEmpty;
Result := DoPop;
end;
function TPriorityQueue.TryPop(out v: T): Boolean;
begin
if Count = 0 then exit(False);
v := DoPop;
Result := True;
end;
function TPriorityQueue.Peek: T;
begin
CheckEmpty;
Result := FNodes[FHeap[0]].Data;
end;
function TPriorityQueue.TryPeek(out v: T): Boolean;
begin
if Count = 0 then exit(False);
v := FNodes[FHeap[0]].Data;
Result := True;
end;
function TPriorityQueue.GetValue(h: THandle): T;
begin
if SizeUInt(h) < SizeUInt(Length(FHeap)) then
Result := FNodes[h].Data
else
raise EPqError.CreateFmt(SEInvalidHandleFmt, [h]);
end;
procedure TPriorityQueue.Update(h: THandle; const v: T);
begin
if SizeUInt(h) < SizeUInt(Length(FHeap)) then begin
if FCompare(FNodes[h].Data, v) then begin
FNodes[h].Data := v;
PushUp(FNodes[h].HeapIndex);
end else
if FCompare(v, FNodes[h].Data) then begin
FNodes[h].Data := v;
SiftDown(FNodes[h].HeapIndex);
end;
end else
raise EPqError.CreateFmt(SEInvalidHandleFmt, [h]);
end;
end.
</syntaxhighlight>
Usage:
<syntaxhighlight lang="pascal">
program PqDemo;
{$mode delphi}
uses
SysUtils, PQueue;
type
TTask = record
Name: string; Prio: Integer;
end;
const
Tasks: array of TTask = [
(Name: 'Clear drains'; Prio: 3), (Name: 'Feed cat'; Prio: 4),
(Name: 'Make tea'; Prio: 5), (Name: 'Solve RC tasks'; Prio: 1),
(Name: 'Tax return'; Prio: 2)];
function TaskCmp(const L, R: TTask): Boolean;
begin
Result := L.Prio < R.Prio;
end;
var
q: TPriorityQueue<TTask>;
h: q.THandle = q.NULL_HANDLE;
t: TTask;
MaxPrio: Integer = Low(Integer);
begin
Randomize;
q := TPriorityQueue<TTask>.Create(@TaskCmp);
for t in Tasks do begin
if t.Prio > MaxPrio then MaxPrio := t.Prio;
if Pos('cat', t.Name) > 0 then
h := q.Push(t)
else
q.Push(t);
end;
if (h <> q.NULL_HANDLE) and Boolean(Random(2)) then begin
WriteLn('Cat is angry!');
t := q.GetValue(h);
t.Prio := Succ(MaxPrio);
q.Update(h, t);
end;
WriteLn('Task list:');
while q.TryPop(t) do
WriteLn(' ', t.Prio, ' ', t.Name);
q.Free;
end.
</syntaxhighlight>
{{out}}
<pre>
Cat is angry!
Task list:
6 Feed cat
5 Make tea
3 Clear drains
2 Tax return
1 Solve RC tasks
</pre>
=={{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]
<
use
use feature 'say';
use Heap::Priority;
my $h =
$h->highest_first(); # higher or lower number is more important
Line 3,744 ⟶ 6,366:
["Tax return", 2];
say while ($_ = $h->pop);</
{{out}}
<pre>
Make tea
Feed cat
Clear drains
Tax return
Solve RC tasks
</pre>
===IBM card sorter version===
<syntaxhighlight lang="perl">use strict;
use warnings; # in homage to IBM card sorters :)
Line 3,782 ⟶ 6,407:
delete $bins[-1] while @bins and @{ $bins[-1] // [] } == 0;
shift @{ $bins[-1] // [] };
}</
{{out}}
<pre>
Line 3,796 ⟶ 6,421:
Dictionary based solution. Allows duplicate tasks, FIFO within priority, and uses a callback-style method of performing tasks.<br>
Assumes 5 is the highest priority and should be done first, for 1 first just delete the ",true" on traverse_dict calls.
<!--<syntaxhighlight lang="phix">(phixonline)-->
<span style="color: #008080;">with</span> <span style="color: #008080;">javascript_semantics</span>
<span style="color: #008080;">constant</span> <span style="color: #000000;">tasklist</span> <span style="color: #0000FF;">=</span> <span style="color: #7060A8;">new_dict</span><span style="color: #0000FF;">()</span>
<span style="color: #008080;">procedure</span> <span style="color: #000000;">add_task</span><span style="color: #0000FF;">(</span><span style="color: #004080;">integer</span> <span style="color: #000000;">priority</span><span style="color: #0000FF;">,</span> <span style="color: #004080;">string</span> <span style="color: #000000;">desc</span><span style="color: #0000FF;">)</span>
<span style="color: #004080;">integer</span> <span style="color: #000000;">k</span> <span style="color: #0000FF;">=</span> <span style="color: #7060A8;">getd_index</span><span style="color: #0000FF;">(</span><span style="color: #000000;">priority</span><span style="color: #0000FF;">,</span><span style="color: #000000;">tasklist</span><span style="color: #0000FF;">)</span>
<span style="color: #008080;">if</span> <span style="color: #000000;">k</span><span style="color: #0000FF;">=</span><span style="color: #000000;">0</span> <span style="color: #008080;">then</span>
<span style="color: #7060A8;">putd</span><span style="color: #0000FF;">(</span><span style="color: #000000;">priority</span><span style="color: #0000FF;">,{</span><span style="color: #000000;">desc</span><span style="color: #0000FF;">},</span><span style="color: #000000;">tasklist</span><span style="color: #0000FF;">)</span>
<span style="color: #008080;">else</span>
<span style="color: #004080;">sequence</span> <span style="color: #000000;">descs</span> <span style="color: #0000FF;">=</span> <span style="color: #7060A8;">getd_by_index</span><span style="color: #0000FF;">(</span><span style="color: #000000;">k</span><span style="color: #0000FF;">,</span><span style="color: #000000;">tasklist</span><span style="color: #0000FF;">)</span>
<span style="color: #7060A8;">putd</span><span style="color: #0000FF;">(</span><span style="color: #000000;">priority</span><span style="color: #0000FF;">,</span><span style="color: #7060A8;">append</span><span style="color: #0000FF;">(</span><span style="color: #000000;">descs</span><span style="color: #0000FF;">,</span><span style="color: #000000;">desc</span><span style="color: #0000FF;">),</span><span style="color: #000000;">tasklist</span><span style="color: #0000FF;">)</span>
<span style="color: #008080;">end</span> <span style="color: #008080;">if</span>
<span style="color: #008080;">end</span> <span style="color: #008080;">procedure</span>
<span style="color: #008080;">function</span> <span style="color: #000000;">list_task_visitor</span><span style="color: #0000FF;">(</span><span style="color: #004080;">integer</span> <span style="color: #000000;">priority</span><span style="color: #0000FF;">,</span> <span style="color: #004080;">sequence</span> <span style="color: #000000;">descs</span><span style="color: #0000FF;">,</span> <span style="color: #004080;">integer</span> <span style="color: #000080;font-style:italic;">/*user_data*/</span><span style="color: #0000FF;">)</span>
<span style="color: #0000FF;">?{</span><span style="color: #000000;">priority</span><span style="color: #0000FF;">,</span><span style="color: #000000;">descs</span><span style="color: #0000FF;">}</span>
<span style="color: #008080;">return</span> <span style="color: #004600;">true</span> <span style="color: #000080;font-style:italic;">-- continue</span>
<span style="color: #008080;">end</span> <span style="color: #008080;">function</span>
<span style="color: #008080;">procedure</span> <span style="color: #000000;">list_tasks</span><span style="color: #0000FF;">()</span>
<span style="color: #7060A8;">traverse_dict</span><span style="color: #0000FF;">(</span><span style="color: #000000;">list_task_visitor</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">0</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">tasklist</span><span style="color: #0000FF;">,</span> <span style="color: #004600;">true</span><span style="color: #0000FF;">)</span>
<span style="color: #008080;">end</span> <span style="color: #008080;">procedure</span>
<span style="color: #008080;">function</span> <span style="color: #000000;">pop_task_visitor</span><span style="color: #0000FF;">(</span><span style="color: #004080;">integer</span> <span style="color: #000000;">priority</span><span style="color: #0000FF;">,</span> <span style="color: #004080;">sequence</span> <span style="color: #000000;">descs</span><span style="color: #0000FF;">,</span> <span style="color: #004080;">integer</span> <span style="color: #000000;">rid</span><span style="color: #0000FF;">)</span>
<span style="color: #004080;">string</span> <span style="color: #000000;">desc</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">descs</span><span style="color: #0000FF;">[</span><span style="color: #000000;">1</span><span style="color: #0000FF;">]</span>
<span style="color: #000000;">descs</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">descs</span><span style="color: #0000FF;">[</span><span style="color: #000000;">2</span><span style="color: #0000FF;">..$]</span>
<span style="color: #008080;">if</span> <span style="color: #7060A8;">length</span><span style="color: #0000FF;">(</span><span style="color: #000000;">descs</span><span style="color: #0000FF;">)=</span><span style="color: #000000;">0</span> <span style="color: #008080;">then</span>
<span style="color: #7060A8;">deld</span><span style="color: #0000FF;">(</span><span style="color: #000000;">priority</span><span style="color: #0000FF;">,</span><span style="color: #000000;">tasklist</span><span style="color: #0000FF;">)</span>
<span style="color: #008080;">else</span>
<span style="color: #7060A8;">putd</span><span style="color: #0000FF;">(</span><span style="color: #000000;">priority</span><span style="color: #0000FF;">,</span><span style="color: #000000;">descs</span><span style="color: #0000FF;">,</span><span style="color: #000000;">tasklist</span><span style="color: #0000FF;">)</span>
<span style="color: #008080;">end</span> <span style="color: #008080;">if</span>
<span style="color: #000000;">rid</span><span style="color: #0000FF;">(</span><span style="color: #000000;">priority</span><span style="color: #0000FF;">,</span><span style="color: #000000;">desc</span><span style="color: #0000FF;">)</span>
<span style="color: #008080;">return</span> <span style="color: #004600;">false</span> <span style="color: #000080;font-style:italic;">-- stop</span>
<span style="color: #008080;">end</span> <span style="color: #008080;">function</span>
<span style="color: #008080;">procedure</span> <span style="color: #000000;">pop_task</span><span style="color: #0000FF;">(</span><span style="color: #004080;">integer</span> <span style="color: #000000;">rid</span><span style="color: #0000FF;">)</span>
<span style="color: #008080;">if</span> <span style="color: #7060A8;">dict_size</span><span style="color: #0000FF;">(</span><span style="color: #000000;">tasklist</span><span style="color: #0000FF;">)!=</span><span style="color: #000000;">0</span> <span style="color: #008080;">then</span>
<span style="color: #7060A8;">traverse_dict</span><span style="color: #0000FF;">(</span><span style="color: #000000;">pop_task_visitor</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">rid</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">tasklist</span><span style="color: #0000FF;">,</span> <span style="color: #004600;">true</span><span style="color: #0000FF;">)</span>
<span style="color: #008080;">end</span> <span style="color: #008080;">if</span>
<span style="color: #008080;">end</span> <span style="color: #008080;">procedure</span>
<span style="color: #000000;">add_task</span><span style="color: #0000FF;">(</span><span style="color: #000000;">3</span><span style="color: #0000FF;">,</span><span style="color: #008000;">"Clear drains"</span><span style="color: #0000FF;">)</span>
<span style="color: #000000;">add_task</span><span style="color: #0000FF;">(</span><span style="color: #000000;">4</span><span style="color: #0000FF;">,</span><span style="color: #008000;">"Feed cat"</span><span style="color: #0000FF;">)</span>
<span style="color: #000000;">add_task</span><span style="color: #0000FF;">(</span><span style="color: #000000;">5</span><span style="color: #0000FF;">,</span><span style="color: #008000;">"Make tea"</span><span style="color: #0000FF;">)</span>
<span style="color: #000000;">add_task</span><span style="color: #0000FF;">(</span><span style="color: #000000;">1</span><span style="color: #0000FF;">,</span><span style="color: #008000;">"Solve RC tasks"</span><span style="color: #0000FF;">)</span>
<span style="color: #000000;">add_task</span><span style="color: #0000FF;">(</span><span style="color: #000000;">2</span><span style="color: #0000FF;">,</span><span style="color: #008000;">"Tax return"</span><span style="color: #0000FF;">)</span>
<span style="color: #008080;">procedure</span> <span style="color: #000000;">do_task</span><span style="color: #0000FF;">(</span><span style="color: #004080;">integer</span> <span style="color: #000000;">priority</span><span style="color: #0000FF;">,</span> <span style="color: #004080;">string</span> <span style="color: #000000;">desc</span><span style="color: #0000FF;">)</span>
<span style="color: #0000FF;">?{</span><span style="color: #000000;">priority</span><span style="color: #0000FF;">,</span><span style="color: #000000;">desc</span><span style="color: #0000FF;">}</span>
<span style="color: #008080;">end</span> <span style="color: #008080;">procedure</span>
<span style="color: #000000;">list_tasks</span><span style="color: #0000FF;">()</span>
<span style="color: #0000FF;">?</span><span style="color: #008000;">"==="</span>
<span style="color: #000000;">pop_task</span><span style="color: #0000FF;">(</span><span style="color: #000000;">do_task</span><span style="color: #0000FF;">)</span>
<span style="color: #0000FF;">?</span><span style="color: #008000;">"==="</span>
<span style="color: #000000;">list_tasks</span><span style="color: #0000FF;">()</span>
<!--</syntaxhighlight>-->
{{out}}
<pre>
Line 3,865 ⟶ 6,493:
{1,{"Solve RC tasks"}}
</pre>
=== trans nim ===
{{trans|Nim}}
(I needed this for [[Taxicab_numbers#Phix|Taxicab_numbers]])<br>
The bulk of this code now forms builtins/pqueue.e (not
<!--<syntaxhighlight lang="phix">(phixonline)-->
<span style="color: #008080;">with</span> <span style="color: #008080;">javascript_semantics</span>
<span style="color: #004080;">sequence</span> <span style="color: #000000;">pq</span> <span style="color: #0000FF;">=</span> <span style="color: #0000FF;">{}</span>
<span style="color: #008080;">constant</span> <span style="color: #000000;">PRIORITY</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">2</span>
<span style="color: #008080;">procedure</span> <span style="color: #000000;">pqAdd</span><span style="color: #0000FF;">(</span><span style="color: #004080;">sequence</span> <span style="color: #000000;">item</span><span style="color: #0000FF;">)</span>
<span style="color: #000080;font-style:italic;">-- item is {object data, object priority}</span>
<span style="color: #004080;">integer</span> <span style="color: #000000;">n</span> <span style="color: #0000FF;">=</span> <span style="color: #7060A8;">length</span><span style="color: #0000FF;">(</span><span style="color: #000000;">pq</span><span style="color: #0000FF;">)+</span><span style="color: #000000;">1</span><span style="color: #0000FF;">,</span>
<span style="color: #000000;">m</span> <span style="color: #0000FF;">=</span> <span style="color: #7060A8;">floor</span><span style="color: #0000FF;">(</span><span style="color: #000000;">n</span><span style="color: #0000FF;">/</span><span style="color: #000000;">2</span><span style="color: #0000FF;">)</span>
<span style="color: #000000;">pq</span> <span style="color: #0000FF;">&=</span> <span style="color: #000000;">0</span>
<span style="color: #000080;font-style:italic;">-- append at end, then up heap</span>
<span style="color: #008080;">while</span> <span style="color: #000000;">m</span><span style="color: #0000FF;">></span><span style="color: #000000;">0</span> <span style="color: #008080;">and</span> <span style="color: #000000;">item</span><span style="color: #0000FF;">[</span><span style="color: #000000;">PRIORITY</span><span style="color: #0000FF;">]<</span><span style="color: #000000;">pq</span><span style="color: #0000FF;">[</span><span style="color: #000000;">m</span><span style="color: #0000FF;">][</span><span style="color: #000000;">PRIORITY</span><span style="color: #0000FF;">]</span> <span style="color: #008080;">do</span>
<span style="color: #000000;">pq</span><span style="color: #0000FF;">[</span><span style="color: #000000;">n</span><span style="color: #0000FF;">]</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">pq</span><span style="color: #0000FF;">[</span><span style="color: #000000;">m</span><span style="color: #0000FF;">]</span>
<span style="color: #000000;">n</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">m</span>
<span style="color: #000000;">m</span> <span style="color: #0000FF;">=</span> <span style="color: #7060A8;">floor</span><span style="color: #0000FF;">(</span><span style="color: #000000;">m</span><span style="color: #0000FF;">/</span><span style="color: #000000;">2</span><span style="color: #0000FF;">)</span>
<span style="color: #008080;">end</span> <span style="color: #008080;">while</span>
<span style="color: #000000;">pq</span><span style="color: #0000FF;">[</span><span style="color: #000000;">n</span><span style="color: #0000FF;">]</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">item</span>
<span style="color: #008080;">end</span> <span style="color: #008080;">procedure</span>
<span style="color: #008080;">function</span> <span style="color: #000000;">pqPop</span><span style="color: #0000FF;">()</span>
<span style="color: #004080;">sequence</span> <span style="color: #000000;">result</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">pq</span><span style="color: #0000FF;">[</span><span style="color: #000000;">1</span><span style="color: #0000FF;">]</span>
<span style="color: #004080;">integer</span> <span style="color: #000000;">qn</span> <span style="color: #0000FF;">=</span> <span style="color: #7060A8;">length</span><span style="color: #0000FF;">(</span><span style="color: #000000;">pq</span><span style="color: #0000FF;">),</span>
<span style="color: #000000;">n</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">1</span><span style="color: #0000FF;">,</span>
<span style="color: #000000;">m</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">2</span>
<span style="color: #008080;">while</span> <span style="color: #000000;">m</span><span style="color: #0000FF;"><</span><span style="color: #000000;">qn</span> <span style="color: #008080;">do</span>
<span style="color: #008080;">if</span> <span style="color: #000000;">m</span><span style="color: #0000FF;">+</span><span style="color: #000000;">1</span><span style="color: #0000FF;"><</span><span style="color: #000000;">qn</span> <span style="color: #008080;">and</span> <span style="color: #000000;">pq</span><span style="color: #0000FF;">[</span><span style="color: #000000;">m</span><span style="color: #0000FF;">][</span><span style="color: #000000;">PRIORITY</span><span style="color: #0000FF;">]></span><span style="color: #000000;">pq</span><span style="color: #0000FF;">[</span><span style="color: #000000;">m</span><span style="color: #0000FF;">+</span><span style="color: #000000;">1</span><span style="color: #0000FF;">][</span><span style="color: #000000;">PRIORITY</span><span style="color: #0000FF;">]</span> <span style="color: #008080;">then</span>
<span style="color: #000000;">m</span> <span style="color: #0000FF;">+=</span> <span style="color: #000000;">1</span>
<span style="color: #008080;">end</span> <span style="color: #008080;">if</span>
<span style="color: #008080;">if</span> <span style="color: #000000;">pq</span><span style="color: #0000FF;">[</span><span style="color: #000000;">qn</span><span style="color: #0000FF;">][</span><span style="color: #000000;">PRIORITY</span><span style="color: #0000FF;">]<=</span><span style="color: #000000;">pq</span><span style="color: #0000FF;">[</span><span style="color: #000000;">m</span><span style="color: #0000FF;">][</span><span style="color: #000000;">PRIORITY</span><span style="color: #0000FF;">]</span> <span style="color: #008080;">then</span> <span style="color: #008080;">exit</span> <span style="color: #008080;">end</span> <span style="color: #008080;">if</span>
<span style="color: #000000;">pq</span><span style="color: #0000FF;">[</span><span style="color: #000000;">n</span><span style="color: #0000FF;">]</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">pq</span><span style="color: #0000FF;">[</span><span style="color: #000000;">m</span><span style="color: #0000FF;">]</span>
<span style="color: #000000;">n</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">m</span>
<span style="color: #000000;">m</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">m</span> <span style="color: #0000FF;">*</span> <span style="color: #000000;">2</span>
<span style="color: #008080;">end</span> <span style="color: #008080;">while</span>
<span style="color: #000000;">pq</span><span style="color: #0000FF;">[</span><span style="color: #000000;">n</span><span style="color: #0000FF;">]</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">pq</span><span style="color: #0000FF;">[</span><span style="color: #000000;">qn</span><span style="color: #0000FF;">]</span>
<span style="color: #000000;">pq</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">pq</span><span style="color: #0000FF;">[</span><span style="color: #000000;">1</span><span style="color: #0000FF;">..$-</span><span style="color: #000000;">1</span><span style="color: #0000FF;">]</span>
<span style="color: #008080;">return</span> <span style="color: #000000;">result</span>
<span style="color: #008080;">end</span> <span style="color: #008080;">function</span>
<span style="color: #7060A8;">set_rand</span><span style="color: #0000FF;">(</span><span style="color: #008080;">iff</span><span style="color: #0000FF;">(</span><span style="color: #7060A8;">platform</span><span style="color: #0000FF;">()=</span><span style="color: #004600;">JS</span><span style="color: #0000FF;">?</span><span style="color: #000000;">5749</span><span style="color: #0000FF;">:</span> <span style="color: #000080;font-style:italic;">-- (optional!)</span>
<span style="color: #008080;">iff</span><span style="color: #0000FF;">(</span><span style="color: #7060A8;">machine_bits</span><span style="color: #0000FF;">()=</span><span style="color: #000000;">32</span><span style="color: #0000FF;">?</span><span style="color: #000000;">4601</span><span style="color: #0000FF;">:</span><span style="color: #000000;">97</span><span style="color: #0000FF;">)))</span>
<span style="color: #008080;">constant</span> <span style="color: #000000;">set</span> <span style="color: #0000FF;">=</span> <span style="color: #7060A8;">shuffle</span><span style="color: #0000FF;">({{</span><span style="color: #008000;">"Clear drains"</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">3</span><span style="color: #0000FF;">},</span>
<span style="color: #0000FF;">{</span><span style="color: #008000;">"Feed cat"</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">4</span><span style="color: #0000FF;">},</span>
<span style="color: #0000FF;">{</span><span style="color: #008000;">"Make tea"</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">5</span><span style="color: #0000FF;">},</span>
<span style="color: #0000FF;">{</span><span style="color: #008000;">"Solve RC tasks"</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">1</span><span style="color: #0000FF;">},</span>
<span style="color: #0000FF;">{</span><span style="color: #008000;">"Tax return"</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">2</span><span style="color: #0000FF;">}})</span>
<span style="color: #008080;">for</span> <span style="color: #000000;">i</span><span style="color: #0000FF;">=</span><span style="color: #000000;">1</span> <span style="color: #008080;">to</span> <span style="color: #7060A8;">length</span><span style="color: #0000FF;">(</span><span style="color: #000000;">set</span><span style="color: #0000FF;">)</span> <span style="color: #008080;">do</span>
<span style="color: #000000;">pqAdd</span><span style="color: #0000FF;">(</span><span style="color: #000000;">set</span><span style="color: #0000FF;">[</span><span style="color: #000000;">i</span><span style="color: #0000FF;">])</span>
<span style="color: #000000;">pqAdd</span><span style="color: #0000FF;">(</span><span style="color: #000000;">set</span><span style="color: #0000FF;">[</span><span style="color: #7060A8;">rand</span><span style="color: #0000FF;">(</span><span style="color: #7060A8;">length</span><span style="color: #0000FF;">(</span><span style="color: #000000;">set</span><span style="color: #0000FF;">))])</span>
<span style="color: #008080;">end</span> <span style="color: #008080;">for</span>
<span style="color: #004080;">sequence</span> <span style="color: #000000;">res</span> <span style="color: #0000FF;">=</span> <span style="color: #0000FF;">{}</span>
<span style="color: #008080;">while</span> <span style="color: #7060A8;">length</span><span style="color: #0000FF;">(</span><span style="color: #000000;">pq</span><span style="color: #0000FF;">)</span> <span style="color: #008080;">do</span>
<span style="color: #0000FF;">?</span><span style="color: #000000;">pqPop</span><span style="color: #0000FF;">()</span>
<span style="color: #008080;">end</span> <span style="color: #008080;">while</span>
<!--</syntaxhighlight>-->
{{out}}
<small>As shown set_rand() achieves consistency per-platform, not cross-platform, the numbers above were found using a brute-force outer loop stopping on the desired result, since deleted.</small>
<pre>
{"Solve RC tasks",1}
{"Tax return",2}
{"Clear drains",3}
{"Feed cat",4}
{"Feed cat",4}
{"Feed cat",4}
Line 3,934 ⟶ 6,570:
{"Make tea",5}
</pre>
=== builtin ===
If you omit MAX_HEAP or (same thing) specify MIN_HEAP, the output'll be 1..5
<!--<syntaxhighlight lang="phix">(phixonline)-->
<span style="color: #008080;">with</span> <span style="color: #008080;">javascript_semantics</span>
<span style="color: #008080;">constant</span> <span style="color: #000000;">tasklist</span> <span style="color: #0000FF;">=</span> <span style="color: #7060A8;">pq_new</span><span style="color: #0000FF;">(</span><span style="color: #004600;">MAX_HEAP</span><span style="color: #0000FF;">)</span>
<span style="color: #7060A8;">pq_add</span><span style="color: #0000FF;">({</span><span style="color: #008000;">"Clear drains"</span><span style="color: #0000FF;">,</span><span style="color: #000000;">3</span><span style="color: #0000FF;">},</span><span style="color: #000000;">tasklist</span><span style="color: #0000FF;">)</span>
<span style="color: #7060A8;">pq_add</span><span style="color: #0000FF;">({</span><span style="color: #008000;">"Feed cat"</span><span style="color: #0000FF;">,</span><span style="color: #000000;">4</span><span style="color: #0000FF;">},</span><span style="color: #000000;">tasklist</span><span style="color: #0000FF;">)</span>
<span style="color: #7060A8;">pq_add</span><span style="color: #0000FF;">({</span><span style="color: #008000;">"Make tea"</span><span style="color: #0000FF;">,</span><span style="color: #000000;">5</span><span style="color: #0000FF;">},</span><span style="color: #000000;">tasklist</span><span style="color: #0000FF;">)</span>
<span style="color: #7060A8;">pq_add</span><span style="color: #0000FF;">({</span><span style="color: #008000;">"Solve RC tasks"</span><span style="color: #0000FF;">,</span><span style="color: #000000;">1</span><span style="color: #0000FF;">},</span><span style="color: #000000;">tasklist</span><span style="color: #0000FF;">)</span>
<span style="color: #7060A8;">pq_add</span><span style="color: #0000FF;">({</span><span style="color: #008000;">"Tax return"</span><span style="color: #0000FF;">,</span><span style="color: #000000;">2</span><span style="color: #0000FF;">},</span><span style="color: #000000;">tasklist</span><span style="color: #0000FF;">)</span>
<span style="color: #008080;">while</span> <span style="color: #7060A8;">pq_size</span><span style="color: #0000FF;">(</span><span style="color: #000000;">tasklist</span><span style="color: #0000FF;">)</span> <span style="color: #008080;">do</span>
<span style="color: #0000FF;">{</span><span style="color: #004080;">string</span> <span style="color: #000000;">task</span><span style="color: #0000FF;">,</span> <span style="color: #004080;">integer</span> <span style="color: #000000;">priority</span><span style="color: #0000FF;">}</span> <span style="color: #0000FF;">=</span> <span style="color: #7060A8;">pq_pop</span><span style="color: #0000FF;">(</span><span style="color: #000000;">tasklist</span><span style="color: #0000FF;">)</span>
<span style="color: #7060A8;">printf</span><span style="color: #0000FF;">(</span><span style="color: #000000;">1</span><span style="color: #0000FF;">,</span><span style="color: #008000;">"%d: %s\n"</span><span style="color: #0000FF;">,{</span><span style="color: #000000;">priority</span><span style="color: #0000FF;">,</span><span style="color: #000000;">task</span><span style="color: #0000FF;">})</span>
<span style="color: #008080;">end</span> <span style="color: #008080;">while</span>
<!--</syntaxhighlight>-->
{{out}}
<pre>
5: Make tea
4: Feed cat
3: Clear drains
2: Tax return
1: Solve RC tasks
</pre>
=={{header|Phixmonti}}==
<syntaxhighlight lang="phixmonti">/# Rosetta Code problem: http://rosettacode.org/wiki/Priority_queue
by Galileo, 05/2022 #/
include ..\Utilitys.pmt
( )
( 3 "Clear drains" ) 0 put ( 4 "Feed cat" ) 0 put ( 5 "Make tea" ) 0 put ( 1 "Solve RC tasks" ) 0 put ( 2 "Tax return" ) 0 put
sort pop swap print pstack
</syntaxhighlight>
{{out}}
<pre>[1, "Solve RC tasks"]
[[[2, "Tax return"], [3, "Clear drains"], [4, "Feed cat"], [5, "Make tea"]]]
=== Press any key to exit ===</pre>
=={{header|PHP}}==
{{works with|PHP|5.3+}}
PHP's <code>SplPriorityQueue</code> class implements a max-heap. PHP also separately has <code>SplHeap</code>, <code>SplMinHeap</code>, and <code>SplMaxHeap</code> classes.
<
$pq = new SplPriorityQueue;
Line 3,954 ⟶ 6,632:
print_r($pq->extract());
}
?></
Output:
Line 3,987 ⟶ 6,665:
{{works with|PHP|5.3+}}
The difference between <code>SplHeap</code> and <code>SplPriorityQueue</code> is that <code>SplPriorityQueue</code> takes the data and the priority as two separate arguments, and the comparison is only made on the priority; whereas <code>SplHeap</code> takes only one argument (the element), and the comparison is made on that directly. In all of these classes it is possible to provide a custom comparator by subclassing the class and overriding its <code>compare</code> method.
<
$pq = new SplMinHeap;
Line 3,999 ⟶ 6,677:
print_r($pq->extract());
}
?></
Output:
Line 4,029 ⟶ 6,707:
)
</pre>
=={{header|Picat}}==
Picat has built-in support for min and max heaps.
<syntaxhighlight lang="picat">main =>
Tasks = [[3,"Clear drains"],
[4,"Feed cat"],
[5,"Make tea"],
[1,"Solve RC tasks"],
[2,"Tax return"]],
Heap = new_min_heap([]),
foreach(Task in Tasks)
Heap.heap_push(Task),
println(top=Heap.heap_top())
end,
nl,
println(Heap),
println(size=Heap.heap_size),
nl,
println("Pop the elements from the queue:"),
println([Heap.heap_pop() : _ in 1..Heap.heap_size]).</syntaxhighlight>
{{out}}
<pre>top = [3,Clear drains]
top = [3,Clear drains]
top = [3,Clear drains]
top = [1,Solve RC tasks]
top = [1,Solve RC tasks]
_$heap(5,{[1,Solve RC tasks],[2,Tax return],[5,Make tea],[4,Feed cat],[3,Clear drains],_33c8},min)
size = 5
Pop the elements from the queue:
[[1,Solve RC tasks],[2,Tax return],[3,Clear drains],[4,Feed cat],[5,Make tea]]</pre>
The heaps creation functions can take the task list as argument:
<syntaxhighlight lang="picat"> Tasks = [[3,"Clear drains"],
[4,"Feed cat"],
[5,"Make tea"],
[1,"Solve RC tasks"],
[2,"Tax return"]],
Heap = new_min_heap(Tasks),
println([Heap.heap_pop() : _ in 1..Heap.heap_size]).</syntaxhighlight>
=={{header|PicoLisp}}==
The following implementation imposes no limits. It uses a [http://software-lab.de/doc/refI.html#idx binary tree] for storage. The priority levels may be numeric, or of any other type.
<
(de insertPQ (Queue Prio Item)
(idx Queue (cons Prio Item) T) )
Line 4,049 ⟶ 6,770:
# Merge second queue into first
(de mergePQ (Queue1 Queue2)
(balance Queue1 (sort (conc (idx Queue1) (idx Queue2)))) )</
Test:
<
(off Pq1 Pq2)
Line 4,068 ⟶ 6,789:
# Remove and print all items from first queue
(while Pq1
(println (removePQ 'Pq1)) )</
Output:
<pre>(Solve RC tasks)
Line 4,076 ⟶ 6,797:
(Make tea)</pre>
=== Alternative version using a pairing heap: ===
<syntaxhighlight lang="picolisp">
(de heap-first (H) (car H))
Line 4,100 ⟶ 6,821:
(de heap-rest (H)
("merge-pairs" (cdr H)))
</syntaxhighlight>
Test:
<syntaxhighlight lang="picolisp">
(setq H NIL)
(for
Line 4,118 ⟶ 6,839:
(bye)
</syntaxhighlight>
{{Out}}
<pre>
Line 4,133 ⟶ 6,854:
Example of use :
<
TL0 = [3-'Clear drains',
4-'Feed cat'],
Line 4,161 ⟶ 6,882:
heap_to_list(Heap4, TL2),
writeln('Content of the queue'), maplist(writeln, TL2).
</syntaxhighlight>
The output :
<pre>1 ?- priority-queue.
Line 4,185 ⟶ 6,906:
The map stores the elements of a given priority in a FIFO list.
Priorities can be any signed 32 value.
<
List description.s() ;implements FIFO queue
EndStructure
Line 4,303 ⟶ 7,024:
Print(#CRLF$ + #CRLF$ + "Press ENTER to exit"): Input()
CloseConsole()
EndIf</
{{out}}
<pre>Solve RC tasks
Line 4,323 ⟶ 7,044:
The data structures in the "queue" module are synchronized multi-producer, multi-consumer queues for multi-threaded use. They can however handle this task:
<
>>> pq = queue.PriorityQueue()
>>> for item in ((3, "Clear drains"), (4, "Feed cat"), (5, "Make tea"), (1, "Solve RC tasks"), (2, "Tax return")):
Line 4,338 ⟶ 7,059:
(4, 'Feed cat')
(5, 'Make tea')
>>> </
;Help text for queue.PriorityQueue:
<
>>> help(queue.PriorityQueue)
Help on class PriorityQueue in module queue:
Line 4,447 ⟶ 7,168:
| list of weak references to the object (if defined)
>>> </
===Using heapq===
Line 4,453 ⟶ 7,174:
Although one can use the heappush method to add items individually to a heap similar to the method used in the PriorityQueue example above, we will instead transform the list of items into a heap in one go then pop them off one at a time as before.
<
>>> items = [(3, "Clear drains"), (4, "Feed cat"), (5, "Make tea"), (1, "Solve RC tasks"), (2, "Tax return")]
>>> heapify(items)
Line 4,465 ⟶ 7,186:
(4, 'Feed cat')
(5, 'Make tea')
>>> </
;Help text for module heapq:
<
Help on module heapq:
Line 4,556 ⟶ 7,277:
>>> </
=={{header|Quackery}}==
For more examples uf usage, see [[Sorting algorithms/Heapsort#Quackery]] and [[Huffman coding#Quackery]]
<syntaxhighlight lang="quackery">( ***** priotity queue ***** )
[ stack ] is heap.pq ( --> s )
[ stack ] is comp.pq ( --> s )
[ unpack
comp.pq put heap.pq put ] is pq->stacks ( p --> )
[ heap.pq take comp.pq take
2 pack ] is stacks->pq ( --> p )
[ heap.pq share swap peek ] is heapeek ( n --> x )
[ heap.pq take
swap poke heap.pq put ] is heapoke ( n x --> )
[ 1 - 1 >> ] is parent ( n --> n )
[ 0 > ] is has-parent ( n --> b )
[ 1 << 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 --> n )
[ 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 1 >> times
[ i heapify.pq ]
stacks->pq ] is pqwith ( [ --> p )
( ***** task ***** )
[ 2 pack topq ] is insert ( p n $ --> p )
[ frompq unpack ] is dequeue ( p --> p n $ )
[] pqwith [ 0 peek dip [ 0 peek ] < ]
3 $ "Clear drains" insert
4 $ "Feed cat" insert
5 $ "Make tea" insert
1 $ "Solve RC tasks" insert
2 $ "Tax return" insert
5 times
[ dequeue
swap echo say ": "
echo$ cr ]
drop</syntaxhighlight>
{{out}}
<pre>1: Solve RC tasks
2: Tax return
3: Clear drains
4: Feed cat
5: Make tea
</pre>
=={{header|R}}==
Using closures:
<
keys <- values <- NULL
insert <- function(key, value) {
Line 4,585 ⟶ 7,419:
while(!pq$empty()) {
with(pq$pop(), cat(key,":",value,"\n"))
}</
2 : Tax return
3 : Clear drains
4 : Feed cat
5 : Make tea</
setRefClass("PriorityQueue",
fields = list(keys = "numeric", values = "list"),
Line 4,605 ⟶ 7,439:
},
empty = function() length(keys) == 0
))</
=={{header|Racket}}==
This solution implements priority queues on top of heaps.
<
#lang racket
(require data/heap)
Line 4,634 ⟶ 7,468:
(remove-min!)
(remove-min!)
</syntaxhighlight>
Output:
<
"Solve RC tasks"
"Tax return"
Line 4,642 ⟶ 7,476:
"Feed cat"
"Make tea"
</syntaxhighlight>
=={{header|Raku}}==
Line 4,650 ⟶ 7,484:
The tasks are stored internally as an array of FIFO buffers, so multiple tasks of the same priority level will be returned in the order they were stored.
<syntaxhighlight lang="raku"
has @!tasks;
Line 4,677 ⟶ 7,511:
}
say $pq.get until $pq.is-empty;</
{{out}}
Line 4,692 ⟶ 7,526:
===version 1===
Programming note: this REXX version allows any number (with or without decimals, say, '''5.7''') for the priority, including negative numbers.
<
#=0; @.= /*0 tasks; nullify the priority queue.*/
say '══════ inserting tasks.'; call .ins 3 "Clear drains"
Line 4,713 ⟶ 7,547:
if top=='' | _>top then do; top=_; top#=j; end
end /*j*/
return top#</
{{out|output}}
<pre>
Line 4,730 ⟶ 7,564:
===version 2===
<
n=0
task.=0 /* for the sake of task.0done.* */
Line 4,771 ⟶ 7,605:
task.0done.j=1
todo=todo-1
return res</
{{out}}
<pre>------ inserting tasks.
Line 4,793 ⟶ 7,627:
=={{header|Ruby}}==
A naive, inefficient implementation
<
def initialize(data=nil)
@q = Hash.new {|h, k| h[k] = []}
Line 4,874 ⟶ 7,708:
puts pq3.pop
end
puts "peek : #{pq3.peek}"</
{{out}}
Line 4,901 ⟶ 7,735:
=={{header|Run BASIC}}==
<
#mem execute("CREATE TABLE queue (priority float,descr text)")
Line 4,945 ⟶ 7,779:
print priority;" ";descr$
next i
RETURN</
{{out}}
<pre> -------------- Find first priority ---------------------
Line 4,962 ⟶ 7,796:
=={{header|Rust}}==
<
use std::cmp::Ordering;
use std::borrow::Cow;
Line 5,009 ⟶ 7,843:
println!("{}", item.task);
}
}</
{{out}}
<pre>Solve RC tasks
Line 5,016 ⟶ 7,850:
Feed cat
Clear drains</pre>
=={{header|SAS}}==
Using macros in a SAS data step:
<syntaxhighlight lang="sas">%macro HeapInit(size=1000,nchar=20);
do;
_len = 0;
_size = &size;
array _times(&size) _temporary_ ;
array _kinds(&size) $ &nchar _temporary_;
drop _size _len;
end;
%mend;
%macro HeapSwapItem(index1, index2);
do;
_tempN = _times[&index1]; _times[&index1] = _times[&index2]; _times[&index2] = _tempN;
_tempC = _kinds[&index1]; _kinds[&index1] = _kinds[&index2]; _kinds[&index2]= _tempC;
drop _tempN _tempC;
end;
%mend;
%macro HeapEmpty;
(_len=0)
%mend;
%macro HeapCompare(index1, index2);
(_times[&index1] < _times[&index2])
%mend;
%macro HeapSiftdown(index);
do;
_parent = &index;
_done = 0;
do while (_parent*2 <= _len & ^_done);
_child = _parent*2;
if (_child+1 <= _len and %HeapCompare(_child+1,_child)) then
_child = _child + 1;
if %HeapCompare(_child,_parent) then do;
%HeapSwapItem(_child,_parent);
_parent = _child;
end;
else _done = 1;
end;
drop _done _parent _child;
end;
%mend;
%macro HeapSiftup(index);
do;
_child = &index;
_done = 0;
do while(_child>1 and ^_done);
_parent = floor(_child/2);
if %HeapCompare(_parent,_child) then
_done = 1;
else do;
%HeapSwapItem(_child,_parent);
_tempN = _child;
_child = _parent;
_parent = _tempN;
end;
end;
drop _parent _child _done _tempN;
end;
%mend;
%macro HeapPush(time, kind);
do;
if _len >= _size then do;
put "ERROR: exceeded size of heap. Consider changing size argument to %HeapInit.";
stop;
end;
_len = _len + 1;
_times[_len] = &time;
_kinds[_len] = &kind;
%HeapSiftup(_len);
end;
%mend;
%macro HeapPop;
do;
_len = _len - 1;
if (_len>0) then do;
_times[1] = _times[_len+1];
_kinds[1] = _kinds[_len+1];
%HeapSiftdown(1);
end;
end;
%mend;
%macro HeapPeek;
time = _times[1];
kind = _kinds[1];
put time kind;
%mend;
data _null_;
%HeapInit;
%HeapPush(3, "Clear drains");
%HeapPush(4, "Feed cat");
%HeapPush(5, "Make tea");
%HeapPush(1, "Solve RC tasks");
%HeapPush(2, "Tax return");
do while(^%HeapEmpty);
%HeapPeek;
%HeapPop;
end;
run;</syntaxhighlight>
{{output}}
<pre>1 Solve RC tasks
2 Tax return
3 Clear drains
4 Feed cat
5 Make tea</pre>
An implementation using <code>proc ds2</code> may be more structured:
<syntaxhighlight lang="sas">proc ds2;
package Heap / overwrite=yes;
dcl int _entryorder _size _len _entryOrders[1000];
dcl double _times[1000];
dcl varchar(20) _kinds[1000];
method init();
_entryOrder = 1;
_size = 1000;
_len = 0;
end;
method empty() returns int;
return(_len=0);
end;
method compare(int index1, int index2) returns int;
return(_times[index1] < _times[index2] or (_times[index1] = _times[index2] and _entryOrders[index1] < _entryOrders[index2]));
end;
method SetItem(int index, double _time, int entryOrder, varchar(20) kind);
_times[index] = _time;
_entryOrders[index] = entryOrder;
_kinds[index] = kind;
end;
method CopyItem(int ito, int ifrom);
_times[ito] = _times[ifrom];
_entryOrders[ito] = _entryOrders[ifrom];
_kinds[ito] = _kinds[ifrom];
end;
method SwapItem(int index1, int index2);
dcl double tempD;
dcl int tempI;
dcl varchar(20) tempC;
tempD = _times[index1]; _times[index1] = _times[index2]; _times[index2]= tempD;
tempI = _entryorders[index1]; _entryorders[index1] = _entryorders[index2]; _entryorders[index2]= tempI;
tempC = _kinds[index1]; _kinds[index1] = _kinds[index2]; _kinds[index2]= tempC;
end;
method Siftdown(int index);
dcl int parent done child;
parent = index;
done = 0;
do while (parent*2 <= _len and ^done);
child = parent*2;
if (child+1 <= _len and Compare(child+1,child)) then
child = child + 1;
if Compare(child,parent) then do;
SwapItem(child,parent);
parent = child;
end;
else done = 1;
end;
end;
method Siftup(int index);
dcl int parent child done tempI;
child = index;
done = 0;
do while(child>1 and ^done);
parent = floor(child/2);
if Compare(parent,child) then
done = 1;
else do;
SwapItem(child,parent);
tempI = child;
child = parent;
parent = tempI;
end;
end;
end;
method Pop();
_len = _len - 1;
if (_len>0) then do;
CopyItem(1,_len+1);
Siftdown(1);
end;
end;
method PeekTime() returns double;
return _times[1];
end;
method PeekKind() returns varchar(20);
return _kinds[1];
end;
method Push(double _time, varchar(20) kind);
if _len >= _size then do;
put 'ERROR: exceeded size of heap.';
stop;
end;
_len = _len + 1;
_entryOrder = _entryOrder + 1;
SetItem(_len, _time, _entryOrder, kind);
Siftup(_len);
end;
endpackage;
run;
data _null_;
dcl package Heap h();
method init();
dcl double _time;
dcl varchar(20) _kind;
h.init();
h.Push(3, 'Clear drains');
h.Push(4, 'Feed cat');
h.Push(5, 'Make tea');
h.Push(1, 'Solve RC tasks');
h.Push(2, 'Tax return');
do while(^h.empty());
_time = h.PeekTime();
_kind = h.PeekKind();
put _time _kind;
h.Pop();
end;
end;
enddata;
run;</syntaxhighlight>
=={{header|Scala}}==
Scala has a class PriorityQueue in its standard library.
<
case class Task(prio:Int, text:String) extends Ordered[Task] {
def compare(that: Task)=that.prio compare this.prio
Line 5,027 ⟶ 8,078:
var q=PriorityQueue[Task]() ++ Seq(Task(3, "Clear drains"), Task(4, "Feed cat"),
Task(5, "Make tea"), Task(1, "Solve RC tasks"), Task(2, "Tax return"))
while(q.nonEmpty) println(q dequeue)</
Output:
<pre>Task(1,Solve RC tasks)
Line 5,035 ⟶ 8,086:
Task(5,Make tea)</pre>
Instead of deriving the class from Ordering an implicit conversion could be provided.
<
implicit def taskOrdering=new Ordering[Task] {
def compare(t1:Task, t2:Task):Int=t2.prio compare t1.prio
}</
=={{header|SenseTalk}}==
We use New to create an object instance -- in this case (for simplicity) based on the script itself, which is named PriorityQueue. The Tell command or dot notation are then used to send messages directly to that object.
<syntaxhighlight lang="sensetalk">
// PriorityQueue.script
set Tasks to a new PriorityQueue
tell Tasks to add 3,"Clear drains"
tell Tasks to add 4,"Feed cat"
tell Tasks to add 5,"Make tea"
tell Tasks to add 1,"Solve RC tasks"
tell Tasks to add 2,"Tax return"
put "Initial tasks:"
put Tasks.report & return
put Tasks.getTop into topItem
put "Top priority: " & topItem & return
put "Remaining:" & return & Tasks.report
------
properties
queue:[]
end properties
to add newPriority, newTask
repeat with each item of my queue
if newPriority comes before the priority of it then
insert {priority:newPriority, task:newTask} before item the counter of my queue
return
end if
end repeat
insert {priority:newPriority, task:newTask} into my queue -- add at end if last priority
end add
to getTop
pull my queue into firstItem
return firstItem
end getTop
to report
return (priority of each && task of each for each item of my queue) joined by return
end report
</syntaxhighlight>
{{out}}
<pre>
Initial tasks:
1 Solve RC tasks
2 Tax return
3 Clear drains
4 Feed cat
5 Make tea
Top priority: {priority:1, task:"Solve RC tasks"}
Remaining:
2 Tax return
3 Clear drains
4 Feed cat
5 Make tea
</pre>
=={{header|Sidef}}==
{{trans|Raku}}
<
has tasks = []
Line 5,071 ⟶ 8,184:
}
say pq.get while !pq.is_empty</
{{out}}
Line 5,089 ⟶ 8,202:
Note: this is a max-heap
<
type priority = int
val compare = Int.compare
Line 5,117 ⟶ 8,230:
in
aux pq
end</
testing:
Line 5,127 ⟶ 8,240:
1, Solve RC tasks
</pre>
=={{header|Stata}}==
{{trans|Fortran}}
Using <code>mata</code>, which has 1-based arrays:
<syntaxhighlight lang="stata">mata
struct Node {
real scalar time
transmorphic data
}
class Heap {
public:
struct Node rowvector nodes
real scalar len
real scalar size
real scalar minHeap
void new()
void push()
void siftup()
void siftdown()
struct Node scalar pop()
real scalar empty()
real scalar compare()
}
real scalar Heap::compare(a,b) {
struct Node scalar left, right
left = nodes[a]
right = nodes[b]
return(minHeap ? left.time<right.time : left.time>right.time)
}
void Heap::new() {
len = 0
size = 4
nodes = Node(1,size)
minHeap = 1 // defaults to min heap
}
real scalar Heap::empty() {
return(len==0)
}
void Heap::siftdown(real scalar index) {
parent = index
while (parent*2 <= len) {
child = parent*2
if (child+1 <= len ? compare(child+1,child) : 0) {
child++
}
if (compare(child,parent)) {
nodes[(child,parent)] = nodes[(parent,child)]
parent = child
} else break
}
}
void Heap::siftup(real scalar index) {
child = index
while(child>1) {
parent = floor(child/2)
if (compare(parent,child)) {
break
}
nodes[(child,parent)] = nodes[(parent,child)]
temp = child
child = parent
parent = temp
}
}
void Heap::push (real scalar time, transmorphic data) {
if (len + 1 >= size) {
nodes = (nodes, nodes)
size = size*2
}
len++
nodes[len].time = time
nodes[len].data = data
siftup(len)
}
struct Node scalar Heap::pop () {
if (len==0) {
_error(3000,"empty heap")
}
len--
struct Node scalar newnode
newnode.time = nodes[1].time
newnode.data = nodes[1].data
if (len>0) {
nodes[1] = nodes[len+1]
siftdown(1)
}
return(newnode)
}
void testHeap(real scalar minHeap) {
class Heap scalar h
struct Node scalar node
h = Heap()
h.minHeap = minHeap
h.push(3, "Clear drains")
h.push(4, "Feed cat")
h.push(5, "Make tea")
h.push(1, "Solve RC tasks")
h.push(2, "Tax return")
while (!h.empty()) {
node = h.pop()
printf("%f -> %s\n", node.time, node.data)
}
}
testHeap(1)
testHeap(0)
end
</syntaxhighlight>
{{out}}
<pre>
: testHeap(1)
1 -> Solve RC tasks
2 -> Tax return
3 -> Clear drains
4 -> Feed cat
5 -> Make tea
: testHeap(0)
5 -> Make tea
4 -> Feed cat
3 -> Clear drains
2 -> Tax return
1 -> Solve RC tasks
</pre>
Note: the Fortran version was simpler and did not use the <code>siftup()</code> method.
=={{header|Swift}}==
You can use <code>CFBinaryHeap</code> from Core Foundation, but it is super ugly due to the fact that <code>CFBinaryHeap</code> operates on generic pointers, and you need to convert back and forth between that and objects.
{{works with|Swift|2.x}}
<
var priority : Int
var name: String
Line 5,186 ⟶ 8,425:
while pq.count != 0 {
print(pq.pop())
}</
{{out}}
Line 5,199 ⟶ 8,438:
=={{header|Tcl}}==
{{tcllib|struct::prioqueue}}
<
set pq [struct::prioqueue]
Line 5,216 ⟶ 8,455:
# Remove the front-most item from the priority queue
puts [$pq get]
}</
Which produces this output:
<pre>
Line 5,224 ⟶ 8,463:
Tax return
Solve RC tasks
</pre>
=={{header|uBasic/4tH}}==
This implementation inserts items using a binary search. Hence, no sorting is required, since all entries are always in order of priority. It also allows for listing of valid entries.
<syntaxhighlight lang="text">b = -1 ' b points to last entry on the queue
q = FUNC(_Grab) ' now grab the top value
' and display it
Print Peek(q, 0) - Ord("0"), Show(Chop(q, 1))
Print
Proc _Insert(3, "Clear drains") ' insert the whole bunch
Proc _Insert(4, "Feed cat")
Proc _Insert(5, "Make tea")
Proc _Insert(1, "Solve RC tasks")
Proc _Insert(2, "Tax return")
For x = 0 To b: Proc _List(x) : Next ' list all entries
q = FUNC(_Grab) ' now grab the top value
Print ' and display it
Print Peek(q, 0) - Ord("0"), Show(Chop(q, 1))
Print
For x = 0 To b: Proc _List(x) : Next ' list all entries
End
_Grab ' return and remove top entry
Local (2)
' return dummy on error
If b < 0 Then Return ("0No such entry")
a@ = @(0)) ' save the top entry
For b@ = 0 To Set(b, b - 1) : @(b@) = @(b@+1): Next
Return (a@)
_List ' list any (valid) position on queue
Param (1)
If (a@ > b) = 0 Then Print Peek(@(a@), 0) - Ord("0"), Show(Chop(@(a@), 1))
Return
_Insert ' insert an entry
Param (2) ' priority, task
Local (1)
c@ = FUNC(_binarySearch(a@, 0, b)) ' search the position
Proc _MakeRoom (c@) ' make room
@(c@) = Join(Str(a@), b@) ' assign the entry
Return
_binarySearch ' perform a binary search
Param(3) ' value, start index, end index
Local(1) ' The middle of the array
' Ok, signal we didn't find it
If c@ < b@ Then Return (b@) ' first entry on start
d@ = SHL(b@ + c@, -1) ' prevent overflow (LOL!)
If a@ < Peek(@(d@), 0) - Ord("0") Then Return (FUNC(_binarySearch (a@, b@, d@-1)))
If a@ > Peek(@(d@), 0) - Ord("0") Then Return (FUNC(_binarySearch (a@, d@+1, c@)))
If a@ = Peek(@(d@), 0) - Ord("0") Then Return (d@)
Return (-1) ' -1 on error
_MakeRoom ' make some space
Param (1) ' starting position
Local (1)
' from bottom to top
For b@ = Set(b, b+1) To a@ + 1 Step -1: @(b@) = @(b@-1) : Next
Return
</syntaxhighlight>
{{Out}}
First an entry is dequeued from an empty queue. Then all entries are inserted and listed. Finally, another entry is dequeued and the remainder of the entries is listed again.
<pre>0 No such entry
1 Solve RC tasks
2 Tax return
3 Clear drains
4 Feed cat
5 Make tea
1 Solve RC tasks
2 Tax return
3 Clear drains
4 Feed cat
5 Make tea
0 OK, 0:750
</pre>
=={{header|VBA}}==
<
Priority As Integer
Data As String
Line 5,305 ⟶ 8,631:
Debug.Print t.Priority, t.Data
Loop
End Sub</
2 Tax return
3 Clear drains
4 Feed cat
5 Make tea
</pre>
=={{header|VBScript}}==
I wrote this priority queue in a class. It uses a dynamic array to implement the class. Function out_of_order must be adapted to the data. Run it with CScript.
<syntaxhighlight lang="vb">
option explicit
Class prio_queue
private size
private q
'adapt this function to your data
private function out_of_order(f1,f2): out_of_order = f1(0)>f2(0):end function
function peek
peek=q(1)
end function
property get qty
qty=size
end property
property get isempty
isempty=(size=0)
end property
function remove
dim x
x=q(1)
q(1)=q(size)
size=size-1
sift_down
remove=x
end function
sub add (x)
size=size+1
if size>ubound(q) then redim preserve q(ubound(q)*1.1)
q(size)=x
sift_up
end sub
Private sub swap (i,j)
dim x
x=q(i):q(i)=q(j):q(j)=x
end sub
private sub sift_up
dim h,p
h=size
p=h\2
if p=0 then exit sub
while out_of_order(q(p),q(h))
swap h,p
h=p
p=h\2
if p=0 then exit sub
wend
end sub
end sub
private sub sift_down
dim p,h
p=1
do
if p>=size then exit do
h =p*2
if h >size then exit do
if h+1<=size then if out_of_order(q(h),q(h+1)) then h=h+1
if out_of_order(q(p),q(h)) then swap h,p
p=h
loop
end sub
'Al instanciar objeto con New
Private Sub Class_Initialize( )
redim q(100)
size=0
End Sub
'When Object is Set to Nothing
Private Sub Class_Terminate( )
erase q
End Sub
End Class
'-------------------------------------
'test program
'---------------------------------
dim tasks:tasks=array(_
array(3,"Clear drains"),_
array(4,"Feed cat"),_
array(5,"Make tea"),_
array(1,"Solve RC tasks"),_
array(2,"Tax return"))
dim queue,i,x
set queue=new prio_queue
for i=0 to ubound(tasks)
queue.add(tasks(i))
next
wscript.echo "Done: " & queue.qty() &" items in queue. "& queue.peek()(1)& " is at the top." & vbcrlf
while not queue.isempty()
x=queue.remove()
wscript.echo x(0),x(1)
wend
set queue= nothing
</syntaxhighlight>
Output:
<pre>
Done: 5 items in queue. Item Solve RC tasks is at the top.
1 Solve RC tasks
2 Tax return
3 Clear drains
4 Feed cat
5 Make tea
</pre>
=={{header|Wren}}==
{{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="wren">import "./queue" for PriorityQueue
var tasks = PriorityQueue.new()
tasks.push("Clear drains", 3)
tasks.push("Feed cat", 4)
tasks.push("Make tea", 5)
tasks.push("Solve RC tasks", 1)
tasks.push("Tax return", 2)
while (!tasks.isEmpty) {
var t = tasks.pop()
System.print(t)
}</syntaxhighlight>
{{out}}
<pre>
[Make tea, 5]
[Feed cat, 4]
[Clear drains, 3]
[Tax return, 2]
[Solve RC tasks, 1]
</pre>
Line 5,320 ⟶ 8,791:
The <code>'PUSH</code> method never needs to search down the levels. The efficiency bottleneck here is probably the implementation of <code>NCONC</code> (used for adding the new item to the end of the queue at the relevant level). A priority <i>stack</i>, with first in / last out at each priority level rather than first in / first out, would be faster.
<
(instance-variables queue lowest-priority most-urgent) )
Line 5,354 ⟶ 8,825:
(define-method (priority-queue 'emptyp)
(and (= most-urgent lowest-priority) (null (vector-ref queue most-urgent))) )</
The example uses strings, but the data items stored in the priority queue can be of any type (including the empty list—or even other priority queues).
<
(pq 'push "Clear drains" 3)
Line 5,363 ⟶ 8,834:
(pq 'push "Make tea" 5)
(pq 'push "Solve RC tasks" 1)
(pq 'push "Tax return" 2)</
{{out}}
Items are popped beginning from the most urgent:
<
"Solve RC tasks"
[2] (pq 'pop)
"Tax return"</
Within each priority level, new items are pushed onto the end and popped from the beginning of the list (a queue is a first in / first out data structure):
<
("Feed cat" "Answer emails")</
Attempting to push with an invalid priority value returns the empty list, i.e. false:
<
()</
<code>'EMPTYP</code> returns false if the priority queue is not empty:
<
()</
<code>'PEEK</code> non-destructively returns the item that would be popped if you called <code>'POP</code>:
<
"Clear drains"</
If you want to examine a whole priority queue, the built-in <code>'SHOW</code> method allows you to do so:
<
Object is #<Object:PRIORITY-QUEUE #x4e2cba8>, Class is #<Class:PRIORITY-QUEUE #x4e254c8>
Line 5,396 ⟶ 8,867:
LOWEST-PRIORITY = 5
MOST-URGENT = 3
#<Object:PRIORITY-QUEUE #x4e2cba8></
Once all the items have been popped, the priority queue is empty and <code>'EMPTYP</code> then returns true:
<
"Clear drains"
Line 5,412 ⟶ 8,883:
[12] (pq 'emptyp)
#T</
Attempting to pop from an empty priority queue returns false:
<
()</
=={{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}}==
Line 5,424 ⟶ 8,948:
Save the following code as <code>priority_queue.zig</code>, and run the tests using <code>zig test priority_queue.zig</code>.
<syntaxhighlight lang="zig">
const std = @import("std");
const PriorityQueue = std.PriorityQueue;
Line 5,451 ⟶ 8,975:
/// fn(T, T) bool
const Comparator = struct {
fn maxCompare(_: void, a: Task, b: Task)
return std.math.order(a.priority
}
fn minCompare(_: void, a: Task, b: Task)
return std.math.order(a.priority
}
};
Line 5,463 ⟶ 8,987:
var arena = std.heap.ArenaAllocator.init(std.heap.page_allocator);
defer arena.deinit();
var pq = PriorityQueue(Task, void, Comparator.maxCompare).init(allocator, {});
defer pq.deinit();
Line 5,473 ⟶ 8,996:
try pq.add(Task.init(1, "Solve RC tasks"));
try pq.add(Task.init(2, "Tax returns"));
try testing.expectEqual(pq.count(), 5);
std.debug.print("\n", .{});
Line 5,480 ⟶ 9,003:
while (pq.count() != 0) {
const task = pq.remove();
std.debug.print("Executing:
}
std.debug.print("\n", .{});
Line 5,488 ⟶ 9,011:
var arena = std.heap.ArenaAllocator.init(std.heap.page_allocator);
defer arena.deinit();
var pq = PriorityQueue(Task, void, Comparator.minCompare).init(allocator, {});
defer pq.deinit();
Line 5,498 ⟶ 9,020:
try pq.add(Task.init(1, "Solve RC tasks"));
try pq.add(Task.init(2, "Tax returns"));
try testing.expectEqual(pq.count(), 5);
std.debug.print("\n", .{});
Line 5,505 ⟶ 9,027:
while (pq.count() != 0) {
const task = pq.remove();
std.debug.print("Executing:
}
std.debug.print("\n", .{});
}
</syntaxhighlight>
Sample output:
<syntaxhighlight lang="zig">
$ zig test priority_queue.zig
Test [1/2] test "priority queue (max heap)"...
Line 5,531 ⟶ 9,052:
All 2 tests passed.
</syntaxhighlight>
=={{header|zkl}}==
This solution uses a [hopefully small] fixed number of priorities, each of which has an unordered list of tasks. This allows O(1) insertions, O(p) for retrievals (p is the number of priorities).
<
fcn init(numLevels=10){ // 0..numLevels, bigger # == lower priorty
var [const] queue=(1).pump(numLevels+1,List.createLong(numLevels).write,L().copy);
Line 5,554 ⟶ 9,075:
fcn walker{ state.clear().append(0,0); Walker(next) } // iterator front end
fcn toString{ "PQ(%d) items".fmt(queue.reduce(fcn(sum,q){ sum+q.len() },0)) }
}</
<
foreach x in
(T("Clear drains",3, "Feed cat",4, "Make tea",5, "Solve RC tasks",1, "Tax return",2,
Line 5,567 ⟶ 9,088:
println("ToDo list:");
foreach item in (pq){ item.println() }
pq.println();</
{{out}}
<pre>
| |||