Consider using jheaps

[jbduncan]

I was interested by a recent discussion on JGraphT (jgrapht/jgrapht#645) where they discovered that for a certain algorithm, a different sort of heap performed better than the pre-existing one, which lead to a decision to use a heaps data structure library called jheaps.

Should we consider importing jheaps for our own purposes? And should we consider deprecating MapBinaryHeap in the process?

[jrtom]

It's a reasonable question. MapBinaryHeap, however, is a specialized data structure that (as the name implies) combines two different data structures so as to enable operations that aren't part of the heap vocabulary. So while it's possible that we might modify it to use jheaps, we're unlikely to get rid of it entirely.

[jbduncan]

Ah yes, I remember poking around the source code for MapBinaryHeap a few months ago, realising that it implemented Queue but had unique method(s) not on the interface.

If it were me, I'd keep this issue open until jheaps is needed, but I don't know about you. WDYT?

[jrtom]

It's an internal implementation detail IIRC--that is, MBH itself isn't a part of our APIs, although I think it's a public class--so we can certainly swap our our implementation if that seems warranted. I don't mind leaving this open for now; leave a comment if you want to dig into it further and give jheap a test drive. I don't consider this an urgent issue, though.

[jbduncan]

I don't mind leaving this open for now; leave a comment if you want to dig into it further and give jheap a test drive. I don't consider this an urgent issue, though.

Acknowledged!

I'll leave this issue to one side for now. I'm currently doing stuff for Spotless, but once that's done, I'll consider having a go at one of the other issues here. :)