Skip to main content

You are not logged in. Your edit will be placed in a queue until it is peer reviewed.

We welcome edits that make the post easier to understand and more valuable for readers. Because community members review edits, please try to make the post substantially better than how you found it, for example, by fixing grammar or adding additional resources and hyperlinks.

Required fields*

6
  • I have to make a few comments: PriorityQueue is a bit lacking, for example it should be using bulk loading and bulk additions, so I wouldn't take it as a reference. Then even when storing complex objects, the sorting key often is primitive, e.g. an integer or double priority, think of A* search. A 4-ary heap should also work with bitwise operations, just by shifting 2 instead of 1 and have the same overhead. The 4-ary heap is less sorted actually. If you do not empty the heap (e.g. A* search), this actually should save you comparisons. But it clearly depends on the use case. Commented Dec 24, 2012 at 12:10
  • Sounds like you have a specific use case in mind if you can use primitive keys? If so then sure, a specialized n-ary heap with a separate array of primitive keys may be better. A general purpose priority heap in Java would however typically need to work with Comparators or Comparable instances rather than primitive keys. Commented Dec 24, 2012 at 12:17
  • Added a link to an old priority queue implementation I made a while back that uses primitive doouble keys - may be of interest.... Commented Dec 24, 2012 at 12:22
  • Consider A* search for example. How would your compareTo look like? For me it's usually a Double.compare(this.priority, other.priority). I'm not recomputing paths while repairing the heap. Commented Dec 24, 2012 at 12:23
  • Sure that's the compareTo implementation I'd expect in that case. But that is still two references followed. Make those String keys and it is probably four. etc. The point is that following these extra references is extra memory access cost in an n-ary heap (which does more comparisons than a binary heap). Unless you actually copy these keys into an array within the heap itself (see my RankedQueue implementation for an example of this), this probably kills any benefit from cache locality in n-ary heaps. Commented Dec 24, 2012 at 12:46