Please use this identifier to cite or link to this item: http://scholarbank.nus.edu.sg/handle/10635/71968
Title: The Demarcate Construction: A new form of tree-based priority queues
Authors: Goh, R.S.M.
Tang, W.T. 
Thng, I.L.-.J. 
Quieta, M.T.R.
Keywords: Calendar queue
Priority queue
Skew heap
Splay tree
Issue Date: Nov-2004
Source: Goh, R.S.M.,Tang, W.T.,Thng, I.L.-.J.,Quieta, M.T.R. (2004-11). The Demarcate Construction: A new form of tree-based priority queues. Informatica (Ljubljana) 28 (3) : 277-287. ScholarBank@NUS Repository.
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.
Source Title: Informatica (Ljubljana)
URI: http://scholarbank.nus.edu.sg/handle/10635/71968
ISSN: 03505596
Appears in Collections:Staff Publications

Show full item record
Files in This Item:
There are no files associated with this item.

Page view(s)

21
checked on Feb 16, 2018

Google ScholarTM

Check


Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.