The KIPS Transactions:PartA (정보처리학회논문지A)

Korea Information Processing Society (한국정보처리학회)
권호 표지
DOI QR코드

DOI QR Code

8-heap* : A fast 8-ary implicit Priority queue

8-힢*： 빠른 8-원 묵시 우선순위 큐

  • 정해재 (성신여자대학교 컴퓨터정보학부)
  • Published : 2004.06.01
Download PDF
⟨ Previous Next ⟩

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 if shown that a 2-heap, a traditional Implicit PQ based on a binary tree, is slower than an f-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 8-heap as well as 2-heap.

스케줄링이나 정렬과 같은 응용에 이용될 수 있는 우선순위 큐는 포인터를 사용하는 것과 이용하지 않고 묵시적으로 표현하는 두 가지가 있다. 묵시 우선순위 큐는 메모리 이용에 있어서 포인터를 사용하는 것보다 효율적이다. 묵시 우선순위 에는 이진 트리에 근거한 전통적인 2-힙이 있는데, 이는 캐쉬 메모리를 효율적으로 이용하는 8-원 트리에 근거한 8-힙보다 느린 것으로 나타났다. 본 논문에서는 구현하기 쉽고 빠른 새로운 묵시 우선순위 큐인 8-힙＊를 제안한다. 실험을 통하여 8-힙＊가 2-힙 뿐만 아니라 8-힙보다 빠름을 보인다.

Keywords

References

  1. M. Fredman and R. Tarjan, 'Fibonacci heaps and their uses in improved network optimization algorithms,' JACM, 34(3), pp.596-615, 1987 https://doi.org/10.1145/28869.28874
  2. M. Fredrnan, R. Sedgewick, R. Sleator and R. Tarjan, 'The pairing heap: A new form of self-adjusting heap,' Algorithmica, 1, pp.111-129, March, 1986 https://doi.org/10.1007/BF01840439
  3. T. J. Stasko and J. S. Vitter, 'Pairing heaps: experiments and analysis,' Communications of the ACM, 30(3), pp.234-249, 1987 https://doi.org/10.1145/214748.214759
  4. E. Horowitz, S. Sahni and D. Mehta, Fundamentals of Data Structures in C++, W. H. Freeman, San Francisco, 1995
  5. A. LaMarca and R. Ladner, 'The Influence of Caches on the Performance of Heaps,' ACM Jounrnal of Experimental Algorithmics, 1(4), 1996 https://doi.org/10.1145/235141.235145
  6. H. Jung, S. Sahni, 'Supernode binary search trees,' International Journal of Foundations of Computer Science, 14(3), pp.465-490, Jun, 2003 https://doi.org/10.1142/S0129054103001844
  7. D. Jones, 'An empirical companson of prionty-queue and event- set implementation,' Communications of the Association for Computing Machinery, 29(4), pp.300-311, 1986 https://doi.org/10.1145/5684.5686