Priority queue: Difference between revisions

{{trans|Python}}

 

minheap:heapify(&items)

L !items.empty

 

{{out}}

=={{header|AArch64 Assembly}}==

{{works with|as|Raspberry Pi 3B version Buster 64 bits}}

/* ARM assembly AARCH64 Raspberry PI 3B */

/* program priorQueue64.s */

/* for this file see task include a file in language AArch64 assembly */

.include "../includeARM64.inc"

{{Output}}

<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}}

 

INCLUDE "D2:ALLOCATE.ACT" ;from the Action! Tool Kit. You must type 'SET EndProg=*' from the monitor after compiling, but before running this program!

TestPop()

TestIsEmpty()

{{out}}

[https://gitlab.com/amarok8bit/action-rosetta-code/-/raw/master/images/Priority_queue.png Screenshot from Atari 8-bit computer]

Ada 2012 includes container classes for priority queues.

 

with Ada.Containers.Unbounded_Priority_Queues;

with Ada.Strings.Unbounded;

end loop;

end;

 

{{out}}

=={{header|ARM Assembly}}==

{{works with|as|Raspberry Pi}}

/* ARM assembly Raspberry PI */

/* program priorqueue.s */

pop {r2-r4}

bx lr @ return

{{out}}

<pre>

 

=={{header|AutoHotkey}}==

PQ_TopItem(Queue,Task:=""){ ; remove and return top priority item

TopPriority := PQ_TopPriority(Queue)

TopPriority := TopPriority?TopPriority:P , TopPriority := TopPriority<P?TopPriority:P

return, TopPriority

(

3 Clear drains

MsgBox, 262208,, % (Task:="Feed cat") " priority = " PQ_Check(PQ,task)"`n`n" PQ_View(PQ)

^Esc::

 

=={{header|Axiom}}==

Axiom already has a heap domain for ordered sets.

We define a domain for ordered key-entry pairs and then define a priority queue using the heap domain over the pairs:

OrderedKeyEntry(Key:OrderedSet,Entry:SetCategory): Exports == Implementation where

Exports == OrderedSet with

setelt(x:%,key:Key,entry:Entry) ==

insert!(construct(key,entry)$S,x)

pq(3):="Clear drains";

pq(4):="Feed cat";

pq(1):="Solve RC tasks";

pq(2):="Tax return";

{{out}}

<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

@echo off

setlocal enabledelayedexpansion

:next

set order= %order:~-3%

{{out}}

<pre>

=={{header|C}}==

Using a dynamic array as a binary heap. Stores integer priority and a character pointer. Supports push and pop.

#include <stdlib.h>

 

return 0;

}

{{output}}

<pre>Solve RC tasks

=== Pairing heap w/ generic data types ===

header file:

typedef struct _pq_node_t {

long int key;

NEW_PQ_ELE(p, k); \

*(h) = heap_merge(((pq_node_t *) (p)), *(h))

implementation:

#include <stdlib.h>

#include "pairheap.h"

return two_pass_merge(h->down);

}

usage:

#include <stdio.h>

#include <string.h>

}

}

{{Out}}

<pre>

 

===.NET 6 solution===

using System.Collections.Generic;

 

5 Make tea

 

===Pre-.NET 6 solution===

 

namespace PriorityQueue

}

}

 

'''Min Heap Priority Queue'''

{{works with|C sharp|C#|3.0+/DotNet 3.5+}}

The above code is not really a true Priority Queue as it does not allow duplicate keys; also, the SortedList on which it is based does not have O(log n) insertions and removals for random data as a true Priority Queue does. The below code implements a true Min Heap Priority Queue:

using KeyT = UInt32;

using System;

return toSeq(fromSeq(sq)); }

}

 

The above class code offers a full set of static methods and properties:

 

The above code can be tested as per the page specification by the following code:

Tuple<uint, string>[] ins = { new Tuple<uint,string>(3u, "Clear drains"),

new Tuple<uint,string>(4u, "Feed cat"),

foreach (var e in MinHeapPQ<string>.toSeq(MinHeapPQ<string>.adjust((k, v) => new Tuple<uint,string>(6u - k, v), npq)))

Console.WriteLine(e); Console.WriteLine();

 

It tests building the queue the slow way using repeated "push"'s - O(n log n), the faster "fromSeq" (included in the "sort") - O(n), and also tests the "merge" and "adjust" methods.

The C++ standard library contains the <code>std::priority_queue</code> opaque data structure. It implements a max-heap.

 

#include <string>

#include <queue>

 

return 0;

 

{{out}}

and use the heap operations to manipulate it:

 

#include <string>

#include <vector>

 

return 0;

 

{{out}}

=={{header|Clojure}}==

 

 

; priority-map can be used as a priority queue

; Merge priority-maps together

user=> (into p [["Wax Car" 4]["Paint Fence" 1]["Sand Floor" 3]])

 

=={{header|CLU}}==

must support the less-than operator.

 

where P has lt: proctype (P,P) returns (bool)

stream$putl(po, int$unparse(prio) || ": " || task)

end

{{out}}

<pre>1: Solve RC tasks

 

=={{header|CoffeeScript}}==

PriorityQueue = ->

# Use closure style for object creation (so no "new" required).

v = new_v

console.log "Final random element was #{v}"

 

output

First random element was 0.00002744467929005623

Final random element was 0.9999718656763434

 

=={{header|Common Lisp}}==

In this task were implemented to versions of the functions, the non-destructive ones that will not change the state of the priority queue and the destructive ones that will change. The destructive ones work very similarly to the 'pop' and 'push' functions.

;priority-queue's are implemented with association lists

(defun make-pq (alist)

(format t "~a~&" (remove-pq a))

(format t "~a~&" a)

{{out}}

<pre>

=={{header|Component Pascal}}==

BlackBox Component Builder

MODULE PQueues;

IMPORT StdLog,Boxes;

END PQueues.

Interface extracted from the implementation

DEFINITION PQueues;

 

 

END PQueues.

Execute: ^Q PQueues.Test<br/>

Output:

 

=={{header|D}}==

 

void main() {

heap.removeFront();

}

{{out}}

<pre>Tuple!(int,string)(5, "Make tea")

{{libheader| Boost.Generics.Collection}}

Boost.Generics.Collection is part of [https://github.com/MaiconSoft/DelphiBoostLib DelphiBoostLib]

 

{$APPTYPE CONSOLE}

with Queue.DequeueEx do

Writeln(Priority, ', ', value);

{{out}}

<pre>1, Solve RC tasks

=={{header|EchoLisp}}==

We use the built-in binary tree library. Each tree node has a datum (key . value). The functions (bin-tree-pop-first tree) and (bin-tree-pop-last tree) allow to extract the node with highest or lowest priority.

(lib 'tree)

(define tasks (make-bin-tree 3 "Clear drains"))

(bin-tree-pop-last tasks) → (4 . "Feed 🐡")

; etc.

 

=={{header|Elixir}}==

{{trans|Erlang}}

def create, do: :gb_trees.empty

end

 

 

{{out}}

=={{header|Erlang}}==

Using built in gb_trees module, with the suggested interface for this task.

-module( priority_queue ).

 

io:fwrite( "top priority: ~p~n", [Element] ),

New_queue.

{{out}}

<pre>

 

The following Binomial Heap Priority Queue code has been adapted [http://cs.hubfs.net/topic/None/56608 from a version by "DeeJay"] updated for changes in F# over the intervening years, and implementing the O(1) "peekMin" mentioned in that post; in addition to the above standard priority queue functions, it also implements the "merge" function for which the Binomial Heap is particularly suited, taking O(log n) time rather than the usual O(n) (or worse) time:

module PriorityQ =

 

let sort sq = sq |> fromSeq |> toSeq

 

 

"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.

 

The following code implementing a Min Heap Priority Queue is adapted from the [http://www.cl.cam.ac.uk/~lp15/MLbook/programs/sample4.sml ML PRIORITY_QUEUE code by Lawrence C. Paulson] including separating the key/value pairs as separate entries in the data structure for better comparison efficiency; it implements an efficient "fromSeq" function using reheapify for which the Min Heap is particularly suited as it has only O(n) instead of O(n log n) computational time complexity, which method is also used for the "adjust" and "merge" functions:

module PriorityQ =

 

let toSeq pq = Seq.unfold popMin pq

 

 

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.

 

As the Min Heap is usually implemented as a [http://opendatastructures.org/versions/edition-0.1e/ods-java/10_1_BinaryHeap_Implicit_Bi.html mutable array binary heap] after a genealogical tree based model invented by [https://en.wikipedia.org/wiki/Michael_Eytzinger Michael Eytzinger] over 400 years ago, the following "ugly imperative" code implements the Min Heap Priority Queue this way; note that the code could be implemented not using "ugly" mutable state variables other than the contents of the array (DotNet List which implements a growable array) but in this case the code would be considerably slower as in not much faster or slower than the functional version since using mutable side effects greatly reduces the number of operations:

module PriorityQ =

 

let toSeq pq = Seq.unfold popMin pq

 

 

The comments for the above code are the same as for the functional version; the main difference is that the imperative code takes about two thirds of the time on average.

 

All of the above codes can be tested under the F# REPL using the following:

(4u, "Feed cat");

(5u, "Make tea");

printfn ""

testpq |> MinHeap.adjust (fun k v -> uint32 (MinHeap.size testpq) - k, v)

 

to produce the following output:

=={{header|Factor}}==

Factor has priority queues implemented in the library: documentation is available at http://docs.factorcode.org/content/article-heaps.html (or by typing "heaps" help interactively in the listener).

{ 3 "Clear drains" }

{ 4 "Feed cat" }

] [

[ print ] slurp-heap

 

output:

Tax return

Clear drains

Feed cat

 

=={{header|Forth}}==

{{works with|gforth|0.7.3}}

<br>

 

\ Priority queue

>r 2 s" Tax return" r> >queue

 

 

{{out}}

 

=={{header|Fortran}}==

implicit none

 

! 2 -> Tax return

! 1 -> Solve RC tasks

 

 

=={{header|FreeBASIC}}==

{{trans|VBA}}

Prioridad As Integer

Tarea As String

Print t.Prioridad; " "; t.Tarea

Loop

{{out}}

<pre>

 

=={{header|FunL}}==

native scala.collection.mutable.PriorityQueue

 

 

while not q.isEmpty()

 

{{out}}

Go's standard library contains the <code>container/heap</code> package, which which provides operations to operate as a heap any data structure that contains the <code>Push</code>, <code>Pop</code>, <code>Len</code>, <code>Less</code>, and <code>Swap</code> methods.

 

 

import (

fmt.Println(heap.Pop(pq))

}

 

output:

=={{header|Groovy}}==

Groovy can use the built in java PriorityQueue class

 

@Canonical

 

while (!empty) { println remove() }

 

Output:

=={{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.

 

 

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.

 

{{out}}

<pre>[(1,"Solve RC tasks"),(2,"Tax return"),(3,"Clear drains"),(4,"Feed cat"),(5,"Make tea")]</pre>

 

Alternatively, a homemade min heap implementation:

deriving (Show, Eq)

 

(5, "Make tea"),

(1, "Solve RC tasks"),

 

The above code is a Priority Queue but isn't a [https://en.wikipedia.org/wiki/Binary_heap Min Heap based on a Binary Heap] for the following reasons: 1) it does not preserve the standard tree structure of the binary heap and 2) the tree balancing can be completely destroyed by some combinations of "pop" operations. The following code is a true purely functional Min Heap implementation and as well implements the extra optional features of Min Heap's that it can build a new Min Heap from a list in O(n) amortized time rather than the O(n log n) amortized time (for a large number of randomly ordered entries) by simply using repeated "push" operations; as well as the standard "push", "peek", "delete" and "pop" (combines the previous two). As well as the "fromList", "toList", and "sort" functions (the last combines the first two), it also has an "isEmpty" function to test for the empty queue, an "adjust" function that applies a function to every entry in the queue and reheapifies in O(n) amortized time and also the "replaceMin" function which is about twice as fast on the average as combined "delete" followed by "push" operations:

| MinHeapLeaf !kv

| MinHeapNode !kv {-# UNPACK #-} !Int !(MinHeap a) !(MinHeap a)

 

sortPQ :: (Ord kv) => [kv] -> [kv]

 

If one is willing to forgo the fast O(1) "size" function and to give up strict conformance to the Heap tree structure (where rather than building each new level until each left node is full to that level before increasing level to the right, a new level is built by promoting leaves to branches only containing left leaves until all branches have left leaves before filling any right leaves of that level) although having even better tree balancing and therefore at least as high efficiency, one can use the following code adapted from the [http://www.cl.cam.ac.uk/~lp15/MLbook/programs/sample4.sml ''ML'' PRIORITY_QUEUE code by Lawrence C. Paulson] including separating the key/value pairs as separate entries in the data structure for better comparison efficiency; as noted in the code comments, a "size" function to output the number of elements in the queue (fairly quickly in O((log n)^2)), an "adjust" function to apply a function to all elements and reheapify in O(n) time, and a "merge" function to merge two queues has been added to the ML code:

| Br !k v !(PriorityQ k v) !(PriorityQ k v)

deriving (Eq, Ord, Read, Show)

 

sortPQ :: (Ord k) => [(k, v)] -> [(k, v)]

 

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 when tested with the following "main" function (with a slight modification for the first test when the combined kv entry is used):

(4, "Feed cat"),

(5, "Make tea"),

mapM_ print $ toListPQ $ mergePQ testPQ testPQ

putStrLn "" -- test adjust

 

has the output as follows:

<tt>Closure</tt> is used to allow the queue to order lists based on

their first element. The solution only works in Unicon.

import Collections # For Heap (dense priority queue) class

 

while task := pq.get() do write(task[1]," -> ",task[2])

end

Output when run:

<pre>

Implementation:

 

 

PRI=: ''

QUE=: y}.QUE

r

 

Efficiency is obtained by batching requests. Size of batch for insert is determined by size of arguments. Size of batch for topN is its right argument.

Example:

 

3 4 5 1 2 insert__Q 'clear drains';'feed cat';'make tea';'solve rc task';'tax return'

>topN__Q 1

clear drains

tax return

 

=={{header|Java}}==

Java has a <code>PriorityQueue</code> class. It requires either the elements implement <code>Comparable</code>, or you give it a custom <code>Comparator</code> to compare the elements.

 

 

class Task implements Comparable<Task> {

System.out.println(pq.remove());

}

{{out}}

<pre>

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.

 

 

# Add an item with the given priority (an integer,

def prioritize:

. as $list | {} | pq_add_tasks($list) | pq_pop_tasks ;

The specific task:

[ [3, "Clear drains"],

[4, "Feed cat"],

[2, "Tax return"]

] | prioritize

{{Out}}

"Solve RC tasks"

=={{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.

using Base.Collections

 

dequeue!(task)

println(" \"", t, "\" has priority ", p)

 

{{out}}

=={{header|Kotlin}}==

{{trans|Java}}

 

internal data class Task(val priority: Int, val name: String) : Comparable<Task> {

"Tax return" priority 2))

while (q.any()) println(q.remove())

{{out}}

<pre>Task(priority=1, name=Solve RC tasks)

 

=={{header|Lasso}}==

data

store = map,

while(not #test->isEmpty) => {

stdout(#test->pop)

 

{{out}}

This implementation uses a table with priorities as keys and queues as values. Queues for each priority are created when putting items as needed and are shrunk as necessary when popping items and removed when they are empty. Instead of using a plain array table for each queue, the technique shown in the Lua implementation from the [[Queue/Definition#Lua | Queue]] task is used. This avoids having to use <code>table.remove(t, 1)</code> to get and remove the first queue element, which is rather slow for big tables.

 

__index = {

put = function(self, p, v)

for prio, task in pq.pop, pq do

print(string.format("Popped: %d - %s", prio, task))

 

'''Output:'''

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⁷ tasks with a random priority between 1 and 1000 and to retrieve them from the queue again in order.

 

-- since it has millisecond precision on most systems

local socket = require("socket")

end

 

 

=={{header|M2000 Interpreter}}==

 

===Using unordered array===

Module UnOrderedArray {

Class PriorityQueue {

}

UnOrderedArray

 

===Using a stack with arrays as elements===

Every insertion push item using binary search in proper position. Pop is very fast.

Module PriorityQueue {

a= ( (3, "Clear drains"), (4 ,"Feed cat"), ( 5 , "Make tea"), ( 1 ,"Solve RC tasks"), ( 2 , "Tax return"))

PriorityQueue

 

 

===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.

 

Module PriorityQueueForGroups {

class obj {

}

PriorityQueueForGroups

 

=={{header|Mathematica}}/{{header|Wolfram Language}}==

queue = SortBy[Append[queue, {priority, item}], First], HoldFirst];

pop = Function[queue,

If[Length@queue == 0, Null, Max[queue[[All, 1]]]], HoldFirst];

merge = Function[{queue1, queue2},

 

Example:

 

push[queue, 3, "Clear drains"];

push[queue, 4, "Feed cat"];

queue1 = {};

push[queue1, 6, "Drink tea"];

 

Output:

 

=={{header|Maxima}}==

The key may be any number (integer or not). Items are extracted in FIFO order. */

 

"call friends"

"serve cider"

 

=={{header|Mercury}}==

Mercury comes with an efficient, albeit simple, priority queue in its standard library. The build_pqueue/2 predicate in the code below inserts the test data in arbitrary order. display_pqueue/3, in turn, removes one K/V pair at a time, displaying the value. Compiling and running the supplied program results in all tasks being displayed in priority order as expected.

 

 

:- interface.

main(!IO) :-

build_pqueue(pqueue.init, PQO),

 

=={{header|Nim}}==

{{trans|C}}

PriElem[T] = tuple

data: T

 

while p.count > 0:

{{out}}

<pre>(data: Solve RC tasks, pri: 1)

 

''' Using Nim HeapQueue'''

 

var pq = newHeapQueue[(int, string)]()

 

while pq.len() > 0:

 

{{out}}

 

''' Using Nim tables'''

 

var

pq.del(i)

{{out}}

<pre>1: Solve RC tasks

The priority queue used in this example is not actually written in Objective-C. It is part of Apple's (C-based) Core Foundation library, which is included with in Cocoa on Mac OS X and iOS. Its interface is a C function interface, which makes the code very ugly. Core Foundation is not included in GNUStep or other Objective-C APIs.

 

 

const void *PQRetain(CFAllocatorRef allocator, const void *ptr) {

}

return 0;

 

log:

Holger Arnold's [http://holgerarnold.net/software/ OCaml base library] provides a [http://holgerarnold.net/software/ocaml/doc/base/PriorityQueue.html PriorityQueue] module.

 

 

let () =

PQ.remove_first pq;

print_endline task

 

testing:

Although OCaml's standard library does not have a dedicated priority queue structure, one can (for most purposes) use the built-in Set data structure as a priority queue, as long as no two elements compare equal (since Set does not allow duplicate elements). This is the case here since no two tasks should have the same name. Note that Set is a functional, persistent data structure, so we derive new priority queues from the old ones functionally, rather than modifying them imperatively; the complexity is still O(log n).

{{works with|OCaml|4.02+}}

(struct

type t = int * string (* pair of priority and task name *)

aux (PQSet.remove task pq')

end

{{out}}

<pre>

(buffer empty)

*/

 

=={{header|Pascal}}==

program PriorityQueueTest;

 

Queue.free;

end.

 

=={{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]

use strict;

use Heap::Priority;

["Tax return", 2];

 

Feed cat

Clear drains

Tax return

===IBM card sorter version===

 

use strict; # https://rosettacode.org/wiki/Priority_queue

delete $bins[-1] while @bins and @{ $bins[-1] // [] } == 0;

shift @{ $bins[-1] // [] };

{{out}}

<pre>

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.

<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: #0000FF;">?</span><span style="color: #008000;">"==="</span>

<span style="color: #000000;">list_tasks</span><span style="color: #0000FF;">()</span>

{{out}}

<pre>

(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)

<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: #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>

{{out}}

The optional initial set_rand() makes it slightly more amusing.<br>

=== builtin ===

If you omit MAX_HEAP or (same thing) specify MIN_HEAP, the output'll be 1..5

<span style="color: #008080;">with</span> <span style="color: #008080;">javascript_semantics</span>

<span style="color: #008080;">constant</span> <span style="color: #000000;">tasklist</span> <span style="color: #0000FF;">=</span> <span style="color: #7060A8;">pq_new</span><span style="color: #0000FF;">(</span><span style="color: #004600;">MAX_HEAP</span><span style="color: #0000FF;">)</span>

<span style="color: #7060A8;">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>

{{out}}

<pre>

 

=={{header|Phixmonti}}==

by Galileo, 05/2022 #/

 

( 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

{{out}}

<pre>[1, "Solve RC tasks"]

{{works with|PHP|5.3+}}

PHP's <code>SplPriorityQueue</code> class implements a max-heap. PHP also separately has <code>SplHeap</code>, <code>SplMinHeap</code>, and <code>SplMaxHeap</code> classes.

$pq = new SplPriorityQueue;

 

print_r($pq->extract());

}

 

Output:

{{works with|PHP|5.3+}}

The difference between <code>SplHeap</code> and <code>SplPriorityQueue</code> is that <code>SplPriorityQueue</code> takes the data and the priority as two separate arguments, and the comparison is only made on the priority; whereas <code>SplHeap</code> takes only one argument (the element), and the comparison is made on that directly. In all of these classes it is possible to provide a custom comparator by subclassing the class and overriding its <code>compare</code> method.

$pq = new SplMinHeap;

print_r($pq->extract());

}

 

Output:

=={{header|Picat}}==

Picat has built-in support for min and max heaps.

Tasks = [[3,"Clear drains"],

[4,"Feed cat"],

nl,

println("Pop the elements from the queue:"),

 

{{out}}

 

The heaps creation functions can take the task list as argument:

[4,"Feed cat"],

[5,"Make tea"],

[2,"Tax return"]],

Heap = new_min_heap(Tasks),

 

 

=={{header|PicoLisp}}==

The following implementation imposes no limits. It uses a [http://software-lab.de/doc/refI.html#idx binary tree] for storage. The priority levels may be numeric, or of any other type.

(de insertPQ (Queue Prio Item)

(idx Queue (cons Prio Item) T) )

# Merge second queue into first

(de mergePQ (Queue1 Queue2)

Test:

(off Pq1 Pq2)

 

# Remove and print all items from first queue

(while Pq1

Output:

<pre>(Solve RC tasks)

(Make tea)</pre>

=== Alternative version using a pairing heap: ===

(de heap-first (H) (car H))

 

(de heap-rest (H)

("merge-pairs" (cdr H)))

Test:

(setq H NIL)

(for

 

(bye)

{{Out}}

<pre>

 

Example of use :

TL0 = [3-'Clear drains',

4-'Feed cat'],

heap_to_list(Heap4, TL2),

writeln('Content of the queue'), maplist(writeln, TL2).

The output :

<pre>1 ?- priority-queue.

The map stores the elements of a given priority in a FIFO list.

Priorities can be any signed 32 value.

List description.s() ;implements FIFO queue

EndStructure

Print(#CRLF$ + #CRLF$ + "Press ENTER to exit"): Input()

CloseConsole()

{{out}}

<pre>Solve RC tasks

 

The data structures in the "queue" module are synchronized multi-producer, multi-consumer queues for multi-threaded use. They can however handle this task:

>>> pq = queue.PriorityQueue()

>>> for item in ((3, "Clear drains"), (4, "Feed cat"), (5, "Make tea"), (1, "Solve RC tasks"), (2, "Tax return")):

(4, 'Feed cat')

(5, 'Make tea')

 

;Help text for queue.PriorityQueue:

>>> help(queue.PriorityQueue)

Help on class PriorityQueue in module queue:

| list of weak references to the object (if defined)

 

 

===Using heapq===

 

Although one can use the heappush method to add items individually to a heap similar to the method used in the PriorityQueue example above, we will instead transform the list of items into a heap in one go then pop them off one at a time as before.

>>> items = [(3, "Clear drains"), (4, "Feed cat"), (5, "Make tea"), (1, "Solve RC tasks"), (2, "Tax return")]

>>> heapify(items)

(4, 'Feed cat')

(5, 'Make tea')

 

;Help text for module heapq:

Help on module heapq:

 

 

 

 

 

For more examples uf usage, see [[Sorting algorithms/Heapsort#Quackery]] and [[Huffman coding#Quackery]]

 

 

[ stack ] is heap.pq ( --> s )

swap echo say ": "

echo$ cr ]

 

{{out}}

=={{header|R}}==

Using closures:

keys <- values <- NULL

insert <- function(key, value) {

while(!pq$empty()) {

with(pq$pop(), cat(key,":",value,"\n"))

2 : Tax return

3 : Clear drains

4 : Feed cat

setRefClass("PriorityQueue",

fields = list(keys = "numeric", values = "list"),

},

empty = function() length(keys) == 0

 

=={{header|Racket}}==

This solution implements priority queues on top of heaps.

#lang racket

(require data/heap)

(remove-min!)

(remove-min!)

Output:

"Solve RC tasks"

"Tax return"

"Feed cat"

"Make tea"

 

=={{header|Raku}}==

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.

 

has @!tasks;

 

}

 

{{out}}

===version 1===

Programming note: &nbsp; this REXX version allows any number (with or without decimals, say, '''5.7''') for the priority, including negative numbers.

#=0; @.= /*0 tasks; nullify the priority queue.*/

say '══════ inserting tasks.'; call .ins 3 "Clear drains"

if top=='' | _>top then do; top=_; top#=j; end

end /*j*/

{{out|output}}

<pre>

 

===version 2===

n=0

task.=0 /* for the sake of task.0done.* */

task.0done.j=1

todo=todo-1

{{out}}

<pre>------ inserting tasks.

=={{header|Ruby}}==

A naive, inefficient implementation

def initialize(data=nil)

@q = Hash.new {|h, k| h[k] = []}

puts pq3.pop

end

 

{{out}}

 

=={{header|Run BASIC}}==

#mem execute("CREATE TABLE queue (priority float,descr text)")

 

print priority;" ";descr$

next i

{{out}}

<pre> -------------- Find first priority ---------------------

 

=={{header|Rust}}==

use std::cmp::Ordering;

use std::borrow::Cow;

println!("{}", item.task);

}

{{out}}

<pre>Solve RC tasks

=={{header|SAS}}==

Using macros in a SAS data step:

do;

_len = 0;

%HeapPop;

end;

{{output}}

<pre>1 Solve RC tasks

 

An implementation using <code>proc ds2</code> may be more structured:

package Heap / overwrite=yes;

dcl int _entryorder _size _len _entryOrders[1000];

end;

enddata;

 

=={{header|Scala}}==

Scala has a class PriorityQueue in its standard library.

case class Task(prio:Int, text:String) extends Ordered[Task] {

def compare(that: Task)=that.prio compare this.prio

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"))

Output:

<pre>Task(1,Solve RC tasks)

Task(5,Make tea)</pre>

Instead of deriving the class from Ordering an implicit conversion could be provided.

implicit def taskOrdering=new Ordering[Task] {

def compare(t1:Task, t2:Task):Int=t2.prio compare t1.prio

 

=={{header|SenseTalk}}==

We use New to create an object instance -- in this case (for simplicity) based on the script itself, which is named PriorityQueue. The Tell command or dot notation are then used to send messages directly to that object.

// PriorityQueue.script

set Tasks to a new PriorityQueue

return (priority of each && task of each for each item of my queue) joined by return

end report

{{out}}

<pre>

=={{header|Sidef}}==

{{trans|Raku}}

has tasks = []

 

}

 

 

{{out}}

Note: this is a max-heap

 

type priority = int

val compare = Int.compare

in

aux pq

 

testing:

 

Using <code>mata</code>, which has 1-based arrays:

struct Node {

real scalar time

testHeap(0)

end

{{out}}

<pre>

You can use <code>CFBinaryHeap</code> from Core Foundation, but it is super ugly due to the fact that <code>CFBinaryHeap</code> operates on generic pointers, and you need to convert back and forth between that and objects.

{{works with|Swift|2.x}}

var priority : Int

var name: String

while pq.count != 0 {

print(pq.pop())

 

{{out}}

=={{header|Tcl}}==

{{tcllib|struct::prioqueue}}

 

set pq [struct::prioqueue]

# Remove the front-most item from the priority queue

puts [$pq get]

Which produces this output:

<pre>

For b@ = Set(b, b+1) To a@ + 1 Step -1: @(b@) = @(b@-1) : Next

Return

{{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.

 

=={{header|VBA}}==

Priority As Integer

Data As String

Debug.Print t.Priority, t.Data

Loop

2 Tax return

3 Clear drains

=={{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.

option explicit

Class prio_queue

set queue= nothing

 

Output:

<pre>

{{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!

 

var tasks = PriorityQueue.new()

var t = tasks.pop()

System.print(t)

 

{{out}}

The <code>'PUSH</code> method never needs to search down the levels. The efficiency bottleneck here is probably the implementation of <code>NCONC</code> (used for adding the new item to the end of the queue at the relevant level). A priority <i>stack</i>, with first in / last out at each priority level rather than first in / first out, would be faster.

 

(instance-variables queue lowest-priority most-urgent) )

 

 

(define-method (priority-queue 'emptyp)

 

The example uses strings, but the data items stored in the priority queue can be of any type (including the empty list—or even other priority queues).

 

(pq 'push "Clear drains" 3)

(pq 'push "Make tea" 5)

(pq 'push "Solve RC tasks" 1)

{{out}}

Items are popped beginning from the most urgent:

 

"Solve RC tasks"

[2] (pq 'pop)

 

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):

 

Attempting to push with an invalid priority value returns the empty list, i.e. false:

 

<code>'EMPTYP</code> returns false if the priority queue is not empty:

 

<code>'PEEK</code> non-destructively returns the item that would be popped if you called <code>'POP</code>:

 

If you want to examine a whole priority queue, the built-in <code>'SHOW</code> method allows you to do so:

 

Object is #<Object:PRIORITY-QUEUE #x4e2cba8>, Class is #<Class:PRIORITY-QUEUE #x4e254c8>

LOWEST-PRIORITY = 5

MOST-URGENT = 3

Once all the items have been popped, the priority queue is empty and <code>'EMPTYP</code> then returns true:

 

"Clear drains"

[12] (pq 'emptyp)

 

Attempting to pop from an empty priority queue returns false:

 

 

=={{header|Zig}}==

Save the following code as <code>priority_queue.zig</code>, and run the tests using <code>zig test priority_queue.zig</code>.

 

const std = @import("std");

const PriorityQueue = std.PriorityQueue;

}

 

 

Sample output:

 

$ zig test priority_queue.zig

Test [1/2] test "priority queue (max heap)"...

 

All 2 tests passed.

 

=={{header|zkl}}==

This solution uses a [hopefully small] fixed number of priorities, each of which has an unordered list of tasks. This allows O(1) insertions, O(p) for retrievals (p is the number of priorities).

fcn init(numLevels=10){ // 0..numLevels, bigger # == lower priorty

var [const] queue=(1).pump(numLevels+1,List.createLong(numLevels).write,L().copy);

fcn walker{ state.clear().append(0,0); Walker(next) } // iterator front end

fcn toString{ "PQ(%d) items".fmt(queue.reduce(fcn(sum,q){ sum+q.len() },0)) }

foreach x in

(T("Clear drains",3, "Feed cat",4, "Make tea",5, "Solve RC tasks",1, "Tax return",2,

println("ToDo list:");

foreach item in (pq){ item.println() }

{{out}}

<pre>