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 Q _{temp} *and (2) a primary list denoted as

*Q*

_{heap}.Insertions are always accomplished in constant time by adding the inserted event to the bottom of *Q _{temp}. *The minimum time tag of

*Q*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.

_{temp}#### Case 1:

If the event with the smallest time tag is in *Q _{temp}*, then

*Q*is sorted using a very fast merge-sort algorithm for linked lists. The event with the smallest time tag is removed from

_{temp}*Q*and returned as the next event. The rest of

_{temp }*Q*is Metasized into a single Metaitem that is inserted into

_{temp}*Q*. 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

_{heap}*Q*ever grows larger than a specified value,

_{heap}*S*, then the metaitems in

*Q*are further metasized into a single metaitem so that the number of metaitems in

_{heap}*Q*is reduced back to one. This helps keep

_{heap}*Q*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,

_{heap}*Q*is a recursively linked list data structure that adheres to the heap property.

_{heap}#### Case 2:

The event with the smallest time tag is in *Q _{heap}*. This is more difficult since it is possible that the item removed from the top of

*Q*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

_{heap}*Q*does not have more than

_{heap}*S*elements (if it does, then the elements in

*Q*are turned into a single metaitem and placed back into

_{heap }*Q*as a single element), and then inserting this new metaitem back into

_{heap}*Q*. The untangling procedure is repeated until a single event is obtained.

_{heap}Because heaps are known to have worst-case *log _{2}(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.*

*SPEEDES Qheap* Insertion

- Place the event to be inserted at the end of the
*Q*._{temp} - Update
*T*if this item has the smallest time tag out of all the items in_{min}*Q*._{temp}

*SPEEDES Qheap* Removal

- Check if
*T*is less than the time tag of the next item in_{min}*Q*. If so, perform steps a through f and then return. Otherwise, go on to step 2._{heap}- Sort
*Q*and then set_{temp}*T*to infinity._{min } - Remove the top element (this is what is returned as the next event) and call it
*NextEvent*. - Metasize the rest of the elements from
*Q*into a new metaitem called_{temp }*Meta*._{temp} - Check if
*Q*already contains_{heap}*S*elements. If it does, metasize all of its elements into a new metaitem and place it back into*Q*as its only element._{heap} - Insert
*Meta*into_{temp}*Q*._{heap} - Return
*NextEvent*.

- Sort
- Remove the top item from
*Q*and call it_{heap }*NextItem*. Then loop over steps a through e below until*NextItem*is not a metaitem.- Check if
*NextItem*is a metaitem. If not, then break out of the loop and return*NextItem*as the*NextEvent.*Otherwise, we know that*NextItem*is a metaitem which must be untangled in the steps b-e below. - Remove the top element from
*NextItem*and call it*NewItem. NextItem*now contains one less item. If*NextItem*has only a single element, then unmetasize it so that*NextItem*is a regular item. - Check if
*Q*already contains_{heap}*S*elements. If it does, metasize all of its elements into a new metaitem and place it back into*Q*as its only element._{heap} - Insert
*NextItem*into*Q*_{heap}. - Set
*NextItem*=*NewItem*and then go back to a.

- Check if

*This work was done by Jeffrey S. Steinman of Caltech for *NASA's Jet Propulsion Laboratory*. For further information, access the Technical Support Package (TSP) free on-line at www.techbriefs.com under the category Information Sciences*

*NPO-20095*

##### NASA Tech Briefs Magazine

This article first appeared in the January, 1999 issue of *NASA Tech Briefs* Magazine.

Read more articles from the archives here.