Priority queue: Difference between revisions
→{{header|Lasso}}
m (→{{header|XPL0}}: Alphabetize. (Very sluggish responses!)) |
Ttmrichter (talk | contribs) |
||
Line 4,361:
{{out}}
<pre>Hello!</pre>
=={{header|Logtalk}}==
Logtalk comes with a [https://github.com/LogtalkDotOrg/logtalk3/tree/master/library/heaps heap implementation] out of the box. As such it by definition also has a priority queue. It can be used at the toplevel like this (with some formatting changes for clarity, and '%' 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}}==
| |||