8-heap: A fast 8-ary implicit priority queue


The KIPS Transactions:PartA, Vol. 11, No. 3, pp. 213-216, Jun. 2004
10.3745/KIPSTA.2004.11.3.213,   PDF Download:

Abstract

Proirity queues(PQ) can be used in applications such as scheduling or sorting. The data structures for PQ can be constructed with or without pointers. The implicit representation without pointers uses less memory space than pointer-based representation. It is shown that a 2-heap, a traditional implicit PQ based on a binary tree, is slower than an 8-heap based on a 8-ary tree. This is because 8-heap utilizes cache memory more efficiently. This paper presents a novel fast implicit heap called 8-heap which is easier to implement. Experimental results show that the 8-heap* is faster than 8heap as well as 2-heap.


Statistics
Show / Hide Statistics

Statistics (Cumulative Counts from September 1st, 2017)
Multiple requests among the same browser session are counted as one view.
If you mouse over a chart, the values of data points will be shown.


Cite this article
[IEEE Style]
H. J. Jung, "8-heap: A fast 8-ary implicit priority queue," The KIPS Transactions:PartA, vol. 11, no. 3, pp. 213-216, 2004. DOI: 10.3745/KIPSTA.2004.11.3.213.

[ACM Style]
Hae Jae Jung. 2004. 8-heap: A fast 8-ary implicit priority queue. The KIPS Transactions:PartA, 11, 3, (2004), 213-216. DOI: 10.3745/KIPSTA.2004.11.3.213.