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


Vol. 11,  No. 3, pp. 213-216, Jun.  2004
10.3745/KIPSTA.2004.11.3.213


PDF
  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
  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.

Forms

Search
(IN TITLE, AUTHOR, ABSTRACT,KEYWORDS)

Advanced Search ▼

POPULAR KEYWORDS
(TOP 10 KEYWORDS)

Recent Publications
(LAST 3 YEARS)

Old Journals

Indexing

All publications of TKIPS is indexed in DOI, EBSCO, Google Scholar, Crossref, and CrossCheck.

TKIPS is also selected as the Journal for Accreditation by NRF (National Research Foundation of Korea).

Related Journals