Priority queue: Difference between revisions
Content added Content deleted
No edit summary |
GordonBGood (talk | contribs) m (Priority Qutue page fix highlighting...) |
||
Line 33: | Line 33: | ||
{{trans|Python}} |
{{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) |
minheap:heapify(&items) |
||
L !items.empty |
L !items.empty |
||
print(minheap:pop(&items))</ |
print(minheap:pop(&items))</syntaxhighlight> |
||
{{out}} |
{{out}} |
||
Line 49: | Line 49: | ||
=={{header|AArch64 Assembly}}== |
=={{header|AArch64 Assembly}}== |
||
{{works with|as|Raspberry Pi 3B version Buster 64 bits}} |
{{works with|as|Raspberry Pi 3B version Buster 64 bits}} |
||
< |
<syntaxhighlight lang=AArch64 Assembly> |
||
/* ARM assembly AARCH64 Raspberry PI 3B */ |
/* ARM assembly AARCH64 Raspberry PI 3B */ |
||
/* program priorQueue64.s */ |
/* program priorQueue64.s */ |
||
Line 421: | Line 421: | ||
/* for this file see task include a file in language AArch64 assembly */ |
/* for this file see task include a file in language AArch64 assembly */ |
||
.include "../includeARM64.inc" |
.include "../includeARM64.inc" |
||
</syntaxhighlight> |
|||
</lang> |
|||
{{Output}} |
{{Output}} |
||
<pre> |
<pre> |
||
Line 436: | Line 436: | ||
The user must type in the monitor the following command after compilation and before running the program!<pre>SET EndProg=*</pre> |
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}} |
{{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! |
INCLUDE "D2:ALLOCATE.ACT" ;from the Action! Tool Kit. You must type 'SET EndProg=*' from the monitor after compiling, but before running this program! |
||
Line 541: | Line 541: | ||
TestPop() |
TestPop() |
||
TestIsEmpty() |
TestIsEmpty() |
||
RETURN</ |
RETURN</syntaxhighlight> |
||
{{out}} |
{{out}} |
||
[https://gitlab.com/amarok8bit/action-rosetta-code/-/raw/master/images/Priority_queue.png Screenshot from Atari 8-bit computer] |
[https://gitlab.com/amarok8bit/action-rosetta-code/-/raw/master/images/Priority_queue.png Screenshot from Atari 8-bit computer] |
||
Line 564: | Line 564: | ||
Ada 2012 includes container classes for priority queues. |
Ada 2012 includes container classes for priority queues. |
||
< |
<syntaxhighlight lang=Ada>with Ada.Containers.Synchronized_Queue_Interfaces; |
||
with Ada.Containers.Unbounded_Priority_Queues; |
with Ada.Containers.Unbounded_Priority_Queues; |
||
with Ada.Strings.Unbounded; |
with Ada.Strings.Unbounded; |
||
Line 605: | Line 605: | ||
end loop; |
end loop; |
||
end; |
end; |
||
end Priority_Queues;</ |
end Priority_Queues;</syntaxhighlight> |
||
{{out}} |
{{out}} |
||
Line 612: | Line 612: | ||
=={{header|ARM Assembly}}== |
=={{header|ARM Assembly}}== |
||
{{works with|as|Raspberry Pi}} |
{{works with|as|Raspberry Pi}} |
||
< |
<syntaxhighlight lang=ARM Assembly> |
||
/* ARM assembly Raspberry PI */ |
/* ARM assembly Raspberry PI */ |
||
/* program priorqueue.s */ |
/* program priorqueue.s */ |
||
Line 1,037: | Line 1,037: | ||
pop {r2-r4} |
pop {r2-r4} |
||
bx lr @ return |
bx lr @ return |
||
</syntaxhighlight> |
|||
</lang> |
|||
{{out}} |
{{out}} |
||
<pre> |
<pre> |
||
Line 1,050: | Line 1,050: | ||
=={{header|AutoHotkey}}== |
=={{header|AutoHotkey}}== |
||
< |
<syntaxhighlight lang=AutoHotkey>;----------------------------------- |
||
PQ_TopItem(Queue,Task:=""){ ; remove and return top priority item |
PQ_TopItem(Queue,Task:=""){ ; remove and return top priority item |
||
TopPriority := PQ_TopPriority(Queue) |
TopPriority := PQ_TopPriority(Queue) |
||
Line 1,109: | Line 1,109: | ||
TopPriority := TopPriority?TopPriority:P , TopPriority := TopPriority<P?TopPriority:P |
TopPriority := TopPriority?TopPriority:P , TopPriority := TopPriority<P?TopPriority:P |
||
return, TopPriority |
return, TopPriority |
||
}</ |
}</syntaxhighlight> |
||
Examples:< |
Examples:<syntaxhighlight lang=AutoHotkey>data = |
||
( |
( |
||
3 Clear drains |
3 Clear drains |
||
Line 1,131: | Line 1,131: | ||
MsgBox, 262208,, % (Task:="Feed cat") " priority = " PQ_Check(PQ,task)"`n`n" PQ_View(PQ) |
MsgBox, 262208,, % (Task:="Feed cat") " priority = " PQ_Check(PQ,task)"`n`n" PQ_View(PQ) |
||
^Esc:: |
^Esc:: |
||
ExitApp</ |
ExitApp</syntaxhighlight> |
||
=={{header|Axiom}}== |
=={{header|Axiom}}== |
||
Axiom already has a heap domain for ordered sets. |
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: |
We define a domain for ordered key-entry pairs and then define a priority queue using the heap domain over the pairs: |
||
< |
<syntaxhighlight lang=Axiom>)abbrev Domain ORDKE OrderedKeyEntry |
||
OrderedKeyEntry(Key:OrderedSet,Entry:SetCategory): Exports == Implementation where |
OrderedKeyEntry(Key:OrderedSet,Entry:SetCategory): Exports == Implementation where |
||
Exports == OrderedSet with |
Exports == OrderedSet with |
||
Line 1,162: | Line 1,162: | ||
setelt(x:%,key:Key,entry:Entry) == |
setelt(x:%,key:Key,entry:Entry) == |
||
insert!(construct(key,entry)$S,x) |
insert!(construct(key,entry)$S,x) |
||
entry</ |
entry</syntaxhighlight>For an example:<syntaxhighlight lang=Axiom>pq := empty()$PriorityQueue(Integer,String) |
||
pq(3):="Clear drains"; |
pq(3):="Clear drains"; |
||
pq(4):="Feed cat"; |
pq(4):="Feed cat"; |
||
Line 1,168: | Line 1,168: | ||
pq(1):="Solve RC tasks"; |
pq(1):="Solve RC tasks"; |
||
pq(2):="Tax return"; |
pq(2):="Tax return"; |
||
[extract!(pq) for i in 1..#pq]</ |
[extract!(pq) for i in 1..#pq]</syntaxhighlight> |
||
{{out}} |
{{out}} |
||
<pre> |
<pre> |
||
Line 1,177: | Line 1,177: | ||
=={{header|Batch File}}== |
=={{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 |
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 |
@echo off |
||
setlocal enabledelayedexpansion |
setlocal enabledelayedexpansion |
||
Line 1,206: | Line 1,206: | ||
:next |
:next |
||
set order= %order:~-3% |
set order= %order:~-3% |
||
goto:eof</ |
goto:eof</syntaxhighlight> |
||
{{out}} |
{{out}} |
||
<pre> |
<pre> |
||
Line 1,218: | Line 1,218: | ||
=={{header|C}}== |
=={{header|C}}== |
||
Using a dynamic array as a binary heap. Stores integer priority and a character pointer. Supports push and pop. |
Using a dynamic array as a binary heap. Stores integer priority and a character pointer. Supports push and pop. |
||
< |
<syntaxhighlight lang=c>#include <stdio.h> |
||
#include <stdlib.h> |
#include <stdlib.h> |
||
Line 1,289: | Line 1,289: | ||
return 0; |
return 0; |
||
} |
} |
||
</syntaxhighlight> |
|||
</lang> |
|||
{{output}} |
{{output}} |
||
<pre>Solve RC tasks |
<pre>Solve RC tasks |
||
Line 1,298: | Line 1,298: | ||
=== Pairing heap w/ generic data types === |
=== Pairing heap w/ generic data types === |
||
header file: |
header file: |
||
<syntaxhighlight lang=C> |
|||
<lang C> |
|||
typedef struct _pq_node_t { |
typedef struct _pq_node_t { |
||
long int key; |
long int key; |
||
Line 1,317: | Line 1,317: | ||
NEW_PQ_ELE(p, k); \ |
NEW_PQ_ELE(p, k); \ |
||
*(h) = heap_merge(((pq_node_t *) (p)), *(h)) |
*(h) = heap_merge(((pq_node_t *) (p)), *(h)) |
||
</syntaxhighlight> |
|||
</lang> |
|||
implementation: |
implementation: |
||
<syntaxhighlight lang=C> |
|||
<lang C> |
|||
#include <stdlib.h> |
#include <stdlib.h> |
||
#include "pairheap.h" |
#include "pairheap.h" |
||
Line 1,360: | Line 1,360: | ||
return two_pass_merge(h->down); |
return two_pass_merge(h->down); |
||
} |
} |
||
</syntaxhighlight> |
|||
</lang> |
|||
usage: |
usage: |
||
<syntaxhighlight lang=C> |
|||
<lang C> |
|||
#include <stdio.h> |
#include <stdio.h> |
||
#include <string.h> |
#include <string.h> |
||
Line 1,399: | Line 1,399: | ||
} |
} |
||
} |
} |
||
</syntaxhighlight> |
|||
</lang> |
|||
{{Out}} |
{{Out}} |
||
<pre> |
<pre> |
||
Line 1,412: | Line 1,412: | ||
===.NET 6 solution=== |
===.NET 6 solution=== |
||
< |
<syntaxhighlight lang=csharp>using System; |
||
using System.Collections.Generic; |
using System.Collections.Generic; |
||
Line 1,444: | Line 1,444: | ||
5 Make tea |
5 Make tea |
||
*/</ |
*/</syntaxhighlight> |
||
===Pre-.NET 6 solution=== |
===Pre-.NET 6 solution=== |
||
< |
<syntaxhighlight lang=csharp>using System; |
||
namespace PriorityQueue |
namespace PriorityQueue |
||
Line 1,506: | Line 1,506: | ||
} |
} |
||
} |
} |
||
}</ |
}</syntaxhighlight> |
||
'''Min Heap Priority Queue''' |
'''Min Heap Priority Queue''' |
||
Line 1,512: | Line 1,512: | ||
{{works with|C sharp|C#|3.0+/DotNet 3.5+}} |
{{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: |
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: |
||
< |
<syntaxhighlight lang=csharp>namespace PriorityQ { |
||
using KeyT = UInt32; |
using KeyT = UInt32; |
||
using System; |
using System; |
||
Line 1,632: | Line 1,632: | ||
return toSeq(fromSeq(sq)); } |
return toSeq(fromSeq(sq)); } |
||
} |
} |
||
}</ |
}</syntaxhighlight> |
||
The above class code offers a full set of static methods and properties: |
The above class code offers a full set of static methods and properties: |
||
Line 1,654: | Line 1,654: | ||
The above code can be tested as per the page specification by the following code: |
The above code can be tested as per the page specification by the following code: |
||
< |
<syntaxhighlight lang=csharp> static void Main(string[] args) { |
||
Tuple<uint, string>[] ins = { new Tuple<uint,string>(3u, "Clear drains"), |
Tuple<uint, string>[] ins = { new Tuple<uint,string>(3u, "Clear drains"), |
||
new Tuple<uint,string>(4u, "Feed cat"), |
new Tuple<uint,string>(4u, "Feed cat"), |
||
Line 1,676: | Line 1,676: | ||
foreach (var e in MinHeapPQ<string>.toSeq(MinHeapPQ<string>.adjust((k, v) => new Tuple<uint,string>(6u - k, v), npq))) |
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(); |
Console.WriteLine(e); Console.WriteLine(); |
||
}</ |
}</syntaxhighlight> |
||
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. |
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,714: | Line 1,714: | ||
The C++ standard library contains the <code>std::priority_queue</code> opaque data structure. It implements a max-heap. |
The C++ standard library contains the <code>std::priority_queue</code> opaque data structure. It implements a max-heap. |
||
< |
<syntaxhighlight lang=cpp>#include <iostream> |
||
#include <string> |
#include <string> |
||
#include <queue> |
#include <queue> |
||
Line 1,733: | Line 1,733: | ||
return 0; |
return 0; |
||
}</ |
}</syntaxhighlight> |
||
{{out}} |
{{out}} |
||
Line 1,747: | Line 1,747: | ||
and use the heap operations to manipulate it: |
and use the heap operations to manipulate it: |
||
< |
<syntaxhighlight lang=cpp>#include <iostream> |
||
#include <string> |
#include <string> |
||
#include <vector> |
#include <vector> |
||
Line 1,776: | Line 1,776: | ||
return 0; |
return 0; |
||
}</ |
}</syntaxhighlight> |
||
{{out}} |
{{out}} |
||
Line 1,789: | Line 1,789: | ||
=={{header|Clojure}}== |
=={{header|Clojure}}== |
||
< |
<syntaxhighlight lang=clojure>user=> (use 'clojure.data.priority-map) |
||
; priority-map can be used as a priority queue |
; priority-map can be used as a priority queue |
||
Line 1,807: | Line 1,807: | ||
; Merge priority-maps together |
; Merge priority-maps together |
||
user=> (into p [["Wax Car" 4]["Paint Fence" 1]["Sand Floor" 3]]) |
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}</ |
{"Solve RC tasks" 1, "Paint Fence" 1, "Clear drains" 3, "Sand Floor" 3, "Wax Car" 4, "Feed cat" 4, "Make tea" 5}</syntaxhighlight> |
||
=={{header|CLU}}== |
=={{header|CLU}}== |
||
Line 1,817: | Line 1,817: | ||
must support the less-than operator. |
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) |
where P has lt: proctype (P,P) returns (bool) |
||
Line 1,911: | Line 1,911: | ||
stream$putl(po, int$unparse(prio) || ": " || task) |
stream$putl(po, int$unparse(prio) || ": " || task) |
||
end |
end |
||
end start_up</ |
end start_up</syntaxhighlight> |
||
{{out}} |
{{out}} |
||
<pre>1: Solve RC tasks |
<pre>1: Solve RC tasks |
||
Line 1,920: | Line 1,920: | ||
=={{header|CoffeeScript}}== |
=={{header|CoffeeScript}}== |
||
< |
<syntaxhighlight lang=coffeescript> |
||
PriorityQueue = -> |
PriorityQueue = -> |
||
# Use closure style for object creation (so no "new" required). |
# Use closure style for object creation (so no "new" required). |
||
Line 1,999: | Line 1,999: | ||
v = new_v |
v = new_v |
||
console.log "Final random element was #{v}" |
console.log "Final random element was #{v}" |
||
</syntaxhighlight> |
|||
</lang> |
|||
output |
output |
||
Line 2,012: | Line 2,012: | ||
First random element was 0.00002744467929005623 |
First random element was 0.00002744467929005623 |
||
Final random element was 0.9999718656763434 |
Final random element was 0.9999718656763434 |
||
</syntaxhighlight> |
|||
</lang> |
|||
=={{header|Common Lisp}}== |
=={{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. |
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. |
||
< |
<syntaxhighlight lang=lisp> |
||
;priority-queue's are implemented with association lists |
;priority-queue's are implemented with association lists |
||
(defun make-pq (alist) |
(defun make-pq (alist) |
||
Line 2,049: | Line 2,049: | ||
(format t "~a~&" (remove-pq a)) |
(format t "~a~&" (remove-pq a)) |
||
(format t "~a~&" a) |
(format t "~a~&" a) |
||
</syntaxhighlight> |
|||
</lang> |
|||
{{out}} |
{{out}} |
||
<pre> |
<pre> |
||
Line 2,062: | Line 2,062: | ||
=={{header|Component Pascal}}== |
=={{header|Component Pascal}}== |
||
BlackBox Component Builder |
BlackBox Component Builder |
||
< |
<syntaxhighlight lang=oberon2> |
||
MODULE PQueues; |
MODULE PQueues; |
||
IMPORT StdLog,Boxes; |
IMPORT StdLog,Boxes; |
||
Line 2,151: | Line 2,151: | ||
END PQueues. |
END PQueues. |
||
</syntaxhighlight> |
|||
</lang> |
|||
Interface extracted from the implementation |
Interface extracted from the implementation |
||
< |
<syntaxhighlight lang=oberon2> |
||
DEFINITION PQueues; |
DEFINITION PQueues; |
||
Line 2,176: | Line 2,176: | ||
END PQueues. |
END PQueues. |
||
</syntaxhighlight> |
|||
</lang> |
|||
Execute: ^Q PQueues.Test<br/> |
Execute: ^Q PQueues.Test<br/> |
||
Output: |
Output: |
||
Line 2,188: | Line 2,188: | ||
=={{header|D}}== |
=={{header|D}}== |
||
< |
<syntaxhighlight lang=d>import std.stdio, std.container, std.array, std.typecons; |
||
void main() { |
void main() { |
||
Line 2,202: | Line 2,202: | ||
heap.removeFront(); |
heap.removeFront(); |
||
} |
} |
||
}</ |
}</syntaxhighlight> |
||
{{out}} |
{{out}} |
||
<pre>Tuple!(int,string)(5, "Make tea") |
<pre>Tuple!(int,string)(5, "Make tea") |
||
Line 2,213: | Line 2,213: | ||
{{libheader| Boost.Generics.Collection}} |
{{libheader| Boost.Generics.Collection}} |
||
Boost.Generics.Collection is part of [https://github.com/MaiconSoft/DelphiBoostLib DelphiBoostLib] |
Boost.Generics.Collection is part of [https://github.com/MaiconSoft/DelphiBoostLib DelphiBoostLib] |
||
< |
<syntaxhighlight lang=Delphi>program Priority_queue; |
||
{$APPTYPE CONSOLE} |
{$APPTYPE CONSOLE} |
||
Line 2,230: | Line 2,230: | ||
with Queue.DequeueEx do |
with Queue.DequeueEx do |
||
Writeln(Priority, ', ', value); |
Writeln(Priority, ', ', value); |
||
end.</ |
end.</syntaxhighlight> |
||
{{out}} |
{{out}} |
||
<pre>1, Solve RC tasks |
<pre>1, Solve RC tasks |
||
Line 2,240: | Line 2,240: | ||
=={{header|EchoLisp}}== |
=={{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. |
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. |
||
< |
<syntaxhighlight lang=lisp> |
||
(lib 'tree) |
(lib 'tree) |
||
(define tasks (make-bin-tree 3 "Clear drains")) |
(define tasks (make-bin-tree 3 "Clear drains")) |
||
Line 2,259: | Line 2,259: | ||
(bin-tree-pop-last tasks) → (4 . "Feed 🐡") |
(bin-tree-pop-last tasks) → (4 . "Feed 🐡") |
||
; etc. |
; etc. |
||
</syntaxhighlight> |
|||
</lang> |
|||
=={{header|Elixir}}== |
=={{header|Elixir}}== |
||
{{trans|Erlang}} |
{{trans|Erlang}} |
||
< |
<syntaxhighlight lang=elixir>defmodule Priority do |
||
def create, do: :gb_trees.empty |
def create, do: :gb_trees.empty |
||
Line 2,292: | Line 2,292: | ||
end |
end |
||
Priority.task</ |
Priority.task</syntaxhighlight> |
||
{{out}} |
{{out}} |
||
Line 2,306: | Line 2,306: | ||
=={{header|Erlang}}== |
=={{header|Erlang}}== |
||
Using built in gb_trees module, with the suggested interface for this task. |
Using built in gb_trees module, with the suggested interface for this task. |
||
< |
<syntaxhighlight lang=Erlang> |
||
-module( priority_queue ). |
-module( priority_queue ). |
||
Line 2,335: | Line 2,335: | ||
io:fwrite( "top priority: ~p~n", [Element] ), |
io:fwrite( "top priority: ~p~n", [Element] ), |
||
New_queue. |
New_queue. |
||
</syntaxhighlight> |
|||
</lang> |
|||
{{out}} |
{{out}} |
||
<pre> |
<pre> |
||
Line 2,355: | Line 2,355: | ||
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: |
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: |
||
< |
<syntaxhighlight lang=fsharp>[<RequireQualifiedAccess>] |
||
module PriorityQ = |
module PriorityQ = |
||
Line 2,457: | Line 2,457: | ||
let sort sq = sq |> fromSeq |> toSeq |
let sort sq = sq |> fromSeq |> toSeq |
||
let adjust f pq = pq |> toSeq |> Seq.map (fun (k, v) -> f k v) |> fromSeq</ |
let adjust f pq = pq |> toSeq |> Seq.map (fun (k, v) -> f k v) |> fromSeq</syntaxhighlight> |
||
"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. |
"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 2,470: | Line 2,470: | ||
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: |
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: |
||
< |
<syntaxhighlight lang=fsharp>[<RequireQualifiedAccess>] |
||
module PriorityQ = |
module PriorityQ = |
||
Line 2,602: | Line 2,602: | ||
let toSeq pq = Seq.unfold popMin pq |
let toSeq pq = Seq.unfold popMin pq |
||
let sort sq = sq |> fromSeq |> toSeq</ |
let sort sq = sq |> fromSeq |> toSeq</syntaxhighlight> |
||
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. |
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 2,613: | Line 2,613: | ||
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: |
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: |
||
< |
<syntaxhighlight lang=fsharp>[<RequireQualifiedAccess>] |
||
module PriorityQ = |
module PriorityQ = |
||
Line 2,696: | Line 2,696: | ||
let toSeq pq = Seq.unfold popMin pq |
let toSeq pq = Seq.unfold popMin pq |
||
let sort sq = sq |> fromSeq |> toSeq</ |
let sort sq = sq |> fromSeq |> toSeq</syntaxhighlight> |
||
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. |
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: |
All of the above codes can be tested under the F# REPL using the following: |
||
< |
<syntaxhighlight lang=fsharp>> let testseq = [| (3u, "Clear drains"); |
||
(4u, "Feed cat"); |
(4u, "Feed cat"); |
||
(5u, "Make tea"); |
(5u, "Make tea"); |
||
Line 2,719: | Line 2,719: | ||
printfn "" |
printfn "" |
||
testpq |> MinHeap.adjust (fun k v -> uint32 (MinHeap.size testpq) - k, v) |
testpq |> MinHeap.adjust (fun k v -> uint32 (MinHeap.size testpq) - k, v) |
||
|> MinHeap.toSeq |> Seq.iter (printfn "%A") // test adjust;;</ |
|> MinHeap.toSeq |> Seq.iter (printfn "%A") // test adjust;;</syntaxhighlight> |
||
to produce the following output: |
to produce the following output: |
||
Line 2,765: | Line 2,765: | ||
=={{header|Factor}}== |
=={{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). |
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). |
||
< |
<syntaxhighlight lang=factor><min-heap> [ { |
||
{ 3 "Clear drains" } |
{ 3 "Clear drains" } |
||
{ 4 "Feed cat" } |
{ 4 "Feed cat" } |
||
Line 2,774: | Line 2,774: | ||
] [ |
] [ |
||
[ print ] slurp-heap |
[ print ] slurp-heap |
||
] bi</ |
] bi</syntaxhighlight> |
||
output: |
output: |
||
< |
<syntaxhighlight lang=factor>Solve RC tasks |
||
Tax return |
Tax return |
||
Clear drains |
Clear drains |
||
Feed cat |
Feed cat |
||
Make tea</ |
Make tea</syntaxhighlight> |
||
=={{header|Forth}}== |
=={{header|Forth}}== |
||
{{works with|gforth|0.7.3}} |
{{works with|gforth|0.7.3}} |
||
<br> |
<br> |
||
< |
<syntaxhighlight lang=forth>#! /usr/bin/gforth |
||
\ Priority queue |
\ Priority queue |
||
Line 2,970: | Line 2,970: | ||
>r 2 s" Tax return" r> >queue |
>r 2 s" Tax return" r> >queue |
||
drain-queue</ |
drain-queue</syntaxhighlight> |
||
{{out}} |
{{out}} |
||
Line 2,982: | Line 2,982: | ||
=={{header|Fortran}}== |
=={{header|Fortran}}== |
||
< |
<syntaxhighlight lang=Fortran>module priority_queue_mod |
||
implicit none |
implicit none |
||
Line 3,083: | Line 3,083: | ||
! 2 -> Tax return |
! 2 -> Tax return |
||
! 1 -> Solve RC tasks |
! 1 -> Solve RC tasks |
||
</syntaxhighlight> |
|||
</lang> |
|||
=={{header|FreeBASIC}}== |
=={{header|FreeBASIC}}== |
||
{{trans|VBA}} |
{{trans|VBA}} |
||
< |
<syntaxhighlight lang=freebasic>Type Tupla |
||
Prioridad As Integer |
Prioridad As Integer |
||
Tarea As String |
Tarea As String |
||
Line 3,173: | Line 3,173: | ||
Print t.Prioridad; " "; t.Tarea |
Print t.Prioridad; " "; t.Tarea |
||
Loop |
Loop |
||
Sleep</ |
Sleep</syntaxhighlight> |
||
{{out}} |
{{out}} |
||
<pre> |
<pre> |
||
Line 3,181: | Line 3,181: | ||
=={{header|FunL}}== |
=={{header|FunL}}== |
||
< |
<syntaxhighlight lang=funl>import util.ordering |
||
native scala.collection.mutable.PriorityQueue |
native scala.collection.mutable.PriorityQueue |
||
Line 3,202: | Line 3,202: | ||
while not q.isEmpty() |
while not q.isEmpty() |
||
println( q.dequeue() )</ |
println( q.dequeue() )</syntaxhighlight> |
||
{{out}} |
{{out}} |
||
Line 3,217: | Line 3,217: | ||
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. |
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. |
||
< |
<syntaxhighlight lang=go>package main |
||
import ( |
import ( |
||
Line 3,259: | Line 3,259: | ||
fmt.Println(heap.Pop(pq)) |
fmt.Println(heap.Pop(pq)) |
||
} |
} |
||
}</ |
}</syntaxhighlight> |
||
output: |
output: |
||
Line 3,272: | Line 3,272: | ||
=={{header|Groovy}}== |
=={{header|Groovy}}== |
||
Groovy can use the built in java PriorityQueue class |
Groovy can use the built in java PriorityQueue class |
||
< |
<syntaxhighlight lang=groovy>import groovy.transform.Canonical |
||
@Canonical |
@Canonical |
||
Line 3,289: | Line 3,289: | ||
while (!empty) { println remove() } |
while (!empty) { println remove() } |
||
}</ |
}</syntaxhighlight> |
||
Output: |
Output: |
||
Line 3,300: | Line 3,300: | ||
=={{header|Haskell}}== |
=={{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. |
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. |
||
< |
<syntaxhighlight lang=haskell>import Data.PQueue.Prio.Min |
||
main = print (toList (fromList [(3, "Clear drains"),(4, "Feed cat"),(5, "Make tea"),(1, "Solve RC tasks"), (2, "Tax return")]))</ |
main = print (toList (fromList [(3, "Clear drains"),(4, "Feed cat"),(5, "Make tea"),(1, "Solve RC tasks"), (2, "Tax return")]))</syntaxhighlight> |
||
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. |
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. |
||
< |
<syntaxhighlight lang=haskell>import qualified Data.Set as S |
||
main = print (S.toList (S.fromList [(3, "Clear drains"),(4, "Feed cat"),(5, "Make tea"),(1, "Solve RC tasks"), (2, "Tax return")]))</ |
main = print (S.toList (S.fromList [(3, "Clear drains"),(4, "Feed cat"),(5, "Make tea"),(1, "Solve RC tasks"), (2, "Tax return")]))</syntaxhighlight> |
||
{{out}} |
{{out}} |
||
<pre>[(1,"Solve RC tasks"),(2,"Tax return"),(3,"Clear drains"),(4,"Feed cat"),(5,"Make tea")]</pre> |
<pre>[(1,"Solve RC tasks"),(2,"Tax return"),(3,"Clear drains"),(4,"Feed cat"),(5,"Make tea")]</pre> |
||
Alternatively, a homemade min heap implementation: |
Alternatively, a homemade min heap implementation: |
||
< |
<syntaxhighlight lang=haskell>data MinHeap a = Nil | MinHeap { v::a, cnt::Int, l::MinHeap a, r::MinHeap a } |
||
deriving (Show, Eq) |
deriving (Show, Eq) |
||
Line 3,354: | Line 3,354: | ||
(5, "Make tea"), |
(5, "Make tea"), |
||
(1, "Solve RC tasks"), |
(1, "Solve RC tasks"), |
||
(2, "Tax return")]</ |
(2, "Tax return")]</syntaxhighlight> |
||
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: |
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: |
||
< |
<syntaxhighlight lang=haskell>data MinHeap kv = MinHeapEmpty |
||
| MinHeapLeaf !kv |
| MinHeapLeaf !kv |
||
| MinHeapNode !kv {-# UNPACK #-} !Int !(MinHeap a) !(MinHeap a) |
| MinHeapNode !kv {-# UNPACK #-} !Int !(MinHeap a) !(MinHeap a) |
||
Line 3,480: | Line 3,480: | ||
sortPQ :: (Ord kv) => [kv] -> [kv] |
sortPQ :: (Ord kv) => [kv] -> [kv] |
||
sortPQ ls = toListPQ $ fromListPQ ls</ |
sortPQ ls = toListPQ $ fromListPQ ls</syntaxhighlight> |
||
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: |
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: |
||
< |
<syntaxhighlight lang=haskell>data PriorityQ k v = Mt |
||
| Br !k v !(PriorityQ k v) !(PriorityQ k v) |
| Br !k v !(PriorityQ k v) !(PriorityQ k v) |
||
deriving (Eq, Ord, Read, Show) |
deriving (Eq, Ord, Read, Show) |
||
Line 3,586: | Line 3,586: | ||
sortPQ :: (Ord k) => [(k, v)] -> [(k, v)] |
sortPQ :: (Ord k) => [(k, v)] -> [(k, v)] |
||
sortPQ ls = toListPQ $ fromListPQ ls</ |
sortPQ ls = toListPQ $ fromListPQ ls</syntaxhighlight> |
||
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. |
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 3,595: | Line 3,595: | ||
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): |
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): |
||
< |
<syntaxhighlight lang=haskell>testList = [ (3, "Clear drains"), |
||
(4, "Feed cat"), |
(4, "Feed cat"), |
||
(5, "Make tea"), |
(5, "Make tea"), |
||
Line 3,612: | Line 3,612: | ||
mapM_ print $ toListPQ $ mergePQ testPQ testPQ |
mapM_ print $ toListPQ $ mergePQ testPQ testPQ |
||
putStrLn "" -- test adjust |
putStrLn "" -- test adjust |
||
mapM_ print $ toListPQ $ adjustPQ (\x y -> (x * (-1), y)) testPQ</ |
mapM_ print $ toListPQ $ adjustPQ (\x y -> (x * (-1), y)) testPQ</syntaxhighlight> |
||
has the output as follows: |
has the output as follows: |
||
Line 3,658: | Line 3,658: | ||
<tt>Closure</tt> is used to allow the queue to order lists based on |
<tt>Closure</tt> is used to allow the queue to order lists based on |
||
their first element. The solution only works in Unicon. |
their first element. The solution only works in Unicon. |
||
< |
<syntaxhighlight lang=Unicon>import Utils # For Closure class |
||
import Collections # For Heap (dense priority queue) class |
import Collections # For Heap (dense priority queue) class |
||
Line 3,671: | Line 3,671: | ||
while task := pq.get() do write(task[1]," -> ",task[2]) |
while task := pq.get() do write(task[1]," -> ",task[2]) |
||
end |
end |
||
</syntaxhighlight> |
|||
</lang> |
|||
Output when run: |
Output when run: |
||
<pre> |
<pre> |
||
Line 3,685: | Line 3,685: | ||
Implementation: |
Implementation: |
||
< |
<syntaxhighlight lang=j>coclass 'priorityQueue' |
||
PRI=: '' |
PRI=: '' |
||
Line 3,707: | Line 3,707: | ||
QUE=: y}.QUE |
QUE=: y}.QUE |
||
r |
r |
||
)</ |
)</syntaxhighlight> |
||
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. |
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 3,713: | Line 3,713: | ||
Example: |
Example: |
||
< |
<syntaxhighlight lang=j> Q=: conew'priorityQueue' |
||
3 4 5 1 2 insert__Q 'clear drains';'feed cat';'make tea';'solve rc task';'tax return' |
3 4 5 1 2 insert__Q 'clear drains';'feed cat';'make tea';'solve rc task';'tax return' |
||
>topN__Q 1 |
>topN__Q 1 |
||
Line 3,721: | Line 3,721: | ||
clear drains |
clear drains |
||
tax return |
tax return |
||
solve rc task</ |
solve rc task</syntaxhighlight> |
||
=={{header|Java}}== |
=={{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. |
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. |
||
< |
<syntaxhighlight lang=java>import java.util.PriorityQueue; |
||
class Task implements Comparable<Task> { |
class Task implements Comparable<Task> { |
||
Line 3,756: | Line 3,756: | ||
System.out.println(pq.remove()); |
System.out.println(pq.remove()); |
||
} |
} |
||
}</ |
}</syntaxhighlight> |
||
{{out}} |
{{out}} |
||
<pre> |
<pre> |
||
Line 3,771: | Line 3,771: | ||
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. |
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.< |
We assume that if an item of a given priority is already in the priority queue, there is no need to add it again.<syntaxhighlight lang=jq># In the following, pq stands for "priority queue". |
||
# Add an item with the given priority (an integer, |
# Add an item with the given priority (an integer, |
||
Line 3,820: | Line 3,820: | ||
def prioritize: |
def prioritize: |
||
. as $list | {} | pq_add_tasks($list) | pq_pop_tasks ; |
. as $list | {} | pq_add_tasks($list) | pq_pop_tasks ; |
||
</syntaxhighlight> |
|||
</lang> |
|||
The specific task: |
The specific task: |
||
<syntaxhighlight lang=jq> |
|||
<lang jq> |
|||
[ [3, "Clear drains"], |
[ [3, "Clear drains"], |
||
[4, "Feed cat"], |
[4, "Feed cat"], |
||
Line 3,829: | Line 3,829: | ||
[2, "Tax return"] |
[2, "Tax return"] |
||
] | prioritize |
] | prioritize |
||
</syntaxhighlight> |
|||
</lang> |
|||
{{Out}} |
{{Out}} |
||
"Solve RC tasks" |
"Solve RC tasks" |
||
Line 3,839: | Line 3,839: | ||
=={{header|Julia}}== |
=={{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. |
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 |
using Base.Collections |
||
Line 3,858: | Line 3,858: | ||
dequeue!(task) |
dequeue!(task) |
||
println(" \"", t, "\" has priority ", p) |
println(" \"", t, "\" has priority ", p) |
||
end</ |
end</syntaxhighlight> |
||
{{out}} |
{{out}} |
||
Line 3,871: | Line 3,871: | ||
=={{header|Kotlin}}== |
=={{header|Kotlin}}== |
||
{{trans|Java}} |
{{trans|Java}} |
||
< |
<syntaxhighlight lang=scala>import java.util.PriorityQueue |
||
internal data class Task(val priority: Int, val name: String) : Comparable<Task> { |
internal data class Task(val priority: Int, val name: String) : Comparable<Task> { |
||
Line 3,890: | Line 3,890: | ||
"Tax return" priority 2)) |
"Tax return" priority 2)) |
||
while (q.any()) println(q.remove()) |
while (q.any()) println(q.remove()) |
||
}</ |
}</syntaxhighlight> |
||
{{out}} |
{{out}} |
||
<pre>Task(priority=1, name=Solve RC tasks) |
<pre>Task(priority=1, name=Solve RC tasks) |
||
Line 3,899: | Line 3,899: | ||
=={{header|Lasso}}== |
=={{header|Lasso}}== |
||
< |
<syntaxhighlight lang=lasso>define priorityQueue => type { |
||
data |
data |
||
store = map, |
store = map, |
||
Line 3,957: | Line 3,957: | ||
while(not #test->isEmpty) => { |
while(not #test->isEmpty) => { |
||
stdout(#test->pop) |
stdout(#test->pop) |
||
}</ |
}</syntaxhighlight> |
||
{{out}} |
{{out}} |
||
Line 3,966: | Line 3,966: | ||
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. |
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. |
||
< |
<syntaxhighlight lang=lua>PriorityQueue = { |
||
__index = { |
__index = { |
||
put = function(self, p, v) |
put = function(self, p, v) |
||
Line 4,015: | Line 4,015: | ||
for prio, task in pq.pop, pq do |
for prio, task in pq.pop, pq do |
||
print(string.format("Popped: %d - %s", prio, task)) |
print(string.format("Popped: %d - %s", prio, task)) |
||
end</ |
end</syntaxhighlight> |
||
'''Output:''' |
'''Output:''' |
||
Line 4,032: | Line 4,032: | ||
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. |
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. |
||
< |
<syntaxhighlight lang=lua>-- Use socket.gettime() for benchmark measurements |
||
-- since it has millisecond precision on most systems |
-- since it has millisecond precision on most systems |
||
local socket = require("socket") |
local socket = require("socket") |
||
Line 4,071: | Line 4,071: | ||
end |
end |
||
print(string.format("Elapsed: %.3f ms.", (socket.gettime() - start) * 1000))</ |
print(string.format("Elapsed: %.3f ms.", (socket.gettime() - start) * 1000))</syntaxhighlight> |
||
=={{header|M2000 Interpreter}}== |
=={{header|M2000 Interpreter}}== |
||
Line 4,077: | Line 4,077: | ||
===Using unordered array=== |
===Using unordered array=== |
||
< |
<syntaxhighlight lang=M2000 Interpreter> |
||
Module UnOrderedArray { |
Module UnOrderedArray { |
||
Class PriorityQueue { |
Class PriorityQueue { |
||
Line 4,194: | Line 4,194: | ||
} |
} |
||
UnOrderedArray |
UnOrderedArray |
||
</syntaxhighlight> |
|||
</lang> |
|||
===Using a stack with arrays as elements=== |
===Using a stack with arrays as elements=== |
||
Every insertion push item using binary search in proper position. Pop is very fast. |
Every insertion push item using binary search in proper position. Pop is very fast. |
||
< |
<syntaxhighlight lang=M2000 Interpreter> |
||
Module PriorityQueue { |
Module PriorityQueue { |
||
a= ( (3, "Clear drains"), (4 ,"Feed cat"), ( 5 , "Make tea"), ( 1 ,"Solve RC tasks"), ( 2 , "Tax return")) |
a= ( (3, "Clear drains"), (4 ,"Feed cat"), ( 5 , "Make tea"), ( 1 ,"Solve RC tasks"), ( 2 , "Tax return")) |
||
Line 4,260: | Line 4,260: | ||
PriorityQueue |
PriorityQueue |
||
</syntaxhighlight> |
|||
</lang> |
|||
===Using a stack with Groups as elements=== |
===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. |
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> |
||
Module PriorityQueueForGroups { |
Module PriorityQueueForGroups { |
||
class obj { |
class obj { |
||
Line 4,323: | Line 4,323: | ||
} |
} |
||
PriorityQueueForGroups |
PriorityQueueForGroups |
||
</syntaxhighlight> |
|||
</lang> |
|||
=={{header|Mathematica}}/{{header|Wolfram Language}}== |
=={{header|Mathematica}}/{{header|Wolfram Language}}== |
||
< |
<syntaxhighlight lang=mathematica>push = Function[{queue, priority, item}, |
||
queue = SortBy[Append[queue, {priority, item}], First], HoldFirst]; |
queue = SortBy[Append[queue, {priority, item}], First], HoldFirst]; |
||
pop = Function[queue, |
pop = Function[queue, |
||
Line 4,335: | Line 4,335: | ||
If[Length@queue == 0, Null, Max[queue[[All, 1]]]], HoldFirst]; |
If[Length@queue == 0, Null, Max[queue[[All, 1]]]], HoldFirst]; |
||
merge = Function[{queue1, queue2}, |
merge = Function[{queue1, queue2}, |
||
SortBy[Join[queue1, queue2], First], HoldAll];</ |
SortBy[Join[queue1, queue2], First], HoldAll];</syntaxhighlight> |
||
Example: |
Example: |
||
< |
<syntaxhighlight lang=mathematica>queue = {}; |
||
push[queue, 3, "Clear drains"]; |
push[queue, 3, "Clear drains"]; |
||
push[queue, 4, "Feed cat"]; |
push[queue, 4, "Feed cat"]; |
||
Line 4,349: | Line 4,349: | ||
queue1 = {}; |
queue1 = {}; |
||
push[queue1, 6, "Drink tea"]; |
push[queue1, 6, "Drink tea"]; |
||
Print[merge[queue, queue1]];</ |
Print[merge[queue, queue1]];</syntaxhighlight> |
||
Output: |
Output: |
||
Line 4,360: | Line 4,360: | ||
=={{header|Maxima}}== |
=={{header|Maxima}}== |
||
< |
<syntaxhighlight lang=maxima>/* Naive implementation using a sorted list of pairs [key, [item[1], ..., item[n]]]. |
||
The key may be any number (integer or not). Items are extracted in FIFO order. */ |
The key may be any number (integer or not). Items are extracted in FIFO order. */ |
||
Line 4,441: | Line 4,441: | ||
"call friends" |
"call friends" |
||
"serve cider" |
"serve cider" |
||
"savour !"</ |
"savour !"</syntaxhighlight> |
||
=={{header|Mercury}}== |
=={{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. |
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. |
||
< |
<syntaxhighlight lang=mercury>:- module test_pqueue. |
||
:- interface. |
:- interface. |
||
Line 4,480: | Line 4,480: | ||
main(!IO) :- |
main(!IO) :- |
||
build_pqueue(pqueue.init, PQO), |
build_pqueue(pqueue.init, PQO), |
||
display_pqueue(PQO, !IO).</ |
display_pqueue(PQO, !IO).</syntaxhighlight> |
||
=={{header|Nim}}== |
=={{header|Nim}}== |
||
{{trans|C}} |
{{trans|C}} |
||
< |
<syntaxhighlight lang=nim>type |
||
PriElem[T] = tuple |
PriElem[T] = tuple |
||
data: T |
data: T |
||
Line 4,543: | Line 4,543: | ||
while p.count > 0: |
while p.count > 0: |
||
echo p.pop()</ |
echo p.pop()</syntaxhighlight> |
||
{{out}} |
{{out}} |
||
<pre>(data: Solve RC tasks, pri: 1) |
<pre>(data: Solve RC tasks, pri: 1) |
||
Line 4,552: | Line 4,552: | ||
''' Using Nim HeapQueue''' |
''' Using Nim HeapQueue''' |
||
< |
<syntaxhighlight lang=Nim>import HeapQueue |
||
var pq = newHeapQueue[(int, string)]() |
var pq = newHeapQueue[(int, string)]() |
||
Line 4,563: | Line 4,563: | ||
while pq.len() > 0: |
while pq.len() > 0: |
||
echo pq.pop()</ |
echo pq.pop()</syntaxhighlight> |
||
{{out}} |
{{out}} |
||
Line 4,573: | Line 4,573: | ||
''' Using Nim tables''' |
''' Using Nim tables''' |
||
< |
<syntaxhighlight lang=Nim>import tables |
||
var |
var |
||
Line 4,590: | Line 4,590: | ||
pq.del(i) |
pq.del(i) |
||
main()</ |
main()</syntaxhighlight> |
||
{{out}} |
{{out}} |
||
<pre>1: Solve RC tasks |
<pre>1: Solve RC tasks |
||
Line 4,602: | Line 4,602: | ||
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. |
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. |
||
< |
<syntaxhighlight lang=objc>#import <Foundation/Foundation.h> |
||
const void *PQRetain(CFAllocatorRef allocator, const void *ptr) { |
const void *PQRetain(CFAllocatorRef allocator, const void *ptr) { |
||
Line 4,665: | Line 4,665: | ||
} |
} |
||
return 0; |
return 0; |
||
}</ |
}</syntaxhighlight> |
||
log: |
log: |
||
Line 4,680: | Line 4,680: | ||
Holger Arnold's [http://holgerarnold.net/software/ OCaml base library] provides a [http://holgerarnold.net/software/ocaml/doc/base/PriorityQueue.html PriorityQueue] module. |
Holger Arnold's [http://holgerarnold.net/software/ OCaml base library] provides a [http://holgerarnold.net/software/ocaml/doc/base/PriorityQueue.html PriorityQueue] module. |
||
< |
<syntaxhighlight lang=ocaml>module PQ = Base.PriorityQueue |
||
let () = |
let () = |
||
Line 4,696: | Line 4,696: | ||
PQ.remove_first pq; |
PQ.remove_first pq; |
||
print_endline task |
print_endline task |
||
done</ |
done</syntaxhighlight> |
||
testing: |
testing: |
||
Line 4,708: | Line 4,708: | ||
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). |
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+}} |
{{works with|OCaml|4.02+}} |
||
< |
<syntaxhighlight lang=ocaml>module PQSet = Set.Make |
||
(struct |
(struct |
||
type t = int * string (* pair of priority and task name *) |
type t = int * string (* pair of priority and task name *) |
||
Line 4,729: | Line 4,729: | ||
aux (PQSet.remove task pq') |
aux (PQSet.remove task pq') |
||
end |
end |
||
in aux pq</ |
in aux pq</syntaxhighlight> |
||
{{out}} |
{{out}} |
||
<pre> |
<pre> |
||
Line 4,905: | Line 4,905: | ||
(buffer empty) |
(buffer empty) |
||
*/ |
*/ |
||
</syntaxhighlight> |
|||
</lang> |
|||
=={{header|Pascal}}== |
=={{header|Pascal}}== |
||
< |
<syntaxhighlight lang=Pascal> |
||
program PriorityQueueTest; |
program PriorityQueueTest; |
||
Line 4,983: | Line 4,983: | ||
Queue.free; |
Queue.free; |
||
end. |
end. |
||
</syntaxhighlight> |
|||
</lang> |
|||
=={{header|Perl}}== |
=={{header|Perl}}== |
||
There are a few implementations on CPAN. Following uses <code>Heap::Priority</code>[http://search.cpan.org/~fwojcik/Heap-Priority-0.11/Priority.pm] |
There are a few implementations on CPAN. Following uses <code>Heap::Priority</code>[http://search.cpan.org/~fwojcik/Heap-Priority-0.11/Priority.pm] |
||
< |
<syntaxhighlight lang=perl>use 5.10.0; |
||
use strict; |
use strict; |
||
use Heap::Priority; |
use Heap::Priority; |
||
Line 5,000: | Line 5,000: | ||
["Tax return", 2]; |
["Tax return", 2]; |
||
say while ($_ = $h->pop);</ |
say while ($_ = $h->pop);</syntaxhighlight>output<lang>Make tea |
||
Feed cat |
Feed cat |
||
Clear drains |
Clear drains |
||
Tax return |
Tax return |
||
Solve RC tasks</ |
Solve RC tasks</syntaxhighlight> |
||
===IBM card sorter version=== |
===IBM card sorter version=== |
||
< |
<syntaxhighlight lang=perl>#!/usr/bin/perl |
||
use strict; # https://rosettacode.org/wiki/Priority_queue |
use strict; # https://rosettacode.org/wiki/Priority_queue |
||
Line 5,038: | Line 5,038: | ||
delete $bins[-1] while @bins and @{ $bins[-1] // [] } == 0; |
delete $bins[-1] while @bins and @{ $bins[-1] // [] } == 0; |
||
shift @{ $bins[-1] // [] }; |
shift @{ $bins[-1] // [] }; |
||
}</ |
}</syntaxhighlight> |
||
{{out}} |
{{out}} |
||
<pre> |
<pre> |
||
Line 5,052: | Line 5,052: | ||
Dictionary based solution. Allows duplicate tasks, FIFO within priority, and uses a callback-style method of performing tasks.<br> |
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. |
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;">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;">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> |
||
Line 5,108: | Line 5,108: | ||
<span style="color: #0000FF;">?</span><span style="color: #008000;">"==="</span> |
<span style="color: #0000FF;">?</span><span style="color: #008000;">"==="</span> |
||
<span style="color: #000000;">list_tasks</span><span style="color: #0000FF;">()</span> |
<span style="color: #000000;">list_tasks</span><span style="color: #0000FF;">()</span> |
||
<!--</ |
<!--</syntaxhighlight>--> |
||
{{out}} |
{{out}} |
||
<pre> |
<pre> |
||
Line 5,128: | Line 5,128: | ||
(I needed this for [[Taxicab_numbers#Phix|Taxicab_numbers]])<br> |
(I needed this for [[Taxicab_numbers#Phix|Taxicab_numbers]])<br> |
||
The bulk of this code now forms builtins/pqueue.e (not properly documented at the time, but now is, see below) |
The bulk of this code now forms builtins/pqueue.e (not properly documented at the time, but now is, see below) |
||
<!--< |
<!--<syntaxhighlight lang=Phix>(phixonline)--> |
||
<span style="color: #008080;">with</span> <span style="color: #008080;">javascript_semantics</span> |
<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: #004080;">sequence</span> <span style="color: #000000;">pq</span> <span style="color: #0000FF;">=</span> <span style="color: #0000FF;">{}</span> |
||
Line 5,185: | Line 5,185: | ||
<span style="color: #0000FF;">?</span><span style="color: #000000;">pqPop</span><span style="color: #0000FF;">()</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> |
<span style="color: #008080;">end</span> <span style="color: #008080;">while</span> |
||
<!--</ |
<!--</syntaxhighlight>--> |
||
{{out}} |
{{out}} |
||
The optional initial set_rand() makes it slightly more amusing.<br> |
The optional initial set_rand() makes it slightly more amusing.<br> |
||
Line 5,204: | Line 5,204: | ||
=== builtin === |
=== builtin === |
||
If you omit MAX_HEAP or (same thing) specify MIN_HEAP, the output'll be 1..5 |
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;">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: #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> |
||
Line 5,218: | Line 5,218: | ||
<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: #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> |
<span style="color: #008080;">end</span> <span style="color: #008080;">while</span> |
||
<!--</ |
<!--</syntaxhighlight>--> |
||
{{out}} |
{{out}} |
||
<pre> |
<pre> |
||
Line 5,229: | Line 5,229: | ||
=={{header|Phixmonti}}== |
=={{header|Phixmonti}}== |
||
< |
<syntaxhighlight lang=Phixmonti>/# Rosetta Code problem: http://rosettacode.org/wiki/Priority_queue |
||
by Galileo, 05/2022 #/ |
by Galileo, 05/2022 #/ |
||
Line 5,237: | Line 5,237: | ||
( 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 |
( 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 |
sort pop swap print pstack |
||
</syntaxhighlight> |
|||
</lang> |
|||
{{out}} |
{{out}} |
||
<pre>[1, "Solve RC tasks"] |
<pre>[1, "Solve RC tasks"] |
||
Line 5,247: | Line 5,247: | ||
{{works with|PHP|5.3+}} |
{{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. |
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. |
||
< |
<syntaxhighlight lang=php><?php |
||
$pq = new SplPriorityQueue; |
$pq = new SplPriorityQueue; |
||
Line 5,263: | Line 5,263: | ||
print_r($pq->extract()); |
print_r($pq->extract()); |
||
} |
} |
||
?></ |
?></syntaxhighlight> |
||
Output: |
Output: |
||
Line 5,296: | Line 5,296: | ||
{{works with|PHP|5.3+}} |
{{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. |
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. |
||
< |
<syntaxhighlight lang=php><?php |
||
$pq = new SplMinHeap; |
$pq = new SplMinHeap; |
||
Line 5,308: | Line 5,308: | ||
print_r($pq->extract()); |
print_r($pq->extract()); |
||
} |
} |
||
?></ |
?></syntaxhighlight> |
||
Output: |
Output: |
||
Line 5,341: | Line 5,341: | ||
=={{header|Picat}}== |
=={{header|Picat}}== |
||
Picat has built-in support for min and max heaps. |
Picat has built-in support for min and max heaps. |
||
< |
<syntaxhighlight lang=Picat>main => |
||
Tasks = [[3,"Clear drains"], |
Tasks = [[3,"Clear drains"], |
||
[4,"Feed cat"], |
[4,"Feed cat"], |
||
Line 5,357: | Line 5,357: | ||
nl, |
nl, |
||
println("Pop the elements from the queue:"), |
println("Pop the elements from the queue:"), |
||
println([Heap.heap_pop() : _ in 1..Heap.heap_size]).</ |
println([Heap.heap_pop() : _ in 1..Heap.heap_size]).</syntaxhighlight> |
||
{{out}} |
{{out}} |
||
Line 5,373: | Line 5,373: | ||
The heaps creation functions can take the task list as argument: |
The heaps creation functions can take the task list as argument: |
||
< |
<syntaxhighlight lang=Picat> Tasks = [[3,"Clear drains"], |
||
[4,"Feed cat"], |
[4,"Feed cat"], |
||
[5,"Make tea"], |
[5,"Make tea"], |
||
Line 5,379: | Line 5,379: | ||
[2,"Tax return"]], |
[2,"Tax return"]], |
||
Heap = new_min_heap(Tasks), |
Heap = new_min_heap(Tasks), |
||
println([Heap.heap_pop() : _ in 1..Heap.heap_size]).</ |
println([Heap.heap_pop() : _ in 1..Heap.heap_size]).</syntaxhighlight> |
||
=={{header|PicoLisp}}== |
=={{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. |
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. |
||
< |
<syntaxhighlight lang=PicoLisp># Insert item into priority queue |
||
(de insertPQ (Queue Prio Item) |
(de insertPQ (Queue Prio Item) |
||
(idx Queue (cons Prio Item) T) ) |
(idx Queue (cons Prio Item) T) ) |
||
Line 5,401: | Line 5,401: | ||
# Merge second queue into first |
# Merge second queue into first |
||
(de mergePQ (Queue1 Queue2) |
(de mergePQ (Queue1 Queue2) |
||
(balance Queue1 (sort (conc (idx Queue1) (idx Queue2)))) )</ |
(balance Queue1 (sort (conc (idx Queue1) (idx Queue2)))) )</syntaxhighlight> |
||
Test: |
Test: |
||
< |
<syntaxhighlight lang=PicoLisp># Two priority queues |
||
(off Pq1 Pq2) |
(off Pq1 Pq2) |
||
Line 5,420: | Line 5,420: | ||
# Remove and print all items from first queue |
# Remove and print all items from first queue |
||
(while Pq1 |
(while Pq1 |
||
(println (removePQ 'Pq1)) )</ |
(println (removePQ 'Pq1)) )</syntaxhighlight> |
||
Output: |
Output: |
||
<pre>(Solve RC tasks) |
<pre>(Solve RC tasks) |
||
Line 5,428: | Line 5,428: | ||
(Make tea)</pre> |
(Make tea)</pre> |
||
=== Alternative version using a pairing heap: === |
=== Alternative version using a pairing heap: === |
||
< |
<syntaxhighlight lang=PicoLisp> |
||
(de heap-first (H) (car H)) |
(de heap-first (H) (car H)) |
||
Line 5,452: | Line 5,452: | ||
(de heap-rest (H) |
(de heap-rest (H) |
||
("merge-pairs" (cdr H))) |
("merge-pairs" (cdr H))) |
||
</syntaxhighlight> |
|||
</lang> |
|||
Test: |
Test: |
||
< |
<syntaxhighlight lang=PicoLisp> |
||
(setq H NIL) |
(setq H NIL) |
||
(for |
(for |
||
Line 5,470: | Line 5,470: | ||
(bye) |
(bye) |
||
</syntaxhighlight> |
|||
</lang> |
|||
{{Out}} |
{{Out}} |
||
<pre> |
<pre> |
||
Line 5,485: | Line 5,485: | ||
Example of use : |
Example of use : |
||
< |
<syntaxhighlight lang=Prolog>priority-queue :- |
||
TL0 = [3-'Clear drains', |
TL0 = [3-'Clear drains', |
||
4-'Feed cat'], |
4-'Feed cat'], |
||
Line 5,513: | Line 5,513: | ||
heap_to_list(Heap4, TL2), |
heap_to_list(Heap4, TL2), |
||
writeln('Content of the queue'), maplist(writeln, TL2). |
writeln('Content of the queue'), maplist(writeln, TL2). |
||
</syntaxhighlight> |
|||
</lang> |
|||
The output : |
The output : |
||
<pre>1 ?- priority-queue. |
<pre>1 ?- priority-queue. |
||
Line 5,537: | Line 5,537: | ||
The map stores the elements of a given priority in a FIFO list. |
The map stores the elements of a given priority in a FIFO list. |
||
Priorities can be any signed 32 value. |
Priorities can be any signed 32 value. |
||
< |
<syntaxhighlight lang=purebasic>Structure taskList |
||
List description.s() ;implements FIFO queue |
List description.s() ;implements FIFO queue |
||
EndStructure |
EndStructure |
||
Line 5,655: | Line 5,655: | ||
Print(#CRLF$ + #CRLF$ + "Press ENTER to exit"): Input() |
Print(#CRLF$ + #CRLF$ + "Press ENTER to exit"): Input() |
||
CloseConsole() |
CloseConsole() |
||
EndIf</ |
EndIf</syntaxhighlight> |
||
{{out}} |
{{out}} |
||
<pre>Solve RC tasks |
<pre>Solve RC tasks |
||
Line 5,675: | Line 5,675: | ||
The data structures in the "queue" module are synchronized multi-producer, multi-consumer queues for multi-threaded use. They can however handle this task: |
The data structures in the "queue" module are synchronized multi-producer, multi-consumer queues for multi-threaded use. They can however handle this task: |
||
< |
<syntaxhighlight lang=python>>>> import queue |
||
>>> pq = queue.PriorityQueue() |
>>> pq = queue.PriorityQueue() |
||
>>> for item in ((3, "Clear drains"), (4, "Feed cat"), (5, "Make tea"), (1, "Solve RC tasks"), (2, "Tax return")): |
>>> for item in ((3, "Clear drains"), (4, "Feed cat"), (5, "Make tea"), (1, "Solve RC tasks"), (2, "Tax return")): |
||
Line 5,690: | Line 5,690: | ||
(4, 'Feed cat') |
(4, 'Feed cat') |
||
(5, 'Make tea') |
(5, 'Make tea') |
||
>>> </ |
>>> </syntaxhighlight> |
||
;Help text for queue.PriorityQueue: |
;Help text for queue.PriorityQueue: |
||
< |
<syntaxhighlight lang=python>>>> import queue |
||
>>> help(queue.PriorityQueue) |
>>> help(queue.PriorityQueue) |
||
Help on class PriorityQueue in module queue: |
Help on class PriorityQueue in module queue: |
||
Line 5,799: | Line 5,799: | ||
| list of weak references to the object (if defined) |
| list of weak references to the object (if defined) |
||
>>> </ |
>>> </syntaxhighlight> |
||
===Using heapq=== |
===Using heapq=== |
||
Line 5,805: | Line 5,805: | ||
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. |
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. |
||
< |
<syntaxhighlight lang=python>>>> from heapq import heappush, heappop, heapify |
||
>>> items = [(3, "Clear drains"), (4, "Feed cat"), (5, "Make tea"), (1, "Solve RC tasks"), (2, "Tax return")] |
>>> items = [(3, "Clear drains"), (4, "Feed cat"), (5, "Make tea"), (1, "Solve RC tasks"), (2, "Tax return")] |
||
>>> heapify(items) |
>>> heapify(items) |
||
Line 5,817: | Line 5,817: | ||
(4, 'Feed cat') |
(4, 'Feed cat') |
||
(5, 'Make tea') |
(5, 'Make tea') |
||
>>> </ |
>>> </syntaxhighlight> |
||
;Help text for module heapq: |
;Help text for module heapq: |
||
< |
<syntaxhighlight lang=python>>>> help('heapq') |
||
Help on module heapq: |
Help on module heapq: |
||
Line 5,908: | Line 5,908: | ||
>>> </ |
>>> </syntaxhighlight> |
||
Line 5,915: | Line 5,915: | ||
For more examples uf usage, see [[Sorting algorithms/Heapsort#Quackery]] and [[Huffman coding#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 heap.pq ( --> s ) |
||
Line 6,012: | Line 6,012: | ||
swap echo say ": " |
swap echo say ": " |
||
echo$ cr ] |
echo$ cr ] |
||
drop</ |
drop</syntaxhighlight> |
||
{{out}} |
{{out}} |
||
Line 6,025: | Line 6,025: | ||
=={{header|R}}== |
=={{header|R}}== |
||
Using closures: |
Using closures: |
||
< |
<syntaxhighlight lang=R>PriorityQueue <- function() { |
||
keys <- values <- NULL |
keys <- values <- NULL |
||
insert <- function(key, value) { |
insert <- function(key, value) { |
||
Line 6,050: | Line 6,050: | ||
while(!pq$empty()) { |
while(!pq$empty()) { |
||
with(pq$pop(), cat(key,":",value,"\n")) |
with(pq$pop(), cat(key,":",value,"\n")) |
||
}</ |
}</syntaxhighlight>With output:<syntaxhighlight lang=R>1 : Solve RC tasks |
||
2 : Tax return |
2 : Tax return |
||
3 : Clear drains |
3 : Clear drains |
||
4 : Feed cat |
4 : Feed cat |
||
5 : Make tea</ |
5 : Make tea</syntaxhighlight>A similar implementation using R5 classes:<syntaxhighlight lang=R>PriorityQueue <- |
||
setRefClass("PriorityQueue", |
setRefClass("PriorityQueue", |
||
fields = list(keys = "numeric", values = "list"), |
fields = list(keys = "numeric", values = "list"), |
||
Line 6,070: | Line 6,070: | ||
}, |
}, |
||
empty = function() length(keys) == 0 |
empty = function() length(keys) == 0 |
||
))</ |
))</syntaxhighlight>The only change in the example would be in the instantiation:<syntaxhighlight lang=R>pq <- PriorityQueue$new()</syntaxhighlight>. |
||
=={{header|Racket}}== |
=={{header|Racket}}== |
||
This solution implements priority queues on top of heaps. |
This solution implements priority queues on top of heaps. |
||
< |
<syntaxhighlight lang=racket> |
||
#lang racket |
#lang racket |
||
(require data/heap) |
(require data/heap) |
||
Line 6,099: | Line 6,099: | ||
(remove-min!) |
(remove-min!) |
||
(remove-min!) |
(remove-min!) |
||
</syntaxhighlight> |
|||
</lang> |
|||
Output: |
Output: |
||
< |
<syntaxhighlight lang=racket> |
||
"Solve RC tasks" |
"Solve RC tasks" |
||
"Tax return" |
"Tax return" |
||
Line 6,107: | Line 6,107: | ||
"Feed cat" |
"Feed cat" |
||
"Make tea" |
"Make tea" |
||
</syntaxhighlight> |
|||
</lang> |
|||
=={{header|Raku}}== |
=={{header|Raku}}== |
||
Line 6,115: | Line 6,115: | ||
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. |
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=perl6>class PriorityQueue { |
||
has @!tasks; |
has @!tasks; |
||
Line 6,142: | Line 6,142: | ||
} |
} |
||
say $pq.get until $pq.is-empty;</ |
say $pq.get until $pq.is-empty;</syntaxhighlight> |
||
{{out}} |
{{out}} |
||
Line 6,157: | Line 6,157: | ||
===version 1=== |
===version 1=== |
||
Programming note: this REXX version allows any number (with or without decimals, say, '''5.7''') for the priority, including negative numbers. |
Programming note: this REXX version allows any number (with or without decimals, say, '''5.7''') for the priority, including negative numbers. |
||
< |
<syntaxhighlight lang=rexx>/*REXX program implements a priority queue with insert/display/delete the top task.*/ |
||
#=0; @.= /*0 tasks; nullify the priority queue.*/ |
#=0; @.= /*0 tasks; nullify the priority queue.*/ |
||
say '══════ inserting tasks.'; call .ins 3 "Clear drains" |
say '══════ inserting tasks.'; call .ins 3 "Clear drains" |
||
Line 6,178: | Line 6,178: | ||
if top=='' | _>top then do; top=_; top#=j; end |
if top=='' | _>top then do; top=_; top#=j; end |
||
end /*j*/ |
end /*j*/ |
||
return top#</ |
return top#</syntaxhighlight> |
||
{{out|output}} |
{{out|output}} |
||
<pre> |
<pre> |
||
Line 6,195: | Line 6,195: | ||
===version 2=== |
===version 2=== |
||
< |
<syntaxhighlight lang=rexx>/*REXX pgm implements a priority queue; with insert/show/delete top task*/ |
||
n=0 |
n=0 |
||
task.=0 /* for the sake of task.0done.* */ |
task.=0 /* for the sake of task.0done.* */ |
||
Line 6,236: | Line 6,236: | ||
task.0done.j=1 |
task.0done.j=1 |
||
todo=todo-1 |
todo=todo-1 |
||
return res</ |
return res</syntaxhighlight> |
||
{{out}} |
{{out}} |
||
<pre>------ inserting tasks. |
<pre>------ inserting tasks. |
||
Line 6,258: | Line 6,258: | ||
=={{header|Ruby}}== |
=={{header|Ruby}}== |
||
A naive, inefficient implementation |
A naive, inefficient implementation |
||
< |
<syntaxhighlight lang=ruby>class PriorityQueueNaive |
||
def initialize(data=nil) |
def initialize(data=nil) |
||
@q = Hash.new {|h, k| h[k] = []} |
@q = Hash.new {|h, k| h[k] = []} |
||
Line 6,339: | Line 6,339: | ||
puts pq3.pop |
puts pq3.pop |
||
end |
end |
||
puts "peek : #{pq3.peek}"</ |
puts "peek : #{pq3.peek}"</syntaxhighlight> |
||
{{out}} |
{{out}} |
||
Line 6,366: | Line 6,366: | ||
=={{header|Run BASIC}}== |
=={{header|Run BASIC}}== |
||
< |
<syntaxhighlight lang=runbasic>sqliteconnect #mem, ":memory:" |
||
#mem execute("CREATE TABLE queue (priority float,descr text)") |
#mem execute("CREATE TABLE queue (priority float,descr text)") |
||
Line 6,410: | Line 6,410: | ||
print priority;" ";descr$ |
print priority;" ";descr$ |
||
next i |
next i |
||
RETURN</ |
RETURN</syntaxhighlight> |
||
{{out}} |
{{out}} |
||
<pre> -------------- Find first priority --------------------- |
<pre> -------------- Find first priority --------------------- |
||
Line 6,427: | Line 6,427: | ||
=={{header|Rust}}== |
=={{header|Rust}}== |
||
< |
<syntaxhighlight lang=rust>use std::collections::BinaryHeap; |
||
use std::cmp::Ordering; |
use std::cmp::Ordering; |
||
use std::borrow::Cow; |
use std::borrow::Cow; |
||
Line 6,474: | Line 6,474: | ||
println!("{}", item.task); |
println!("{}", item.task); |
||
} |
} |
||
}</ |
}</syntaxhighlight> |
||
{{out}} |
{{out}} |
||
<pre>Solve RC tasks |
<pre>Solve RC tasks |
||
Line 6,484: | Line 6,484: | ||
=={{header|SAS}}== |
=={{header|SAS}}== |
||
Using macros in a SAS data step: |
Using macros in a SAS data step: |
||
< |
<syntaxhighlight lang=sas>%macro HeapInit(size=1000,nchar=20); |
||
do; |
do; |
||
_len = 0; |
_len = 0; |
||
Line 6,579: | Line 6,579: | ||
%HeapPop; |
%HeapPop; |
||
end; |
end; |
||
run;</ |
run;</syntaxhighlight> |
||
{{output}} |
{{output}} |
||
<pre>1 Solve RC tasks |
<pre>1 Solve RC tasks |
||
Line 6,588: | Line 6,588: | ||
An implementation using <code>proc ds2</code> may be more structured: |
An implementation using <code>proc ds2</code> may be more structured: |
||
< |
<syntaxhighlight lang=sas>proc ds2; |
||
package Heap / overwrite=yes; |
package Heap / overwrite=yes; |
||
dcl int _entryorder _size _len _entryOrders[1000]; |
dcl int _entryorder _size _len _entryOrders[1000]; |
||
Line 6,697: | Line 6,697: | ||
end; |
end; |
||
enddata; |
enddata; |
||
run;</ |
run;</syntaxhighlight> |
||
=={{header|Scala}}== |
=={{header|Scala}}== |
||
Scala has a class PriorityQueue in its standard library. |
Scala has a class PriorityQueue in its standard library. |
||
< |
<syntaxhighlight lang=scala>import scala.collection.mutable.PriorityQueue |
||
case class Task(prio:Int, text:String) extends Ordered[Task] { |
case class Task(prio:Int, text:String) extends Ordered[Task] { |
||
def compare(that: Task)=that.prio compare this.prio |
def compare(that: Task)=that.prio compare this.prio |
||
Line 6,709: | Line 6,709: | ||
var q=PriorityQueue[Task]() ++ Seq(Task(3, "Clear drains"), Task(4, "Feed cat"), |
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")) |
Task(5, "Make tea"), Task(1, "Solve RC tasks"), Task(2, "Tax return")) |
||
while(q.nonEmpty) println(q dequeue)</ |
while(q.nonEmpty) println(q dequeue)</syntaxhighlight> |
||
Output: |
Output: |
||
<pre>Task(1,Solve RC tasks) |
<pre>Task(1,Solve RC tasks) |
||
Line 6,717: | Line 6,717: | ||
Task(5,Make tea)</pre> |
Task(5,Make tea)</pre> |
||
Instead of deriving the class from Ordering an implicit conversion could be provided. |
Instead of deriving the class from Ordering an implicit conversion could be provided. |
||
< |
<syntaxhighlight lang=scala>case class Task(prio:Int, text:String) |
||
implicit def taskOrdering=new Ordering[Task] { |
implicit def taskOrdering=new Ordering[Task] { |
||
def compare(t1:Task, t2:Task):Int=t2.prio compare t1.prio |
def compare(t1:Task, t2:Task):Int=t2.prio compare t1.prio |
||
}</ |
}</syntaxhighlight> |
||
=={{header|SenseTalk}}== |
=={{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. |
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 |
// PriorityQueue.script |
||
set Tasks to a new PriorityQueue |
set Tasks to a new PriorityQueue |
||
Line 6,765: | Line 6,765: | ||
return (priority of each && task of each for each item of my queue) joined by return |
return (priority of each && task of each for each item of my queue) joined by return |
||
end report |
end report |
||
</syntaxhighlight> |
|||
</lang> |
|||
{{out}} |
{{out}} |
||
<pre> |
<pre> |
||
Line 6,786: | Line 6,786: | ||
=={{header|Sidef}}== |
=={{header|Sidef}}== |
||
{{trans|Raku}} |
{{trans|Raku}} |
||
< |
<syntaxhighlight lang=ruby>class PriorityQueue { |
||
has tasks = [] |
has tasks = [] |
||
Line 6,815: | Line 6,815: | ||
} |
} |
||
say pq.get while !pq.is_empty</ |
say pq.get while !pq.is_empty</syntaxhighlight> |
||
{{out}} |
{{out}} |
||
Line 6,833: | Line 6,833: | ||
Note: this is a max-heap |
Note: this is a max-heap |
||
< |
<syntaxhighlight lang=sml>structure TaskPriority = struct |
||
type priority = int |
type priority = int |
||
val compare = Int.compare |
val compare = Int.compare |
||
Line 6,861: | Line 6,861: | ||
in |
in |
||
aux pq |
aux pq |
||
end</ |
end</syntaxhighlight> |
||
testing: |
testing: |
||
Line 6,876: | Line 6,876: | ||
Using <code>mata</code>, which has 1-based arrays: |
Using <code>mata</code>, which has 1-based arrays: |
||
< |
<syntaxhighlight lang=stata>mata |
||
struct Node { |
struct Node { |
||
real scalar time |
real scalar time |
||
Line 6,978: | Line 6,978: | ||
testHeap(0) |
testHeap(0) |
||
end |
end |
||
</syntaxhighlight> |
|||
</lang> |
|||
{{out}} |
{{out}} |
||
<pre> |
<pre> |
||
Line 7,001: | Line 7,001: | ||
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. |
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}} |
{{works with|Swift|2.x}} |
||
< |
<syntaxhighlight lang=swift>class Task : Comparable, CustomStringConvertible { |
||
var priority : Int |
var priority : Int |
||
var name: String |
var name: String |
||
Line 7,056: | Line 7,056: | ||
while pq.count != 0 { |
while pq.count != 0 { |
||
print(pq.pop()) |
print(pq.pop()) |
||
}</ |
}</syntaxhighlight> |
||
{{out}} |
{{out}} |
||
Line 7,069: | Line 7,069: | ||
=={{header|Tcl}}== |
=={{header|Tcl}}== |
||
{{tcllib|struct::prioqueue}} |
{{tcllib|struct::prioqueue}} |
||
< |
<syntaxhighlight lang=tcl>package require struct::prioqueue |
||
set pq [struct::prioqueue] |
set pq [struct::prioqueue] |
||
Line 7,086: | Line 7,086: | ||
# Remove the front-most item from the priority queue |
# Remove the front-most item from the priority queue |
||
puts [$pq get] |
puts [$pq get] |
||
}</ |
}</syntaxhighlight> |
||
Which produces this output: |
Which produces this output: |
||
<pre> |
<pre> |
||
Line 7,162: | Line 7,162: | ||
For b@ = Set(b, b+1) To a@ + 1 Step -1: @(b@) = @(b@-1) : Next |
For b@ = Set(b, b+1) To a@ + 1 Step -1: @(b@) = @(b@-1) : Next |
||
Return |
Return |
||
</ |
</syntaxhighlight> |
||
{{Out}} |
{{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. |
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. |
||
Line 7,184: | Line 7,184: | ||
=={{header|VBA}}== |
=={{header|VBA}}== |
||
< |
<syntaxhighlight lang=VB>Type Tuple |
||
Priority As Integer |
Priority As Integer |
||
Data As String |
Data As String |
||
Line 7,262: | Line 7,262: | ||
Debug.Print t.Priority, t.Data |
Debug.Print t.Priority, t.Data |
||
Loop |
Loop |
||
End Sub</ |
End Sub</syntaxhighlight>{{out}}<pre>1 Solve RC tasks |
||
2 Tax return |
2 Tax return |
||
3 Clear drains |
3 Clear drains |
||
Line 7,271: | Line 7,271: | ||
=={{header|VBScript}}== |
=={{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. |
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> |
|||
<lang vb> |
|||
option explicit |
option explicit |
||
Class prio_queue |
Class prio_queue |
||
Line 7,377: | Line 7,377: | ||
set queue= nothing |
set queue= nothing |
||
</syntaxhighlight> |
|||
</lang> |
|||
Output: |
Output: |
||
<pre> |
<pre> |
||
Line 7,392: | Line 7,392: | ||
{{libheader|Wren-queue}} |
{{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! |
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=ecmascript>import "/queue" for PriorityQueue |
||
var tasks = PriorityQueue.new() |
var tasks = PriorityQueue.new() |
||
Line 7,403: | Line 7,403: | ||
var t = tasks.pop() |
var t = tasks.pop() |
||
System.print(t) |
System.print(t) |
||
}</ |
}</syntaxhighlight> |
||
{{out}} |
{{out}} |
||
Line 7,422: | Line 7,422: | ||
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. |
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. |
||
< |
<syntaxhighlight lang=lisp>(define-class priority-queue |
||
(instance-variables queue lowest-priority most-urgent) ) |
(instance-variables queue lowest-priority most-urgent) ) |
||
Line 7,456: | Line 7,456: | ||
(define-method (priority-queue 'emptyp) |
(define-method (priority-queue 'emptyp) |
||
(and (= most-urgent lowest-priority) (null (vector-ref queue most-urgent))) )</ |
(and (= most-urgent lowest-priority) (null (vector-ref queue most-urgent))) )</syntaxhighlight> |
||
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). |
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). |
||
< |
<syntaxhighlight lang=lisp>(define pq (priority-queue 'new 5)) |
||
(pq 'push "Clear drains" 3) |
(pq 'push "Clear drains" 3) |
||
Line 7,465: | Line 7,465: | ||
(pq 'push "Make tea" 5) |
(pq 'push "Make tea" 5) |
||
(pq 'push "Solve RC tasks" 1) |
(pq 'push "Solve RC tasks" 1) |
||
(pq 'push "Tax return" 2)</ |
(pq 'push "Tax return" 2)</syntaxhighlight> |
||
{{out}} |
{{out}} |
||
Items are popped beginning from the most urgent: |
Items are popped beginning from the most urgent: |
||
< |
<syntaxhighlight lang=lisp>[1] (pq 'pop) |
||
"Solve RC tasks" |
"Solve RC tasks" |
||
[2] (pq 'pop) |
[2] (pq 'pop) |
||
"Tax return"</ |
"Tax return"</syntaxhighlight> |
||
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): |
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): |
||
< |
<syntaxhighlight lang=lisp>[3] (pq 'push "Answer emails" 4) |
||
("Feed cat" "Answer emails")</ |
("Feed cat" "Answer emails")</syntaxhighlight> |
||
Attempting to push with an invalid priority value returns the empty list, i.e. false: |
Attempting to push with an invalid priority value returns the empty list, i.e. false: |
||
< |
<syntaxhighlight lang=lisp>[4] (pq 'push "Weed garden" 17) |
||
()</ |
()</syntaxhighlight> |
||
<code>'EMPTYP</code> returns false if the priority queue is not empty: |
<code>'EMPTYP</code> returns false if the priority queue is not empty: |
||
< |
<syntaxhighlight lang=lisp>[5] (pq 'emptyp) |
||
()</ |
()</syntaxhighlight> |
||
<code>'PEEK</code> non-destructively returns the item that would be popped if you called <code>'POP</code>: |
<code>'PEEK</code> non-destructively returns the item that would be popped if you called <code>'POP</code>: |
||
< |
<syntaxhighlight lang=lisp>[6] (pq 'peek) |
||
"Clear drains"</ |
"Clear drains"</syntaxhighlight> |
||
If you want to examine a whole priority queue, the built-in <code>'SHOW</code> method allows you to do so: |
If you want to examine a whole priority queue, the built-in <code>'SHOW</code> method allows you to do so: |
||
< |
<syntaxhighlight lang=scheme>[7] (pq 'show) |
||
Object is #<Object:PRIORITY-QUEUE #x4e2cba8>, Class is #<Class:PRIORITY-QUEUE #x4e254c8> |
Object is #<Object:PRIORITY-QUEUE #x4e2cba8>, Class is #<Class:PRIORITY-QUEUE #x4e254c8> |
||
Line 7,498: | Line 7,498: | ||
LOWEST-PRIORITY = 5 |
LOWEST-PRIORITY = 5 |
||
MOST-URGENT = 3 |
MOST-URGENT = 3 |
||
#<Object:PRIORITY-QUEUE #x4e2cba8></ |
#<Object:PRIORITY-QUEUE #x4e2cba8></syntaxhighlight> |
||
Once all the items have been popped, the priority queue is empty and <code>'EMPTYP</code> then returns true: |
Once all the items have been popped, the priority queue is empty and <code>'EMPTYP</code> then returns true: |
||
< |
<syntaxhighlight lang=lisp>[8] (pq 'pop) |
||
"Clear drains" |
"Clear drains" |
||
Line 7,514: | Line 7,514: | ||
[12] (pq 'emptyp) |
[12] (pq 'emptyp) |
||
#T</ |
#T</syntaxhighlight> |
||
Attempting to pop from an empty priority queue returns false: |
Attempting to pop from an empty priority queue returns false: |
||
< |
<syntaxhighlight lang=lisp>[13] (pq 'pop) |
||
()</ |
()</syntaxhighlight> |
||
=={{header|Zig}}== |
=={{header|Zig}}== |
||
Line 7,526: | Line 7,526: | ||
Save the following code as <code>priority_queue.zig</code>, and run the tests using <code>zig test priority_queue.zig</code>. |
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 std = @import("std"); |
||
const PriorityQueue = std.PriorityQueue; |
const PriorityQueue = std.PriorityQueue; |
||
Line 7,612: | Line 7,612: | ||
} |
} |
||
</syntaxhighlight> |
|||
</lang> |
|||
Sample output: |
Sample output: |
||
< |
<syntaxhighlight lang=Zig> |
||
$ zig test priority_queue.zig |
$ zig test priority_queue.zig |
||
Test [1/2] test "priority queue (max heap)"... |
Test [1/2] test "priority queue (max heap)"... |
||
Line 7,633: | Line 7,633: | ||
All 2 tests passed. |
All 2 tests passed. |
||
</syntaxhighlight> |
|||
</lang> |
|||
=={{header|zkl}}== |
=={{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). |
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). |
||
< |
<syntaxhighlight lang=zkl>class PQ{ |
||
fcn init(numLevels=10){ // 0..numLevels, bigger # == lower priorty |
fcn init(numLevels=10){ // 0..numLevels, bigger # == lower priorty |
||
var [const] queue=(1).pump(numLevels+1,List.createLong(numLevels).write,L().copy); |
var [const] queue=(1).pump(numLevels+1,List.createLong(numLevels).write,L().copy); |
||
Line 7,656: | Line 7,656: | ||
fcn walker{ state.clear().append(0,0); Walker(next) } // iterator front end |
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)) } |
fcn toString{ "PQ(%d) items".fmt(queue.reduce(fcn(sum,q){ sum+q.len() },0)) } |
||
}</ |
}</syntaxhighlight> |
||
< |
<syntaxhighlight lang=zkl>pq:=PQ(); |
||
foreach x in |
foreach x in |
||
(T("Clear drains",3, "Feed cat",4, "Make tea",5, "Solve RC tasks",1, "Tax return",2, |
(T("Clear drains",3, "Feed cat",4, "Make tea",5, "Solve RC tasks",1, "Tax return",2, |
||
Line 7,669: | Line 7,669: | ||
println("ToDo list:"); |
println("ToDo list:"); |
||
foreach item in (pq){ item.println() } |
foreach item in (pq){ item.println() } |
||
pq.println();</ |
pq.println();</syntaxhighlight> |
||
{{out}} |
{{out}} |
||
<pre> |
<pre> |