PriorityQueue/Heap with Removal of an element in the middle (not head only) about fsharpx.collections HOT 14 CLOSED

1. in the proposed implementation, those operations ARE necessary
2. fyi there is a very nice library called https://github.com/Spreads/Spreads
   which has a datastructure (SortedDeque) which supports those operations.

i have used that library instead of FSharpx.Collections

from fsharpx.collections.

Yes FSharpx.Collections contains multiple heap implementd and a priority
queue.
On Mar 24, 2016 7:57 AM, "FaguiCurtain" [email protected] wrote:

Hi
this is not an issue about a bug. Rather i'm a bit lost, and I'd like to
know if among the data structures implemented in this library, there is a
heap-like data structure supporting removal of an element, and perhaps
finding an element as well.

something like

https://code.msdn.microsoft.com/windowsdesktop/Net-Implementation-of-a-d3ac7b9d
however i have some reasons to believe the code above has some bugs.

I've googled to look for implementations elsewhere and couldn't find any,
or at least any that i was able to use.

—
You are receiving this because you are subscribed to this thread.
Reply to this email directly or view it on GitHub
#61

from fsharpx.collections.

Heap<'T> supports insertion but not deletion of an element in the middle of the heap. it just enables removal of the Head.

from fsharpx.collections.

Ah I see you meant in the middle. Yes that's not a operation that heaps
support.
On Mar 24, 2016 8:01 AM, "FaguiCurtain" [email protected] wrote:

Heap<'T> supports insertion but not deletion of an element in the middle
of the heap. it just enables removal of the Head.

—
You are receiving this because you commented.
Reply to this email directly or view it on GitHub
#61 (comment)

from fsharpx.collections.

ok so in the standard implementation its not implemented but it would be useful to provide such functionality i believe in at least Heap<'T>
in the meanwhile do you know of some bug-free implementation available elsewhere ?

from fsharpx.collections.

No I don't agree here. A heap is a well known data structure and removement
of arbitrary elements is nothing it can support well. If you need such
deletion then your use case is probably requiring a different data
structures.

That said: if perf doesn't matter for you then you can remove the element
via a seq function and rebuild the heap.
On Mar 24, 2016 8:06 AM, "FaguiCurtain" [email protected] wrote:

ok so in the standard implementation its not implemented but it would be
useful to provide such functionality i believe in at least Heap<'T>
in the meanwhile do you know of some bug-free implementation available
elsewhere ?

—
You are receiving this because you commented.
Reply to this email directly or view it on GitHub
#61 (comment)

from fsharpx.collections.

well perf patters, otherwise heaps are useless !

i'm just a noobie, Im making a request. you could give another name than heap to it, make it support everything that heap already does, and allow for insertion

fyi, i'm studying on Coursera Algo I and II from Stanford (Tim Roughgarden)
there are lectures and programming exercises, and we need to use such heaps with removal for the suggested implementation of 1- Djikstra's shortest path algorithm 2- Prim's algorithm for Minimum Spanning Tree in a directed graph

The code from MSN in the link above would have done the job, but it seems there is a bug, and i don't know where it comes from, i could upload something on GitHub if anyone wants to have a look

from fsharpx.collections.

My computer science classes are long time ago but IIRC prim' and dijkstra's don't remove arbitrary elements but the element from the front. The rest can be done with sets.

from fsharpx.collections.

well, there is not a unique implementation of Djikstras or Prims algo.
I'm talking about the one which can be found here (for Prim). Djikstra is very similar.
https://class.coursera.org/algo2-004/lecture/35

the PriorityQueue class from MSDN above has the following members

PQ.IndexOf (Returns the index of a given key value pair)
PQ.RemoveAt (Removes the element at the specified index value)

From Pr. Roughgarden
IMPLEMENTATION NOTES: This graph is small enough that the straightforward O(mn) time
implementation of Prim's algorithm should work fine. OPTIONAL: For those of you seeking an
additional challenge, try implementing a heapbased
version. The simpler approach, which
should already give you a healthy speedup,
is to maintain relevant edges in a heap (with keys
= edge costs). The superior approach stores the unprocessed vertices in the heap, as
described in lecture.** Note this requires a heap that supports deletions, and you'll probably need
to maintain some kind of mapping between vertices and their positions in the heap.**

from fsharpx.collections.

well we don't support that

from fsharpx.collections.

well i can guess you have already a lot of work and a lot of requests, but I hope that you will be able to look into this and implement something in the near future.

thanks vm

from fsharpx.collections.

why don't you try it yourself? I mean that's was basically the homework. Prim's and Dijktra's algorithm are pretty trivial to implement if the PQ is given, Where is the fun?

from fsharpx.collections.

believe me, if i could, i would do it. I'm 44 and left university 20 years ago and not done programming since. I've started F# only in december and I promise you I've spent tens or hundreds of hours and hours studying already, completing Algo I and I've written several thousands of lines of codes. F# is my first serious language (i studied Turbo Pascal 25 years ago....), other MOOCs i was doing stuff in R which is not really suited for this.

I've implemented for example UnionFind which could have its place in this library (maybe its already there in some form ?). But for example, if my implementation works for a specific problem, im not completely familiar yet with syntax for libraries.

The problem is not the homework itself, i already know the answer. despite my lack of experience, i feel heaps is a very basic object, and allowing for removal of an object in the middle doesn't seem like an extravagant request. perhaps others than me would like it. After all, a sample was on a Microsoft page. [but its bugged (or not ?) and not been tested and retested by the community]

the code from MSDN seemed to work, and my program worked on small enough graphs (50 nodes), but i can't tell why does not on the bigger graph (500 nodes). its not doing extractmin properly.
It does look well written but I cannot tell where its bugged. Of course you could suspect my code is responsible for that, but I've audited that and done execution step per step vs the program of a pro in Lisp who gave the correct answer, we diverged after 140 iterations.

and i could see by very eyes that at the 141st iteration when i did PQ.Dequeue()
it wasn't extracting the element with lowest Key.

from fsharpx.collections.

Since this is not a supported priority queue operation and the mentioned algorithms dot need it I think it's better to close this. Sorry

from fsharpx.collections.