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

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.