F# priority queue

Question

Does the F# library include a priority queue? Else can someone point to me an implementation of priority queue in F#?

Bandwidth

Are you looking for a mutable or immutable data structure? – Makowski

@gradbot: any will do for now. – Bandwidth

Answer 1

There's an implementation of a binomial heap here which is a common data structure for implementing priority queues.

Anabolite

As noted in my answer improving this code, it is amazing that the code from the referenced blog still (almost) works, but although it is a good implementation of the Binomial Heap, it isn't tuned to it's application as a Priority Queue, which I have done in that answer. – Rovelli

link to website looks scammy – Threepiece

The link is for a shady website. – Penguin

Answer 2

Take a look at http://lepensemoi.free.fr/index.php/tag/data-structure for a whole bunch of F# implementations of various data structures.

Malleolus

A treasure trove! That is brilliant. To be fair I accepted Lee's answer as I used the data structure in his link earlier. I was intending to write the Okasaki book structures in F# at some point, and here it is (largely). – Bandwidth

Answer 3

It is amazing that the accepted answer still almost works with all the changes to F# over the intervening over seven years with the exception that there no longer is a Pervasives.compare function and the "compare" function has now been merged into the base operators at Microsoft.FSharp.Core.Operators.compare.

That said, that referenced blog entry implements the Binomial Heap as a general purpose Heap and not as for the specific requirements of a Priority Queue as to not requiring a generic type for the priority which can just be an integer type for efficiency in comparisons, and it speaks of but does not implement the additional improvement to preserve the minimum as a separate field for efficiency in just checking the top priority item in the queue.

The following module code implements the Binomial Heap Priority Queue as derived from that code with the improved efficiency that it does not use generic comparisons for the priority comparisons and the more efficient O(1) method for checking the top of the queue (although at the cost of more overhead for inserting and deleting entries although they are still O(log n) - n being the number of entries in the queue). This code is more suitable for the usual application of priority queues where the top of the queue is read more often than insertions and/or top item deletions are performed. Note that it isn't as efficient as the MinHeap when one is deleting the top element and reinserting it further down the queue as a full "deleteMin" and "insert" must be performed with much more of a computational overhead. The code is as follows:

[<RequireQualifiedAccess>]
module BinomialHeapPQ =

//  type 'a treeElement = Element of uint32 * 'a
  type 'a treeElement = class val k:uint32 val v:'a new(k,v) = { k=k;v=v } end

  type 'a tree = Node of uint32 * 'a treeElement * 'a tree list

  type 'a heap = 'a tree list

  type 'a outerheap = | HeapEmpty | HeapNotEmpty of 'a treeElement * 'a heap

  let empty = HeapEmpty

  let isEmpty = function | HeapEmpty -> true | _ -> false

  let inline private rank (Node(r,_,_)) = r

  let inline private root (Node(_,x,_)) = x

  exception Empty_Heap

  let getMin = function | HeapEmpty -> None
                        | HeapNotEmpty(min,_) -> Some min

  let rec private findMin heap =
    match heap with | [] -> raise Empty_Heap //guarded so should never happen
                    | [node] -> root node,[]
                    | topnode::heap' ->
                      let min,subheap = findMin heap' in let rtn = root topnode
                      match subheap with
                        | [] -> if rtn.k > min.k then min,[] else rtn,[]
                        | minnode::heap'' ->
                          let rmn = root minnode
                          if rtn.k <= rmn.k then rtn,heap
                          else rmn,minnode::topnode::heap''

  let private mergeTree (Node(r,kv1,ts1) as tree1) (Node (_,kv2,ts2) as tree2) =
    if kv1.k > kv2.k then Node(r+1u,kv2,tree1::ts2)
    else Node(r+1u,kv1,tree2::ts1)

  let rec private insTree (newnode: 'a tree) heap =
    match heap with
      | [] -> [newnode]
      | topnode::heap' -> if (rank newnode) < (rank topnode) then newnode::heap
                          else insTree (mergeTree newnode topnode) heap'

  let insert k v = let kv = treeElement(k,v) in let nn = Node(0u,kv,[])
                   function | HeapEmpty -> HeapNotEmpty(kv,[nn])
                            | HeapNotEmpty(min,heap) -> let nmin = if k > min.k then min else kv
                                                        HeapNotEmpty(nmin,insTree nn heap)

  let rec private merge' heap1 heap2 = //doesn't guaranty minimum tree node as head!!!
    match heap1,heap2 with
      | _,[] -> heap1
      | [],_ -> heap2
      | topheap1::heap1',topheap2::heap2' ->
        match compare (rank topheap1) (rank topheap2) with
          | -1 -> topheap1::merge' heap1' heap2
          | 1 -> topheap2::merge' heap1 heap2'
          | _ -> insTree (mergeTree topheap1 topheap2) (merge' heap1' heap2')

  let merge oheap1 oheap2 = match oheap1,oheap2 with
                              | _,HeapEmpty -> oheap1
                              | HeapEmpty,_ -> oheap2
                              | HeapNotEmpty(min1,heap1),HeapNotEmpty(min2,heap2) ->
                                  let min = if min1.k > min2.k then min2 else min1
                                  HeapNotEmpty(min,merge' heap1 heap2)

  let rec private removeMinTree = function
                          | [] -> raise Empty_Heap // will never happen as already guarded
                          | [node] -> node,[]
                          | t::ts -> let t',ts' = removeMinTree ts
                                     if (root t).k <= (root t').k then t,ts else t',t::ts'

  let deleteMin =
    function | HeapEmpty -> HeapEmpty
             | HeapNotEmpty(_,heap) ->
               match heap with
                 | [] -> HeapEmpty // should never occur: non empty heap with no elements
                 | [Node(_,_,heap')] -> match heap' with
                                          | [] -> HeapEmpty
                                          | _ -> let min,_ = findMin heap'
                                                 HeapNotEmpty(min,heap')
                 | _::_ -> let Node(_,_,ts1),ts2 = removeMinTree heap
                           let nheap = merge' (List.rev ts1) ts2 in let min,_ = findMin nheap
                           HeapNotEmpty(min,nheap)

  let reinsertMinAs k v pq = insert k v (deleteMin pq)

Note that there are two options in the form of the type "treeElement" in order to suit the way this is tested. In the application as noted in my answer about using priority queues to sieve primes, the above code is about 80% slower than the functional implementation of the MinHeap (non multi-processing mode, as the above binomial heap does not lend itself well to in-place adjustments); this is because of the additional computational complexity of the "delete followed by insert" operation for the Binomial Heap rather than the ability to combine these operations efficiently for the MinHeap implementation.

Thus, the MinHeap Priority Queue is more suitable for this type of application and also where efficient in-place adjustments are required, whereas the Binomial Heap Priority Queue is more suitable where one requires the ability to efficiently merge two queues into one.

Rovelli

Answer 4

FSharpx.Collections includes a functional Heap collection https://github.com/fsharp/fsharpx/blob/master/src/FSharpx.Core/Collections/Heap.fsi as well as a PriortityQueue interface for it https://github.com/fsharp/fsharpx/blob/master/src/FSharpx.Core/Collections/PriorityQueue.fs

Pumpkinseed

Answer 5

EDITED: to correct an error in the deleteMin function of the pure functional version and to add the ofSeq function.

I implemented two versions of a MinHeap Binary Heap based Priority Queue in an answer about F# prime sieves, the first one is pure functional code (slower) and the second is array based (ResizeArray, which is built on the DotNet List that internally uses an Array to store the list). The non-functional version is somewhat justified as the MinHeap is usually implemented as a mutable array binary heap after a genealogical tree based model invented by Michael Eytzinger over 400 years ago.

In that answer, I did not implement the "remove top priority item from queue" function as the algorithm did not need it, but I did implement a "reinsert top item further down the queue" function as the algorithm did need it, and that function is quite similar to what would be required for the "deleteMin" function; the difference is that rather than reinserting the top "minimum" item with new parameters, one would just delete the last item from the queue (found in a similar way as when inserting new items but simpler), and reinsert that item to replace the top (minimum) item in the queue (just call the "reinsertMinAt" function). I also implemented an "adjust" function which applies a function to all queue elements and then reheapifies the final result for efficiency, which function was a requirement of the paged Sieve of Eratosthenes algorithm in that answer.

In the following code, I have implemented the "deleteMin" function described above as well as a "ofSeq" function that can be used to build a new queue from a sequence of priority/contents tuple pair elements that uses the internal "reheapify" function for efficiency.

The MinHeap as per this code can easily be changed into a "MaxHeap" by changing the greater than symbols to less than symbols and vice versa in comparisons related to the priority 'k' values. The Min/Max Heap supports multiple elements of the same unsigned integer "Key" priority but does not preserve the order of entries with the same priority; in other words there is no guaranty that the first element that goes into the queue will be the first element that pops up to the minimum position if there are other entries with the same priority as I did not require that and the current code is more efficient. The code could be modified to preserve the order if that were a requirement (keep moving new insertions down until the past any entries of the same priority).

The Min/Max Heap Priority Queue has the advantages that it has less computational complexity overhead as compared to other types of non-simplistic queues, produces the Min or Max (depending on whether a MinHeap or MaxHeap implementation) in O(1) time, and inserts and deletes with a worst case O(log n) time, while adjusting and building require only O(n) time, where 'n' is the number of elements currently in the queue. The advantage of the "resinsertMinAs" function over a delete and then an insert is that it reduces the worst case time to O(log n) from twice that and is often better than that as reinsertions are often near the beginning of the queue so a full sweep is not required.

As compared to the Binomial Heap with the additional option of a pointer to the minimum value to produce O(1) find minimum value performance, the MinHeap may be slightly simpler and therefore quicker when doing about the same job, especially if one does not need the "merge heap" capabilities offered by the Binomial Heap. It may take longer to "reinsertMinAs" using the Binomial Heap "merge" function as compared to using the MinHeap as it would appear that typically slightly more comparisons need to be made on average.

The MinHeap Priority Queue is particularly suited to the problem of the incremental Sieve of Eratosthenes as in the other linked answer, and is likely the queue used by Melissa E. O'Neill in the work done in her paper showing that the Turner prime sieve is not really the Sieve of Eratosthenes neither as to algorithm nor as to performance.

The following pure functional code adds the "deleteMin" and "ofSeq" functions to that code:

[<RequireQualifiedAccess>]
module MinHeap =

  type MinHeapTreeEntry<'T> = class val k:uint32 val v:'T new(k,v) = { k=k;v=v } end
  [<CompilationRepresentation(CompilationRepresentationFlags.UseNullAsTrueValue)>]
  [<NoEquality; NoComparison>]
  type MinHeapTree<'T> = 
      | HeapEmpty 
      | HeapOne of MinHeapTreeEntry<'T>
      | HeapNode of MinHeapTreeEntry<'T> * MinHeapTree<'T> * MinHeapTree<'T> * uint32

  let empty = HeapEmpty

  let getMin pq = match pq with | HeapOne(kv) | HeapNode(kv,_,_,_) -> Some kv | _ -> None

  let insert k v pq =
    let kv = MinHeapTreeEntry(k,v)
    let rec insert' kv msk pq =
      match pq with
        | HeapEmpty -> HeapOne kv
        | HeapOne kvn -> if k < kvn.k then HeapNode(kv,pq,HeapEmpty,2u)
                         else HeapNode(kvn,HeapOne kv,HeapEmpty,2u)
        | HeapNode(kvn,l,r,cnt) ->
          let nc = cnt + 1u
          let nmsk = if msk <> 0u then msk <<< 1 else
                     let s = int32 (System.Math.Log (float nc) / System.Math.Log(2.0))
                     (nc <<< (32 - s)) ||| 1u //never ever zero again with the or'ed 1
          if k <= kvn.k then if (nmsk &&& 0x80000000u) = 0u then HeapNode(kv,insert' kvn nmsk l,r,nc)
                                                            else HeapNode(kv,l,insert' kvn nmsk r,nc)
          else if (nmsk &&& 0x80000000u) = 0u then HeapNode(kvn,insert' kv nmsk l,r,nc)
               else HeapNode(kvn,l,insert' kv nmsk r,nc)
    insert' kv 0u pq

  let private reheapify kv k pq =
    let rec reheapify' pq =
      match pq with
        | HeapEmpty | HeapOne _ -> HeapOne kv
        | HeapNode(kvn,l,r,cnt) ->
            match r with
              | HeapOne kvr when k > kvr.k ->
                  match l with //never HeapEmpty
                    | HeapOne kvl when k > kvl.k -> //both qualify, choose least
                        if kvl.k > kvr.k then HeapNode(kvr,l,HeapOne kv,cnt)
                        else HeapNode(kvl,HeapOne kv,r,cnt)
                    | HeapNode(kvl,_,_,_) when k > kvl.k -> //both qualify, choose least
                        if kvl.k > kvr.k then HeapNode(kvr,l,HeapOne kv,cnt)
                        else HeapNode(kvl,reheapify' l,r,cnt)
                    | _ -> HeapNode(kvr,l,HeapOne kv,cnt) //only right qualifies
              | HeapNode(kvr,_,_,_) when k > kvr.k -> //need adjusting for left leaf or else left leaf
                  match l with //never HeapEmpty or HeapOne
                    | HeapNode(kvl,_,_,_) when k > kvl.k -> //both qualify, choose least
                        if kvl.k > kvr.k then HeapNode(kvr,l,reheapify' r,cnt)
                        else HeapNode(kvl,reheapify' l,r,cnt)
                    | _ -> HeapNode(kvr,l,reheapify' r,cnt) //only right qualifies
              | _ -> match l with //r could be HeapEmpty but l never HeapEmpty
                        | HeapOne(kvl) when k > kvl.k -> HeapNode(kvl,HeapOne kv,r,cnt)
                        | HeapNode(kvl,_,_,_) when k > kvl.k -> HeapNode(kvl,reheapify' l,r,cnt)
                        | _ -> HeapNode(kv,l,r,cnt) //just replace the contents of pq node with sub leaves the same
    reheapify' pq


  let reinsertMinAs k v pq =
    let kv = MinHeapTreeEntry(k,v)
    reheapify kv k pq

  let deleteMin pq =
    let rec delete' kv msk pq =
      match pq with
        | HeapEmpty -> kv,empty //should never get here as should flock off up before an empty is reached
        | HeapOne kvn -> kvn,empty
        | HeapNode(kvn,l,r,cnt) ->
          let nmsk = if msk <> 0u then msk <<< 1 else
                     let s = int32 (System.Math.Log (float cnt) / System.Math.Log(2.0))
                     (cnt <<< (32 - s)) ||| 1u //never ever zero again with the or'ed 1
          if (nmsk &&& 0x80000000u) = 0u then let kvl,pql = delete' kvn nmsk l
                                              match pql with
                                                | HeapEmpty -> kvl,HeapOne kvn
                                                | HeapOne _ | HeapNode _ -> kvl,HeapNode(kvn,pql,r,cnt - 1u)
                                         else let kvr,pqr = delete' kvn nmsk r
                                              kvr,HeapNode(kvn,l,pqr,cnt - 1u)
    match pq with
      | HeapEmpty | HeapOne _ -> empty //for the case of deleting from queue either empty or one entry
      | HeapNode(kv,_,_,cnt) -> let nkv,npq = delete' kv 0u pq in reinsertMinAs nkv.k nkv.v npq

  let adjust f (pq:MinHeapTree<_>) = //adjust all the contents using the function, then rebuild by reheapify
    let rec adjust' pq =
      match pq with
        | HeapEmpty -> pq
        | HeapOne kv -> HeapOne(MinHeapTreeEntry(f kv.k kv.v))
        | HeapNode (kv,l,r,cnt) -> let nkv = MinHeapTreeEntry(f kv.k kv.v)
                                   reheapify nkv nkv.k (HeapNode(kv,adjust' l,adjust' r,cnt))
    adjust' pq

  let ofSeq (sq:seq<MinHeapTreeEntry<_>>) =
    let cnt = sq |> Seq.length |> uint32 in let hcnt = cnt / 2u in let nmrtr = sq.GetEnumerator()
    let rec build' i =
      if nmrtr.MoveNext() && i <= cnt then
        if i > hcnt then HeapOne(nmrtr.Current)
        else let i2 = i + i in HeapNode(nmrtr.Current,build' i2,build' (i2 + 1u),cnt - i)
      else HeapEmpty
    build' 1u

and the following code adds the deleteMin and ofSeq functions to the array based version:

[<RequireQualifiedAccess>]
module MinHeap =

  type MinHeapTreeEntry<'T> = class val k:uint32 val v:'T new(k,v) = { k=k;v=v } end
  type MinHeapTree<'T> = ResizeArray<MinHeapTreeEntry<'T>>

  let empty<'T> = MinHeapTree<MinHeapTreeEntry<'T>>()

  let getMin (pq:MinHeapTree<_>) = if pq.Count > 0 then Some pq.[0] else None

  let insert k v (pq:MinHeapTree<_>) =
    if pq.Count = 0 then pq.Add(MinHeapTreeEntry(0xFFFFFFFFu,v)) //add an extra entry so there's always a right max node
    let mutable nxtlvl = pq.Count in let mutable lvl = nxtlvl <<< 1 //1 past index of value added times 2
    pq.Add(pq.[nxtlvl - 1]) //copy bottom entry then do bubble up while less than next level up
    while ((lvl <- lvl >>> 1); nxtlvl <- nxtlvl >>> 1; nxtlvl <> 0) do
      let t = pq.[nxtlvl - 1] in if t.k > k then pq.[lvl - 1] <- t else lvl <- lvl <<< 1; nxtlvl <- 0 //causes loop break
    pq.[lvl - 1] <-  MinHeapTreeEntry(k,v); pq

  let reinsertMinAs k v (pq:MinHeapTree<_>) = //do minify down for value to insert
    let mutable nxtlvl = 1 in let mutable lvl = nxtlvl in let cnt = pq.Count
    while (nxtlvl <- nxtlvl <<< 1; nxtlvl < cnt) do
      let lk = pq.[nxtlvl - 1].k in let rk = pq.[nxtlvl].k in let oldlvl = lvl
      let k = if k > lk then lvl <- nxtlvl; lk else k in if k > rk then nxtlvl <- nxtlvl + 1; lvl <- nxtlvl
      if lvl <> oldlvl then pq.[oldlvl - 1] <- pq.[lvl - 1] else nxtlvl <- cnt //causes loop break
    pq.[lvl - 1] <- MinHeapTreeEntry(k,v); pq

  let deleteMin (pq:MinHeapTree<_>) =
    if pq.Count <= 2 then empty else //if contains one or less entries, return empty queue
    let btmi = pq.Count - 2 in let btm = pq.[btmi] in pq.RemoveAt btmi
    reinsertMinAs btm.k btm.v pq

  let adjust f (pq:MinHeapTree<_>) = //adjust all the contents using the function, then re-heapify
    if pq <> null then 
      let cnt = pq.Count
      if cnt > 1 then
        for i = 0 to cnt - 2 do //change contents using function
          let e = pq.[i] in let k,v = e.k,e.v in pq.[i] <- MinHeapTreeEntry (f k v)
        for i = cnt/2 downto 1 do //rebuild by reheapify
          let kv = pq.[i - 1] in let k = kv.k
          let mutable nxtlvl = i in let mutable lvl = nxtlvl
          while (nxtlvl <- nxtlvl <<< 1; nxtlvl < cnt) do
            let lk = pq.[nxtlvl - 1].k in let rk = pq.[nxtlvl].k in let oldlvl = lvl
            let k = if k > lk then lvl <- nxtlvl; lk else k in if k > rk then nxtlvl <- nxtlvl + 1; lvl <- nxtlvl
            if lvl <> oldlvl then pq.[oldlvl - 1] <- pq.[lvl - 1] else nxtlvl <- cnt //causes loop break
          pq.[lvl - 1] <- kv
    pq

Rovelli

Answer 6

There is a discussion of functional data structures for priority queues in issue 16 of The Monad.Reader, which is interesting.

It includes a description of pairing heaps which are fast and very easy to implement.

Nagoya

Answer 7

Just use an F# Set of pairs of your element type with a unique int (to allow duplicates) and extract your elements with set.MinElement or set.MaxElement. All of the relevant operations are O(log n) time complexity. If you really need O(1) repeated access to the minimum element you can simply cache it and update the cache upon insertion if a new minimum element is found.

There are many kinds of heap data structures that you could try (skew heaps, splay heaps, pairing heaps, binomial heaps, skew binomial heaps, bootstrapped variants of the above). For a detailed analysis of their design, implementation and real-world performance see the article Data structures: heaps in The F#.NET Journal.

Charleencharlemagne

The solution I ended up using is a Binomial Heap as described in Okasaki's book. Operations are generally O(log n). Can you tell me the time and memory properties of the F# set to be able to compare? – Bandwidth

@Muhammad: Sets are also logarithmic time. – Charleencharlemagne

What are the time complexities? – Nagoya

Typically one asks for O(1) for access to the min element, since it's the primary operation of a PQ. – Nagoya

@Mau: Inserting 1,000,000 random floats and then removing the smallest element repeatedly until none remain takes 32s with Okasaki's binomial heap in F#, 8s with F#'s built-in Set and 4s with .NET's built-in SortedSet. The difference between O(1) and O(log n) is insignificant in this context. – Charleencharlemagne

@Jon: May be you are right. But you can't decide that a Set is the solution by fiat and then go on accusing others that they don't accept it. A main advantage of a priority queue is O(1) for access. I referred you to the web page before. If in measuring Set works then Ok. Just remember: (1) Your current test is wrong. If you insert all the points then extract then 1 by 1 then you are effectively comparing a heap sort (equivalent to sort using a heap) with whatever sort the set uses. (2) If you can explain the underlying data structure of F# Set then it may be obvious that it is better. – Bandwidth

@Jon: remember that this question did take some time till the answer is accepted. You've got to pu a little more effort in why everybody else got it wrong, if you want to accuse us. – Bandwidth

@Jon: while you are at it. Unlike Set, queues store duplicates. Does F# has a bag data structure that can be used instead of Set with the same functionality but can store duplicates? – Bandwidth

@Muhammad: A Set is implemented as a balanced binary tree and you can map duplicates onto unique elements by augmenting them with a unique ID. – Charleencharlemagne

@Muhammad: I just did another benchmark adding 1,000 elements to a priority queue and then adding a random element and removing the smallest 1,000,000 times: Okasaki's binomial heap took 3s, F#'s Set took 1.9s and SortedSet took 0.9s. So, again, the difference between constant and logarithmic time complexity is overwhelmed by constant factors. – Charleencharlemagne

@Jon: thanks. I quote wikipedia To get better performance, priority queues typically use a heap as their backbone, giving O(log n) performance for inserts and removals. Alternatively, if a self-balancing binary search tree is used, all three operations take O(log n) time; this is a popular solution where one already has access to these data structures, such as through third-party or standard libraries. In particular, a tree enforces more constraints than a heap. Still, your timing results show enough difference that a Set is probably better. I will see if it gives me better results. – Bandwidth

@Jon: In my application the Set behaves 3 times worse than the Binomial heap in the selected answer as a priority queue. As it happens, in my application the custom comparison is the expensive operation, and I wrapped my type in a wrapper as shown here before using Set. You may want to try it with custom comparers. Else publish the small benchmark you used so I can reproduce your results. – Bandwidth

Can you make your wrapper type a struct instead of a class to avoid one level of indirection? What is your actual element type? If you want more performance, .NET's mutable SortedSet is typically a few times faster that F#'s Set because it stores the balanced tree directly in an array. BTW, my code there includes a third test where a binomial heap comes between Set and SortedSet for performance. You might also try other kinds of heap such as a LeftistHeap: flyingfrogblog.blogspot.com/2010/05/… – Charleencharlemagne

FWIW, the leftist heap I just referred you to is not only simpler than a binomial heap in F# but it beats it on all three of my benchmarks. – Charleencharlemagne

@Jon: Sorry I wasn't able to do the tests at the time, life intruded. Thanks for the code. I haven't tried the SortedSet yet because I am not on .Net 4, but the others are performing largely in line with your numbers (scaled by 1.5, uncannily accurately). I will test it on my data, probably with a better design for a wrapper, as well as SortedSet later this week. – Bandwidth

Answer 8

Since version 6.0 .NET finally offers PriorityQueue<TElement,TPriority>

Greaser

I believe I remember correctly from quite some time ago, but don't have the time to verify now: That thing will not necessarily serve the outgoing in the same order they were pushed in, when the priorities are the same. Quite a surprise. Should instead have been named PriorityAndBackwardQueue or PriorityAndRandomQueue or something, just as a reminder. – Glen

@BentTranberg Right, you are absolutely correct! And it's mentioned in the remarks sections if follow the link I provided: "Note that the type does not guarantee first-in-first-out semantics for elements of equal priority." – Greaser

This does not provide an answer to the question. To critique or request clarification from an author, leave a comment below their post. - From Review – Finnegan

Answer 9

With F# you can use any .NET library so if you are ok with using an implementation which is not written in F# I Wintellect Power Collection Library.

Resume

I didn't mention .net generally because I preferred something that I can understand (I don't know C#). Anyway, I had a quick look at the library and I can't find an implementation of a priority queue or a heap. There was a comment in https://mcmap.net/q/116367/-priority-queue-in-net-closed that OrderedBag is usable but less efficient than heaps. Do you have any experience with it? – Bandwidth

The OrderedBag is what you want. It is implemented with a more complex algorithm but that won't really affect its performance in most cases – Resume