JHeaps: An open-source library of priority queues

Abstract

Several new heap variants have been introduced in the last two decades. The main research motivation is to match the in-practice performance of pairing heaps while at the same time providing the strong theoretical guarantees of the original fibonacci heap. We present the interface and design of the JHeaps library, a production-ready open-source library of heaps which targets the Java Virtual Machine. The library contains a large number of state-of-the-art implementations of heap variants and properly designed interfaces which allow users to easily interchange and experiment with the performance of different heaps in their applications. Moreover, using the GraalVM for its ahead-of-time compilation together with well-known methodologies such as trace-based simulation, we perform the first large scale experimental study of heaps in a managed environment.

Keywords

• Heap
• Priority queue
• Data structures