The Pairing Heap: A New Form of Self-Adjusting Heap

被引：120

作者：

Fredman, Michael L. ^{[2
]}

Sedgewick, Robert ^{[1
]}

Sleator, Daniel D. ^{[3
]}

Tarjan, Robert E. ^{[1
,3
]}

机构：

[1] Princeton Univ, Dept Comp Sci, Princeton, NJ 08544 USA

[2] Univ Calif San Diego, Dept EECS, La Jolla, CA 92093 USA

[3] AT&T Bell Labs, Murray Hill, NJ 07974 USA

来源：

ALGORITHMICA | 1986年 / 1卷 / 1-4期

基金：

美国国家科学基金会;

关键词：

Data structure; Heap; Priority queue;

D O I：

10.1007/BF01840439

中图分类号：

TP31 [计算机软件];

学科分类号：

081202 ; 0835 ;

摘要：

Recently, Fredman and Tarjan invented a new, especially efficient form of heap (priority queue) called the Fibonacci heap. Although theoretically efficient, Fibonacci heaps are complicated to implement and not as fast in practice as other kinds of heaps. In this paper we describe a new form of heap, called the pairing heap, intended to be competitive with the Fibonacci heap in theory and easy to implement and fast in practice. We provide a partial complexity analysis of pairing heaps. Complete analysis remains an open problem.

引用

页码：111 / 129

页数：19

共 17 条

[1] IMPLEMENTATION AND ANALYSIS OF BINOMIAL QUEUE ALGORITHMS [J].

BROWN, MR .

SIAM JOURNAL ON COMPUTING, 1978, 7 (03) :298-319

[2] ALGORITHM-245 - TREESORT 3 [M1] [J].

FLOYD, RW .

COMMUNICATIONS OF THE ACM, 1964, 7 (12) :701-701

[3]

FREDMAN ML, J ASS COMPUT M UNPUB

[4]

GABOW HN, COMBINATORI IN PRESS

[5]

GABOW HN, 1984, P 25 ANN IEEE S FDN

[6]

JONES DW, COMM ACM UNPUB

[7]

Knuth, 2010, COMBINATORIAL ALGORI, V4

[8]

Knuth D. E., 1973, ART COMPUTER PROGRAM

[9]

Sleator D.D., 1983, P 15 ANN ACM S THEOR, P235

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

SLEATOR, DD ;

TARJAN, RE .

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

← 1 2 →