Priority queue: Difference between revisions
Content added Content deleted
m (→{{header|XPL0}}: Alphabetize. (Very sluggish responses!)) |
Ttmrichter (talk | contribs) |
||
Line 4,361: | Line 4,361: | ||
{{out}} |
{{out}} |
||
<pre>Hello!</pre> |
<pre>Hello!</pre> |
||
=={{header|Logtalk}}== |
|||
Logtalk comes with a [https://github.com/LogtalkDotOrg/logtalk3/tree/master/library/heaps heap implementation] out of the box. As such it by definition also has a priority queue. It can be used at the toplevel like this (with some formatting changes for clarity, and '%' marking comments that would not be in the output): |
|||
<syntaxhighlight lang="logtalk">?- logtalk_load(heaps(loader)). % also `{heaps(loader)}.` on most back-ends |
|||
% output varies by settings and what's already been loaded |
|||
?- heap(<)::new(H0), % H0 contains an empty heap |
|||
heap(<)::insert(3, 'Clear drains', H0, H1), % as with Prolog, variables are in the mathematical |
|||
% sense: immutable, so we make a new heap from the empty one |
|||
heap(<)::insert(4, 'Feed cat',H1, H2), % with each insertion a new heap |
|||
heap(<)::top(H2, K2, V2), % K2=3, V2='Clear drains', |
|||
% H2=t(2, [], t(3, 'Clear drains', t(4, 'Feed cat', t, t), t)) |
|||
heap(<)::insert_all( |
|||
[ |
|||
5-'Make tea', |
|||
1-'Solve RC tasks', |
|||
2-'Tax return' |
|||
], H2, H3), % it's easier and more efficient to add items in K-V pairs |
|||
heap(<)::top(H3, K3, V3), % K3=1, V3='Solve RC tasks', |
|||
% H3=t(5, [], t(1, 'Solve RC tasks', t(3, 'Clear drains', |
|||
% t(4, 'Feed cat', t, t), t), t(2, 'Tax return', |
|||
% t(5, 'Make tea', t, t), t))), |
|||
heap(<)::delete(H3, K3, V3, H4), % K3=1, V3='Solve RC tasks', |
|||
% H4=t(4, [5], t(2, 'Tax return', t(3, 'Clear drains', |
|||
% t(4, 'Feed cat', t, t), t), t(5, 'Make tea', t, t))), |
|||
heap(<)::top(H4, K4, V4). % K4=2, V4='Tax return'</syntaxhighlight> |
|||
Since `heap` is a parametrised class in Logtalk, with the parameter being the ordering predicate, we actually use `heap(<)` object to get min ordering. There are two classes provided in Logtalk that eliminate the unnecessary replication of the two most common orderings: |
|||
<syntaxhighlight lang="logtalk">:- object(minheap, |
|||
extends(heap(<))). |
|||
:- info([ |
|||
version is 1:0:0, |
|||
author is 'Paulo Moura.', |
|||
date is 2010-02-19, |
|||
comment is 'Min-heap implementation. Uses standard order to compare keys.' |
|||
]). |
|||
:- end_object. |
|||
:- object(maxheap, |
|||
extends(heap(>))). |
|||
:- info([ |
|||
version is 1:0:0, |
|||
author is 'Paulo Moura.', |
|||
date is 2010-02-19, |
|||
comment is 'Max-heap implementation. Uses standard order to compare keys.' |
|||
]). |
|||
:- end_object.</syntaxhighlight> |
|||
Given the presence of these two classes, all of the example code above could have `heap(<)` replaced with `minheap` for identical results (including identical performance). It also illustrates how quickly and easily other orderings could be provided at need. |
|||
=={{header|Lua}}== |
=={{header|Lua}}== |