FISHSPEAR - A PRIORITY QUEUE ALGORITHM

被引：9

作者：

FISCHER, MJ ^{[1
]}

PATERSON, MS ^{[1
]}

机构：

[1] UNIV WARWICK,DEPT COMP SCI,COVENTRY CV4 7AL,W MIDLANDS,ENGLAND

来源：

JOURNAL OF THE ACM | 1994年 / 41卷 / 01期

关键词：

COMPARISON COUNT; COMPLEXITY ANALYSIS; HEAP; ONLINE ALGORITHM; PRIORITY QUEUE; RUNNING TIME; SEQUENTIAL STORAGE;

D O I：

10.1145/174644.174645

中图分类号：

TP3 [计算技术、计算机技术];

学科分类号：

0812 ;

摘要：

The Fishspear priority queue algorithm is presented and analyzed. Fishspear is comparable to the usual heap algorithm in its worst-case running time, and its relative performance is much better in many common situations. Fishspear also differs from the heap method in that it can be implemented efficiently using sequential storage such as stacks or tapes, making it potentially attractive for implementation of very large queues on paged memory systems.

引用

页码：3 / 30

页数：28

共 8 条

[1]

Aho A. V., 1974, DESIGN ANAL COMPUTER

[2] A VARIANT OF HEAPSORT WITH ALMOST OPTIMAL NUMBER OF COMPARISONS [J].

CARLSSON, S .

INFORMATION PROCESSING LETTERS, 1987, 24 (04) :247-250

[3] HEAPS ON HEAPS [J].

GONNET, GH ;

MUNRO, JI .

SIAM JOURNAL ON COMPUTING, 1986, 15 (04) :964-971

[4] COMMUNICATING SEQUENTIAL PROCESSES [J].

HOARE, CAR .

COMMUNICATIONS OF THE ACM, 1978, 21 (08) :666-677

[5] SELF-ADJUSTING HEAPS [J].

SLEATOR, DD ;

TARJAN, RE .

SIAM JOURNAL ON COMPUTING, 1986, 15 (01) :52-69

[6] SELF-ADJUSTING BINARY SEARCH-TREES [J].

SLEATOR, DD ;

TARJAN, RE .

JOURNAL OF THE ACM, 1985, 32 (03) :652-686

[7] AMORTIZED EFFICIENCY OF LIST UPDATE AND PAGING RULES [J].

SLEATOR, DD ;

TARJAN, RE .

COMMUNICATIONS OF THE ACM, 1985, 28 (02) :202-208

[8]

WILLIAMS JWJ, 1964, COMMUN ACM, V7, P347

← 1 →