Priority queue: Difference between revisions

Content added Content deleted
(→‎{{header|Haskell}}: Add "mergePQ" function and clean up code...)
(→‎{{header|F Sharp}}: add "merge" function to both versions of MinHeap...)
Line 984: Line 984:
=={{header|F Sharp}}==
=={{header|F Sharp}}==


The below codes all provide the standard priority queue functions of "peekMin", "push", and "deleteMin"; as well, "replaceMin" which can be much more efficient that a "deleteMin" followed by a "push" for some types of queues), "popMin" (generally a convenience function for "peekMin" followed by "deleteMin"), "adjust" for applying a function to all queue entries and reheapifying, "fromSeq" for building a queue from a sequence, "toSeq" for outputting a sorted sequence of the queue contents, and "sort" which is a convenience function combining the latter two functions are provided.
The below codes all provide the standard priority queue functions of "peekMin", "push", and "deleteMin"; as well, "replaceMin" which can be much more efficient that a "deleteMin" followed by a "push" for some types of queues), "popMin" (generally a convenience function for "peekMin" followed by "deleteMin"), "adjust" for applying a function to all queue entries and reheapifying, "fromSeq" for building a queue from a sequence, "toSeq" for outputting a sorted sequence of the queue contents, and "sort" which is a convenience function combining the latter two functions are provided. Finally, the queue's all provide a "merge" function to combine two queues into one, and an "adjust" function which applies a function to every heap element and reheapifies.
===Functional===
===Functional===


Line 1,104: Line 1,104:
'''Min Heap Priority Queue'''
'''Min Heap Priority Queue'''


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:
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:
<lang fsharp>[<RequireQualifiedAccess>]
<lang fsharp>[<RequireQualifiedAccess>]
module PriorityQ =
module PriorityQ =
Line 1,135: Line 1,135:
| Mt -> 2
| Mt -> 2
| Br(_, prl, prr) ->
| Br(_, prl, prr) ->
let d = (n - 1) >>> 1
let nm1 = n - 1 in let d = nm1 >>> 1
if ((n - 1) &&& 1) = 0
if (nm1 &&& 1) = 0
then rest d pll prl // subtree sizes: (d or d+1), d; d, d
then rest d pll prl // subtree sizes: (d or d+1), d; d, d
else rest d plr prr // subtree sizes: d+1, (d or d+1); d+1, d
else rest d plr prr // subtree sizes: d+1, (d or d+1); d+1, d
Line 1,197: Line 1,197:
siftdown ck cv (build lft) (build rght)
siftdown ck cv (build lft) (build rght)
build (sq |> Seq.length)
build (sq |> Seq.length)

let merge (pq1:PQ<_>) (pq2:PQ<_>) = // merges without using a sequence
match pq1 with
| Mt -> pq2
| _ ->
match pq2 with
| Mt -> pq1
| _ ->
let rec zipper lvl pq rest =
if lvl = 0 then Mt, pq, rest else
let lft = lvl >>> 1 in let rght = (lvl - 1) >>> 1
match pq with
| Mt ->
match rest with
| [] | Mt :: _ -> Mt, pq, [] // Mt in list never happens
| Br(kv, ll, Mt) :: tl ->
let pl, pql, rstl = zipper lft ll tl
let pr, pqr, rstr = zipper rght pql rstl
siftdown kv.k kv.v pl pr, pqr, rstr
| Br(kv, ll, rr) :: tl ->
let pl, pql, rstl = zipper lft ll (rr :: tl)
let pr, pqr, rstr = zipper rght pql rstl
siftdown kv.k kv.v pl pr, pqr, rstr
| Br(kv, ll, Mt) ->
let pl, pql, rstl = zipper lft ll rest
let pr, pqr, rstr = zipper rght pql rstl
siftdown kv.k kv.v pl pr, pqr, rstr
| Br(kv, ll, rr) ->
let pl, pql, rstl = zipper lft ll (rr :: rest)
let pr, pqr, rstr = zipper rght pql rstl
siftdown kv.k kv.v pl pr, pqr, rstr
let sz = size pq1 + size pq2
let pq, _, _ = zipper sz pq1 [pq2] in pq


let popMin pq = match peekMin pq with
let popMin pq = match peekMin pq with
Line 1,204: Line 1,237:
let toSeq pq = Seq.unfold popMin pq
let toSeq pq = Seq.unfold popMin pq


let sort sq = sq |> fromSeq |> toSeq
let sort sq = sq |> fromSeq |> toSeq</lang>
</lang>


The above code does not implement a "merge" function but such could be written to use a private internal function to output the two queues to be merged as unsorted sequences (O(n) time) and then use "fromSeq" on the concatenation of the two sequences (also O(n) time complexity) for a combined O(n) computational time complexity.
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.


Other than the "merge" function, the Min Heap Priority Queue has the same time complexity as for the Binomial Heap Priority Queue above except that "push" has O(log n) performance rather than the amortized O(1) performance; however, the Binomial Heap Priority Queue is generally a constant factor slower due to more complex operations. The Binomial Heap Priority Queue is generally more suited when used where merging of large queues or frequent "push" operations are used; the Min Heap Priority Queue is more suitable for use when replacing the value at the minimum entry of the queue is frequently required, especially when the adjusted value is not displaced very far down the queue on average.
Other than the "merge" function, the Min Heap Priority Queue has the same time complexity as for the Binomial Heap Priority Queue above except that "push" has O(log n) performance rather than the amortized O(1) performance; however, the Binomial Heap Priority Queue is generally a constant factor slower due to more complex operations. The Binomial Heap Priority Queue is generally more suited when used where merging of large queues or frequent "push" operations are used; the Min Heap Priority Queue is more suitable for use when replacing the value at the minimum entry of the queue is frequently required, especially when the adjusted value is not displaced very far down the queue on average.
Line 1,278: Line 1,310:
let ckv = pq.[i] in siftdown ckv.k ckv.v i pq
let ckv = pq.[i] in siftdown ckv.k ckv.v i pq
build 0; pq
build 0; pq

let merge (pq1:MinHeapTree<_>) (pq2:MinHeapTree<_>) =
if pq2.Count = 0 then pq1 else
if pq1.Count = 0 then pq2 else
let pq = empty
pq.AddRange(pq1); pq.RemoveAt(pq.Count - 1)
pq.AddRange(pq2)
let sz = pq.Count - 1
let rec build i =
let lefti = i + i + 1
if lefti < sz then
let righti = lefti + 1 in build lefti; build righti
let ckv = pq.[i] in siftdown ckv.k ckv.v i pq
build 0; pq


let popMin pq = match peekMin pq with
let popMin pq = match peekMin pq with
Line 1,290: Line 1,336:


All of the above codes can be tested under the F# REPL using the following:
All of the above codes can be tested under the F# REPL using the following:
<lang fsharp>> [| (3u, "Clear drains");
<lang fsharp>> let testseq = [| (3u, "Clear drains");
(4u, "Feed cat");
(4u, "Feed cat");
(5u, "Make tea");
(5u, "Make tea");
(1u, "Solve RC tasks");
(1u, "Solve RC tasks");
(2u, "Tax return") |]
(2u, "Tax return") |] |> Array.toSeq
let testpq = testseq |> MinHeap.fromSeq
|> Seq.fold (fun pq (k, v) -> PriorityQ.push k v pq) PriorityQ.empty
testseq |> Seq.fold (fun pq (k, v) -> MinHeap.push k v pq) MinHeap.empty
⚫
|> PriorityQ.toSeq |> Seq.iter (printfn "%A");;</lang>
|> MinHeap.toSeq |> Seq.iter (printfn "%A") // test slow build

printfn ""
or with (using the O(n) "fromSeq" reheapify):
testseq |> MinHeap.fromSeq |> MinHeap.toSeq // test fast build
⚫
<lang fsharp>> [| (3u, "Clear drains");
(4u, "Feed cat");
|> Seq.iter (printfn "%A")
(5u, "Make tea");
printfn ""
testseq |> MinHeap.sort |> Seq.iter (printfn "%A") // convenience function
⚫
(1u, "Solve RC tasks");
printfn ""
⚫
(2u, "Tax return") |] |> PriorityQ.sort |> Seq.iter (printfn "%A");;</lang>
MinHeap.merge testpq testpq // test merge
⚫
|> MinHeap.toSeq |> Seq.iter (printfn "%A")
printfn ""
testpq |> MinHeap.adjust (fun k v -> uint32 (MinHeap.size testpq) - k, v)
⚫
|> MinHeap.toSeq |> Seq.iter (printfn "%A") // test adjust;;</lang>


to produce the following output:
to produce the following output:
Line 1,312: Line 1,363:
(4u, "Feed cat")
(4u, "Feed cat")
(5u, "Make tea")
(5u, "Make tea")

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

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

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

(0u, "Make tea")
(1u, "Feed cat")
(2u, "Clear drains")
(3u, "Tax return")
(4u, "Solve RC tasks")
val it : unit = ()</pre>
val it : unit = ()</pre>


with the last code considerably faster for large random-order entry sequences.
Note that the code using "fromSeq" instead of repeated "push" operations to build a queue is considerably faster for large random-order entry sequences.

Also note that the imperative version modifies the state of the "testpq" binding for modification operations such as "push" and "deleteMin" or operations derived from those; this means that if the last two tests were reversed then the "merge" would be passed zero sized queues since the "testpq" would have been reduced by the "toSeq" operation (which effectively uses repeated "deleteMin" functions).


=={{header|Factor}}==
=={{header|Factor}}==
Retrieved from "https://rosettacode.org/wiki/Priority_queue"