Dynamic cost-based multi-tier linked list

Abstract

Priority queues are widely employed in numerous applications such as discrete event simulations (DESs). The priority queue structure plays a paramount role of managing the pending event set of a DES. The priority queue contains events where the minimum timestamp event has the highest priority and the maximum timestamp event has the lowest priority. A Calendar Queue (CQ) is a useful structure often employed in DESs. Its popularity is due to its expected O(1) access time for many simulation scenarios, provided the events are evenly distributed in the CQ structure. However, for skewed distributions, it is likely that many events fall into some few buckets in the CQ structure. This may cause the performance of the CQ to deteriorate to O(n). Furthermore, the CQ's resize operation necessary to handle fluctuating queue sizes is costly as it copies all the already sorted events from the old CQ structure to a newly-created one. This article introduces a novel priority queue implementation known as the Dynamic Cost-based Multi-Tier Linked List (DynamicList) structure which does not require the resize operation to obtain near O(1) performance. The DynamicList is empirically shown to be on the average at least 100% faster than all the current priority queues. In some scenarios, the DynamicList is more than one magnitude faster. These evidence suggest strongly that it is an excellent candidate to be widely employed in DESs.