The Demarcate Construction: A new form of tree-based priority queues

Abstract

A new form of tree-based priority queues is proposed. These priority queues employ the demarcation process to systematically split a single tree-based priority queue into many smaller trees, each divided by a logical time boundary. These new Demarcate Construction priority queues offer an average speedup of more than twice over the single tree-based counterparts and outperform the current expected O(I) Calendar Queues in many scenarios. Their generality in small to large queue sizes, insensitivity to priority increment distributions and low overhead costs, render them suitable for many applications.