Priority queue: Difference between revisions
Rename Perl 6 -> Raku, alphabetize, minor clean-up
(Add task to ARM assembly Raspberry pi) |
Thundergnat (talk | contribs) (Rename Perl 6 -> Raku, alphabetize, minor clean-up) |
||
Line 67:
{{out}}
<pre></pre>
=={{header|ARM Assembly}}==
{{works with|as|Raspberry Pi}}
Line 505 ⟶ 506:
Priority : 5 : Make tea
</pre>
=={{header|AutoHotkey}}==
<lang AutoHotkey>;-----------------------------------
Line 630 ⟶ 632:
[1,"Solve RC tasks"]]
Type: List(OrderedKeyEntry(Integer,String))</pre>
=={{header|Batch File}}==
Batch has only a data structure, the environment that incidentally sorts itself automatically by key. The environment has a limit of 64K
Line 751 ⟶ 754:
Feed cat
Make tea</pre>
=={{header|C sharp}}==
Line 1,093 ⟶ 1,020:
(5, Solve RC tasks)</pre>
=={{header|
The C++ standard library contains the <code>std::priority_queue</code> opaque data structure. It implements a max-heap.
<lang cpp>#include <iostream>
#include <string>
#include <queue>
#include <utility>
int main() {
std::priority_queue<std::pair<int, std::string> > pq;
pq.push(std::make_pair(3, "Clear drains"));
pq.push(std::make_pair(4, "Feed cat"));
pq.push(std::make_pair(5, "Make tea"));
pq.push(std::make_pair(1, "Solve RC tasks"));
pq.push(std::make_pair(2, "Tax return"));
std::cout << pq.top().first << ", " << pq.top().second << std::endl;
pq.pop();
}
return 0;
}</lang>
{{out}}
<pre>
5, Make tea
4, Feed cat
3, Clear drains
2, Tax return
1, Solve RC tasks
</pre>
Alternately, you can use a pre-existing container of yours
and use the heap operations to manipulate it:
<lang cpp>#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
#include <utility>
int main() {
std::vector<std::pair<int, std::string> > pq;
pq.push_back(std::make_pair(3, "Clear drains"));
pq.push_back(std::make_pair(4, "Feed cat"));
pq.push_back(std::make_pair(5, "Make tea"));
pq.push_back(std::make_pair(1, "Solve RC tasks"));
// heapify
std::make_heap(pq.begin(), pq.end());
// enqueue
pq.push_back(std::make_pair(2, "Tax return"));
std::push_heap(pq.begin(), pq.end());
while (!pq.empty()) {
// peek
std::cout << pq[0].first << ", " << pq[0].second << std::endl;
// dequeue
std::pop_heap(pq.begin(), pq.end());
pq.pop_back();
}
return 0;
}</lang>
{{out}}
<pre>
5, Make tea
4, Feed cat
3, Clear drains
2, Tax return
1, Solve RC tasks
</pre>
Line 1,255 ⟶ 1,212:
Final random element was 0.9999718656763434
</lang>
=={{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.
<lang lisp>
;priority-queue's are implemented with association lists
(defun make-pq (alist)
(sort (copy-alist alist) (lambda (a b) (< (car a) (car b)))))
;
;Will change the state of pq
;
(define-modify-macro insert-pq (pair)
(lambda (pq pair) (sort-alist (cons pair pq))))
(define-modify-macro remove-pq-aux () cdr)
(defmacro remove-pq (pq)
`(let ((aux (copy-alist ,pq)))
(REMOVE-PQ-AUX ,pq)
(car aux)))
;
;Will not change the state of pq
;
(defun insert-pq-non-destructive (pair pq)
(sort-alist (cons pair pq)))
(defun remove-pq-non-destructive (pq)
(cdr pq))
;testing
(defparameter a (make-pq '((1 . "Solve RC tasks") (3 . "Clear drains") (2 . "Tax return") (5 . "Make tea"))))
(format t "~a~&" a)
(insert-pq a '(4 . "Feed cat"))
(format t "~a~&" a)
(format t "~a~&" (remove-pq a))
(format t "~a~&" a)
(format t "~a~&" (remove-pq a))
(format t "~a~&" a)
</lang>
{{out}}
<pre>
((1 . Solve RC tasks) (2 . Tax return) (3 . Clear drains) (5 . Make tea))
((1 . Solve RC tasks) (2 . Tax return) (3 . Clear drains) (4 . Feed cat) (5 . Make tea))
(1 . Solve RC tasks)
((2 . Tax return) (3 . Clear drains) (4 . Feed cat) (5 . Make tea))
(2 . Tax return)
((3 . Clear drains) (4 . Feed cat) (5 . Make tea))
</pre>
=={{header|Component Pascal}}==
Line 3,634 ⟶ 3,637:
Tax return
Solve RC tasks</lang>
=={{header|Phix}}==
Line 4,477 ⟶ 4,436:
"Make tea"
</lang>
=={{header|Raku}}==
(formerly Perl 6)
This is a rather simple implementation. It requires the priority to be a positive integer value, with lower values being higher priority. There isn't a hard limit on how many priority levels you can have, though more than a few dozen is probably not practical.
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.
<lang perl6>class PriorityQueue {
has @!tasks;
method insert (Int $priority where * >= 0, $task) {
@!tasks[$priority].push: $task;
}
method get { @!tasks.first(?*).shift }
method is-empty { ?none @!tasks }
}
my $pq = PriorityQueue.new;
for (
3, 'Clear drains',
4, 'Feed cat',
5, 'Make tea',
9, 'Sleep',
3, 'Check email',
1, 'Solve RC tasks',
9, 'Exercise',
2, 'Do taxes'
) -> $priority, $task {
$pq.insert( $priority, $task );
}
say $pq.get until $pq.is-empty;</lang>
{{out}}
<pre>Solve RC tasks
Do taxes
Clear drains
Check email
Feed cat
Make tea
Sleep
Exercise</pre>
=={{header|REXX}}==
Line 5,100 ⟶ 5,104:
5 Make tea
</pre>
=={{header|XLISP}}==
| |||