Does anyone have a modern (fast) implementation of a heap data structure handy. If not I'll throw something together using The Tomes.
Does anyone have a modern (fast) implementation of a heap data structure handy. If not I'll throw something together using The Tomes.
http://www.cprogramming.com/tutorial/computersciencetheory/heap.html
http://www.cprogramming.com/tutorial/computersciencetheory/heap.html
Note: in my implementation there are three classes.
ReplyDeleteThe THeap class takes an IComparer parameter which is used to prioritize values. This should be used if the heap's priority is a property of the objects themselves (e.g. prioritizing based on "shoe size" of a person).
Then there is TsmPriorityQueue. This takes an object and a value. This is to be used when the heap's priority isn't a property of the objects (e.g. distance from a location which may vary). I use this structure to implement Dijkstra's algorithm to determine shortest distances.
Finally there is TsmPriorityDictionary. This is a decendant of TsmPriorityQueue, which also has functionality to see if an object is in the Queue, and what value it holds. The value of the object can also changed and the structure will automatically re-balance. This functionality is implemented using a TDictionary instead of searching recursively through the tree.
While considering adding such a data structure to Spring4D I stumbled upon this issue https://github.com/dotnet/corefx/issues/574. Reading the entire thread was quite enlightening, be it the considerations when naming things (should you name after its usage or its implementation?) or the way some API should be designed. Do you implement for the common use case or for specifics.
ReplyDeleteSimilar considerations (while not always) go into what goes into Spring4D and what not. Personally I really dislike feature creep and putting special case things into core libraries (considering Spring.Base which collections are a part of as some kind of RTL extension). First things have to be implemented and tested and even if its open source, someone has to spend its time with it. If in the end a fraction of people will ever use it that time is not well spent. Especially when it comes to data structures if you have a specific use case you most of the time already have built them yourself or you just cannot use the stock types because they don't fit your specific needs.
Anyway back to this case I can see a heap backed TPriorityQueue in Spring4D. I am leaning to a version without being able to update priority and remove specific items or accept those operations to be rather poor performance and possibly hit the wrong items (in terms of allowing duplicates).
Steve Maughan Thanks for you implementation. Delphi is missing in such classes (also linked list, circular buffer, etc.). Spring also does not have enough such structures.
ReplyDelete