Theory of 2-3 heaps

被引：11

作者：

Takaoka, T ^{[1
]}

机构：

[1] Univ Canterbury, Dept Comp Sci, Christchurch 1, New Zealand

来源：

DISCRETE APPLIED MATHEMATICS | 2003年 / 126卷 / 01期

关键词：

D O I：

10.1016/S0166-218X(02)00219-6

中图分类号：

O29 [应用数学];

学科分类号：

070104 ;

摘要：

As an alternative to the Fibonacci heap, we design a new data structure called a 2-3 heap, which supports n insert, n delete-min, and m decrease-key operations in O(m + n log n) time. Our experiments show the 2-3 heap is more efficient. The new data structure will have a wide application in graph algorithms. (C) 2002 Elsevier Science B.V. All rights reserved.

引用

页码：115 / 128

页数：14

共 9 条

[1]

ADELSONVELSKII GM, 1962, SOV MATH DOKL, V3, P1259

[2]

Aho A.V., 1974, The Design and Analysis of Computer Algorithms

[3] FASTER ALGORITHMS FOR THE SHORTEST-PATH PROBLEM [J].

AHUJA, RK ;

MEHLHORN, K ;

ORLIN, JB ;

TARJAN, RE .

JOURNAL OF THE ACM, 1990, 37 (02) :213-223

[4]

Bondy J.A., 2008, GRAD TEXTS MATH

[5]

Dijkstra E. W., 1959, NUMER MATH, V1, P269, DOI DOI 10.1007/BF01386390

[6] RELAXED HEAPS - AN ALTERNATIVE TO FIBONACCI HEAPS WITH APPLICATIONS TO PARALLEL COMPUTATION [J].

DRISCOLL, JR ;

GABOW, HN ;

SHRAIRMAN, R ;

TARJAN, RE .

COMMUNICATIONS OF THE ACM, 1988, 31 (11) :1343-1354

[7] FIBONACCI HEAPS AND THEIR USES IN IMPROVED NETWORK OPTIMIZATION ALGORITHMS [J].

FREDMAN, ML ;

TARJAN, RE .

JOURNAL OF THE ACM, 1987, 34 (03) :596-615

[8] SHORTEST CONNECTION NETWORKS AND SOME GENERALIZATIONS [J].

PRIM, RC .

BELL SYSTEM TECHNICAL JOURNAL, 1957, 36 (06) :1389-1401

[9] DATA STRUCTURE FOR MANIPULATING PRIORITY QUEUES [J].

VUILLEMIN, J .

COMMUNICATIONS OF THE ACM, 1978, 21 (04) :309-315

← 1 →