F# Priority Queue

4
votes

I have tried to use this snippet of code

https://code.msdn.microsoft.com/windowsdesktop/Net-Implementation-of-a-d3ac7b9d

to implement a heap-based implementation of Prim's algorithm to solve the Minimum Spanning Tree (MST) problem in a non-directed connected graph.

after a few iterations, i find that the heap/priority queue is not well maintained anymore. that is the head of the PriorityQueue doesn't have the lowest Key in the Heap.

PQ 0 [-7230, 309]
...
PQ 146 [-7277, 308]

Has anyone use this code and experienced similar problems ? I can post a link on GitHub if anyone would be looking at it

My needs are for a heap datastructure which supports deletion of an element in the middle. It looks like Fsharpx.collections doesnt have such a data structure.

does anybody know a good implementation available somewhere ?

thanks

2
f#heappriority-queue

2 Answers

7
votes

Recently, I ported a MaxHeap from PLINQ to F# here and made it MinHeap. It is array-based and performs much better than any "pure functional" alternative.

However, after a lot of benchmarking, I found that SortedDeque based on just a simple sorted circular buffer performs significantly better on most use cases even when I need to add or delete in the middle.

-1
votes

My answer is inspired by V.B. but here it is in full

I have used another library than FSharpx.collections, it is called

Spreads

read that page for details and instructions.

SortedDeque is the data structure i need for this problem. I used the same code, just changing from the microsoft blog page code to the library functions and found the good result, so it is indeed some bug in the microsoft blog page code

PS. this spreads library has been designed to format financial data for quantitative analysis and i'm happy i found it !!! IT looks like this library is rather recent and thats why its not on top of Google's search or referenced in any other SO question (or if it is i didn't see it)

FSharpx.Collections is of no use for that problem as you can see from that discussion heap issue in FSharpx.Collections