CODEWITHSUNDEEP
performancealgorithmdata-structuresheappriority-queue
Has QUIT--Anony-Mousse
Has QUIT--Anony-Mousse

Reputation: 77454

Array-backed heap structures for Java

I'm looking for heap structures for priority queues that can be implemented using Object[] arrays instead of Node objects.

Binary heaps of course work well, and so do n-ary heaps. Java's java.util.PriorityQueue is a binary heap, using an Object[] array as storage.

There are plenty of other heaps, such as Fibonacci heaps for example, but as far as I can tell, these need to be implemented using nodes. And from my benchmarks I have the impression that the overhead paid by managing all these node objects comes at a cost that may well eat up all benefits gained. I find it very hard to implement a heap that can comete with the simple array-backed binary heap.

So I'm currently looking for advanced heap / priority queue structures that also do not have the overhead of using Node objects. Because I want it to be fast in reality, not just better in complexity theory... and there is much more happening in reality: for example the CPU has L1, L2 and L3 caches etc. that do affect performance.

My question also focuses on Java for the very reason that I have little influence on memory management here, and there are no structs as in C. A lot of heaps that work well when implemented in C become costly in Java because of the memory management overhead and garbage collection costs.

Upvotes: 3

Views: 782

Answers (1)

templatetypedef
templatetypedef

Reputation: 372684

Several uncommon heap structures can be implemented this way. For example, the Leonardo Heap used in Dijkstra's smoothsort algorithm is typically implemented as an array augmented with two machine words. Like a binary heap, the array representation is an array representation of a specific tree structure (or rather, a forest, since it's a collection of trees).

The poplar heap structure was introduced as a slightly less efficient theoretically but more efficient practically heap structure with the same basic idea - the data is represented as an array with some extra small state information, and is a compressed representation of a forest structure.

A more canonical array-based heap is a d-ary heap, which is a natural generalization of the binary heap to have d children instead of two.

As a very silly example, a sorted array can be used as a priority queue, though it's very inefficient.

Hope this helps!

Upvotes: 3

Related Questions