Priority queue: Difference between revisions

A [[wp:Priority queue|priority queue]] is somewhat similar to a [[Queue|queue]], with an important distinction: each item is added to a priority queue with a priority level, and will be later removed from the queue with the highest priority element first. That is, the items are (conceptually) stored in the queue in priority order instead of in insertion order.

 

 

Optionally, other operations may be defined, such as peeking (find what current top priority/top element is), merging (combining two priority queues into one), etc.

 

 

 

=={{header|Ada}}==

Ada 2012 includes container classes for priority queues.

 

with Ada.Containers.Unbounded_Priority_Queues;

with Ada.Strings.Unbounded;

 

procedure Priority_Queues is

end loop;

end;

 

 

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

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

[[5,"Make tea"], [4,"Feed cat"], [3,"Clear drains"], [2,"Tax return"],

[1,"Solve RC tasks"]]

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

}

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

<pre>

</pre>

 

 

 

 

 

 

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.

(4, Tax return)

(5, Solve RC tasks)</pre>

 

=={{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|CoffeeScript}}==

PriorityQueue = ->

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

v = new_v

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

 

output

 

> coffee priority_queue.coffee

Solve RC tasks

First random element was 0.00002744467929005623

Final random element was 0.9999718656763434

 

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

5:> Make tea

</pre>

=={{header|D}}==

 

void main() {

heap.removeFront();

}

{{out}}

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

Tuple!(int,string)(2, "Tax return")

Tuple!(int,string)(1, "Solve RC tasks")</pre>

=={{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|Fortran}}==

implicit none

 

! 2 -> Tax return

! 1 -> Solve RC tasks

 

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

}

 

PriorityQueue<Task> pq = new PriorityQueue<Task>();

pq.add(new Task(3, "Clear drains"));

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

}

<pre>

1, Solve RC tasks

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"

"Feed cat"

"Make tea"

 

=={{header|Lasso}}==

data

store = map,

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

stdout(#test->pop)

 

{{out}}

<pre>Hello!</pre>

 

=={{header|Lua}}==

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

 

 

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:

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

(data: Tax return, pri: 2)

(data: Feed cat, pri: 4)

(data: Make tea, pri: 5)</pre>

 

=={{header|Objective-C}}==

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>

4, Feed cat

5, Make tea