The d-deap*: a fast and simple cache-aligned d-ary deap

详细信息    查看全文

• 作者：Jung ; Haejae
• 关键词：Data structures ; Double-ended priority queue ; Deap
• 刊名：Information Processing Letters
• 出版年：2005
• 出版时间：January 31, 2005
• 年：2005
• 卷：93
• 期：2
• 页码：63-67
• 全文大小：122 K

文摘

This paper presents a generalized and cache-aligned implicit version of the deap, called d-deap* that utilizes cache memory efficiently. The d-deap* is based on a tree structure that may be mapped into a cache-aligned array without padding. This results in a match between node indexes and array indexes as well as good cache utilization. Experimental results show that the d-deap* clearly outperforms the symmetric min-max heap and deap structures proposed earlier for double-ended priority queues.