Calendar queue
≈ 3 min read
Names in other languages
No names in other languages are held for this entry yet.
Article bodies are English and are not machine-translated. A name in another language is not a translation of the article.
A calendar queue (CQ) is a priority queue (queue in which every element has associated priority and the dequeue operation removes the highest priority element). It is analogous to desk calendar, which is used by humans for ordering future events by date. Discrete event simulations require a future event list (FEL) structure that sorts pending events according to their time. Such simulators require a good and efficient data structure as time spent on queue management can be significant. The calendar queue (with optimum bucket size) can approach O(1) average performance. Calendar queues are closely related to bucket queues but differ from them in how they are searched and in being dynamically resized.
A calendar queue (CQ) is a priority queue (queue in which every element has associated priority and the dequeue operation removes the highest priority element). It is analogous to desk calendar, which is used by humans for ordering future events by date. Discrete event simulations require a future event list (FEL) structure that sorts pending events according to their time. Such simulators require a good and efficient data structure as time spent on queue management can be significant. The calendar queue (with optimum bucket size) can approach O(1) average performance. Calendar queues are closely related to bucket queues but differ from them in how they are searched and in being dynamically resized. If the number of events in the queue is much smaller or much larger than the number of buckets, it will not function efficiently. The solution is to allow the number of buckets to correspondingly grow and shrink as the queue grows and shrinks. To simplify the resize operation, the Nb (number of buckets) in a CQ is often chosen to be the power of two, i.e., Nb=2^n ;↵ The number of buckets is doubled or halved each time the Ne (number of events) exceeds 2Nb or decreases below Nb/2 respectively. When Nb is resized, the new width w has to be calculated as well. The new w that is adopted will be estimated by sampling the average inter-event time gap from the first few hundred events starting at the current bucket position. Thereafter, a new Calendar queue is created and all the events in the old calendar will be recopied over.
Text derived from https://en.wikipedia.org/w/index.php?oldid=1278349479 under CC BY-SA 4.0; modifications have been made.