4-Deap✽ : A Fast 4-ary Deap using Cache
Haejae Jung · The KIPS Transactions PartA · 2004
Double-ended Proirity queues(DEPQ) can be used in applications such as scheduling or sorting. The data structures for DEPQ can be con-structed with or without pointers. The implicit representation without pointers uses less memory space than pointer-based representation. This paper presents a novel fast implicit heap called 4-deapr which utilizes cache memory efficiently. Experimental results show that the 4-deap is faster than symmetric min-max heap as well as deap.