SPEEDES Qheap

Abstract

The Synchronous Parallel Environment for Emulation and Discrete-Event Simulation (SPEEDES) is now using a new general-purpose priority queue data structure called the SPEEDES Qheap for managing its set of pending events in ascending time order. Empirical studies have shown this data structure to outperform more traditional priority queue data structures for large numbers of elements without breaking down.

Two operations are required of the SPEEDES Qheap: (1) Insertion of time-tagged events (time represents a priority of an event -- low time means high priority) and (2) Removal of the event with the smallest time tag. These operations help SPEEDES preserve causality since events, which may generate future events, must always be processed in ascending time order. The SPEEDES Qheap is composed of two lists: (1) a temporary list denoted as Qtemp and (2) a primary list denoted as Qheap.
Insertions are always accomplished in constant time by adding the inserted event to the bottom of Qtemp. The minimum time tag of Qtemp is always maintained. If the newly inserted event has a smaller time tag than the previous value, the minimum time-tag value is updated. Removal of events is more complicated. There are two cases.

Case 1:
If the event with the smallest time tag is in Qtemp, then Qtemp is sorted using a very fast merge-sort algorithm for linked lists. The event with the smallest time tag is removed from Qtemp and returned as the next event. The rest of Qtemp is Metasized into a single Metaitem that is inserted into Qheap. Note that the newly formed metaitem is actually a sorted list of events. The time tag of the metaitem is defined as the time tag of the first event in its sorted list. If the number of metaitems in Qheap ever grows larger than a specified value, S, then the metaitems in Qheap are further metasized into a single metaitem so that the number of metaitems in Qheap is reduced back to one. This helps keep Qheap small enough so that straight insertion of metaitems remains efficient. Metaitems may contain lists of other metaitems, which can contain lists of other metaitems, etc. In this way, Qheap is a recursively linked list data structure that adheres to the heap property.

Case 2:
The event with the smallest time tag is in Qheap. This is more difficult since it is possible that the item removed from the top of Qheap is actually a metaitem itself. If this is so, then the metaitem must be untangled by removing its top item, redefining the rest of the list of the metaitem as a new metaitem, making sure that Qheap does not have more than S elements (if it does, then the elements in Qheap are turned into a single metaitem and placed back into Qheap as a single element), and then inserting this new metaitem back into Qheap. The untangling procedure is repeated until a single event is obtained.

Because heaps are known to have worst-case log2(n) amortized behavior, this data structure should never break down. Also, because it is composed exclusively of linked lists, it should have very low overheads. There are no complicated rotation operations or arbitrary balancing heuristics to apply. This data structure does not require resizable arrays or modular arithmetic schemes either. The only (slightly) complicated part of the SPEEDES Qheap is the untangling procedure (which is actually very straight-forward). Because of its nice properties, the SPEEDES Qheap is highly recommended for general-event list management in discrete-event simulations and for other applications that require general-purpose priority queues. Provided below is a step-by-step procedure for implementing the SPEEDES Qheap.