The pairing heap is well regarded as an efficient data structure for implementing priority queue operations. It is included in the GNU C++ library. Strikingly simple in design, the pairing heap data structure nonetheless seems difficult to analyze, belonging to the genre of self-adjusting data structures. With its design originating as a self-adjusting analogue of the Fibonacci heap, it has been previously conjectured that the pairing heap provides constrant amortized time decrease-key operations, and experimental studies have supported this conjecture. This paper demonstrates, contrary to conjecture, that the pairing heap requires more than constant amortized time to perform decrease-key operations. Moreover, new experimental findings are presented that reveal detectable growth in the amortized cost of the decrease-key operation. Second, a unifying framework is developed that includes both pairing heaps and Fibonacci heaps. The parameter of interest in this framework is the storage capacity available in the nodes of the data structure for auxiliary balance information fields. In this respect Fibonacci heaps require log log n bits per node when n items are present. This is shown to be asymptotically optimal for data structures that achieve the same asymptotic performance bounds as Fibonacci heaps and fall within this framework.

Article Information theoretic implications for pairing heaps Share on Author: Michael L. Fredman Dept. of Computer Science--Hill Center, Rutgers University, New Brunswick, NJ Dept. of Computer Science--Hill Center, Rutgers University, New Brunswick, NJView Profile Authors Info & Claims STOC '98: Proceedings of the thirtieth annual ACM symposium on Theory of computingMay 1998 Pages 319–326https://doi.org/10.1145/276698.276779Online:23 May 1998Publication History 0citation291DownloadsMetricsTotal Citations0Total Downloads291Last 12 Months1Last 6 weeks0 Get Citation AlertsNew Citation Alert added!This alert has been successfully added and will be sent to:You will be notified whenever a record that you have chosen has been cited.To manage your alert preferences, click on the button below.Manage my AlertsNew Citation Alert!Please log in to your account Save to BinderSave to BinderCreate a New BinderNameCancelCreateExport CitationPublisher SiteGet Access

Let A be an array. The partial sum problem concerns the design of a data structure for implementing the following operations. The operation update (j,x) has the effect $A[j] \leftarrow A[j]+x \,$, and the query operation $\ssum(j)$ returns the partial sum $\sum_{i=1}^j \, A[i] \,$. Our interest centers upon the optimal efficiency with which sequences of such operations can be performed, and we derive new upper and lower bounds in the semigroup model of computation. Our analysis relates the optimal complexity of the partial sum problem to optimal binary trees relative to a type of weighting scheme that defines the notion of biweighted binary tree.

This paper describes a new approach to testing that uses combinatorial designs to generate tests that cover the pairwise, triple, or n-way combinations of a system's test parameters. These are the parameters that determine the system's test scenarios. Examples are system configuration parameters, user inputs and other external events. We implemented this new method in the AETG system. The AETG system uses new combinatorial algorithms to generate test sets that cover all valid n-way parameter combinations. The size of an AETG test set grows logarithmically in the number of test parameters. This allows testers to define test models with dozens of parameters. The AETG system is used in a variety of applications for unit, system, and interoperability testing. It has generated both high-level test plans and detailed test cases. In several applications, it greatly reduced the cost of test plan development.

Let A be an array. The partial sum problem concerns the design of a data structure for implementing the following operations. The operation update(j,x) has the effect, A[j]/spl larr/A[j]+x, and the query operation sum(j) returns the partial sum, /spl Sigma//sub i=1//sup j/A[i]. Our interest centers upon the optimal efficiency with which sequences of such operations can be performed, and we derive new upper and lower bounds in the semi-group model of computation. Our analysis relates the optimal complexity of the partial sum problem to optimal binary trees relative to a type of weighting scheme that defines the notion of bi-weighted binary tree.>

The fusion tree method is extended to develop a linear-time algorithm for the minimum spanning tree problem and an O(m+n log n/log log n) implementation of Dijkstra's shortest-path algorithm for a graph with n vertices and m edges. The shortest-path algorithm surpasses information-theoretic limitations. The extension of the fusion tree method involves the development of a new data structure, the atomic heap. The atomic heap accommodates heap (priority queue) operations in constant amortized time under suitable polylog restrictions on the heap size. The linear-time minimum spanning tree algorithm results from a direct application of the atomic heap. To obtain the shortest path algorithm, the atomic heap is used as a building block to construct a new data structure, the AF-heap, which has no size restrictions and surpasses information theoretic limitations. The AF-heap belongs to the Fibonacci heap family.>

Article Free Access Share on BLASTING through the information theoretic barrier with FUSION TREES Authors: M. L. Fredman Rutgers, Bellcore and UCSD Rutgers, Bellcore and UCSDView Profile , D. E. Willard SUNY at Albany SUNY at AlbanyView Profile Authors Info & Claims STOC '90: Proceedings of the twenty-second annual ACM symposium on Theory of ComputingApril 1990 Pages 1–7https://doi.org/10.1145/100216.100217Published:01 April 1990Publication History 35citation1,119DownloadsMetricsTotal Citations35Total Downloads1,119Last 12 Months86Last 6 weeks4 Get Citation AlertsNew Citation Alert added!This alert has been successfully added and will be sent to:You will be notified whenever a record that you have chosen has been cited.To manage your alert preferences, click on the button below.Manage my Alerts New Citation Alert!Please log in to your account Save to BinderSave to BinderCreate a New BinderNameCancelCreateExport CitationPublisher SiteeReaderPDF

Dynamic data structure problems involve the representation of data in memory in such a way as to permit certain types of modifications of the data (updates) and certain types of questions about the data (queries). This paradigm encompasses many fundamental problems in computer science.

The storage allocation for three stacks has been traditionally accomplished by using pointers to store the stacks as linked lists or by relocating the stacks within memory when collisions take place. The former approach requires additional space to store the pointers, and the latter approach requires additional time. The authors explore the extent to which some additional space or time is required to maintain three stacks. They provide a formal setting for this topic and establish upper and lower complexity bounds on various aspects.>

In this paper we develop a new data structure for implementing heaps (priority queues). Our structure, Fibonacci heaps (abbreviated F-heaps ), extends the binomial queues proposed by Vuillemin and studied further by Brown. F-heaps support arbitrary deletion from an n -item heap in O (log n ) amortized time and all other standard heap operations in O (1) amortized time. Using F-heaps we are able to obtain improved running times for several network optimization algorithms. In particular, we obtain the following worst-case bounds, where n is the number of vertices and m the number of edges in the problem graph: O ( n log n + m ) for the single-source shortest path problem with nonnegative edge lengths, improved from O ( m log ( m/n +2) n ); O ( n 2 log n + nm ) for the all-pairs shortest path problem, improved from O ( nm log ( m/n +2) n ); O ( n 2 log n + nm ) for the assignment problem (weighted bipartite matching), improved from O ( nm log ( m/n +2) n ); O ( mβ ( m, n )) for the minimum spanning tree problem, improved from O ( m log log ( m/n +2) n ); where β ( m, n ) = min { i | log ( i ) n ≤ m/n }. Note that β ( m, n ) ≤ log * n if m ≥ n . Of these results, the improved bound for minimum spanning trees is the most striking, although all the results give asymptotic improvements for graphs of appropriate densities.

In this paper we develop a new data structure for implementing heaps (priority queues). Our structure, Fibonacci heaps (abbreviated F-heaps), extends the binomial queues proposed by Vuillemin and studied further by Brown. F-heaps support arbitrary deletion from an n-item heap in 0(log n) amortized time and all other standard heap operations in 0(1) amortized time. Using F-heaps we are able to obtain improved running times for several network optimization algorithms.

A data structure for representing a set of n items from a umverse of m items, which uses space n + o(n) and accommodates membership queries m constant time is described.Both the data structure and the query algorithm are easy to ~mplement.

The complexity of priority queue operations is analyzed with respect to the cell probe computational model of A. Yao. A method utilizing families of hash functions is developed which permits priority queue operations to be implemented in constant worst case time provided that a size constraint is satisfied. The minimum necessary size of a family of hash functions for computing the rank function is estimated and contrasted with the minimum size required for perfect hashing.

We describe a data structure for representing a set of n items from a universe of m items, which uses space n+o(n) and accommodates membership queries in constant time. Both the data structure and the query algorithm are easy to implement.

Given an array A (k), I _< k <_ N, it is desired to perform two tasks' (a) A (i) ~ A (0 + x, and (b) compute A(I) + A(2) + .-. + A(j), where t, j, and x are arbitrary inputs These tasks are to be performed on-hne Two computational models are defined relative to which computational complexity is assessed' an algebraic model, and an reformation-theoretic model The informatlon-theoreuc complexity measure counts the number of accesses and changes to a random access memory.Upper and lower bounds are derived, and a trade-off between the complexmes of (a) versus (b) is observed Categories and Subject Descriptors: E.!

Let S be an arbitrary commutaUve semigroup (set of elements closed under a commutative and associative addmon operation, +).Given a set of records wtth d-dimensional key vectors over an ordered key space, such that each record has associated with it a value in S, an orthogonal range query is a request for the sum of the values associated with each record in some specified hypercube (cross product of mtervals).Data structures which accommodate inserUons and delettons of records and orthogonal range queries, such that an arbitrary sequence of n such operations takes time O(n(log n)a), have been presented by G. Lueker and D. Wdlard.It is shown here that fi(n(logn) ~) is a lower bound on the inherent worst case time reqmred to process a sequence of n intermixed insemons, deleuons, and range queries, which imphes that the Lueker and Wdlard data structures are in some sense optimal.

A technique is presented for deriving lower bounds on the complexity of optimal data structures which permit insertions and deletions of records, and queries of the form \[ {\text{Query (Region)}};\quad {\text{Return}}\quad \sum_{\begin{subarray}{l} {\text{key}}(r) \\ \in {\text{Region}} \end{subarray}} {{\text{value }}(r)} \quad ({\text{Region}} \in \Gamma ), \] where value$(r)$ (the value associated with a record r) lies in a commutative semi-group S, and $\Gamma $ denotes a set of regions of the space of possible keys. This technique is illustrated with several examples.

Defines and studies a class of on-line algebraic problems; a particular problem in this class is specified by providing ann×nmatrixA. The author shows that the question of algebraic complexity reduces to determining the existence of what he calls (r,u) factorizations ofA. Given ann×nmatrixA, a factorizationA=RU(RandUaren×mandm×nmatrices, respectively;munconstrained) is called an (r,u) factorization, provided that no row ofRhas more thanrnonzero entries and no column ofUhas more thanunonzero entries. The existence of (r,u) factorization is explored from a general perspective.

A formal framework is presented in which to explore the complexity issues of data structures which accommodate various types of range queries. Within this framework, a systematic and reasonably tractable method for assessing inherent complexity is developed. Included among the interesting results are the following: the fact that non-linear lower bounds are readily accessible, and the existence of a complexity gap between linear time and n log n time.

Let G denote the set of elements of a commutative group whose addition operations is denoted by +, let N be a positive integer, and let A(1) ,..., A(N) denote an array with values in G. We will be concerned with designing data structures for representing the array A, which facilitate efficient implementation of the following two on-line tasks:

The purpose of this paper is to develop a decision tree-like model for defining and measuring the on-line complexity of algorithms for generating combinatorial objects. For the purpose of illustration, we consider the problem of generating Gray codes and simple generalizations of Gray codes. We include some results pertaining to the generation of certain special codes and, in addition, we present a trade-off theorem. Our model is information theoretical and we emphasize two aspects of complexity; the amount of information that must be gathered and the amount of data structure update required to generate the successor to a given codeword.

It is shown that $O(N^{5/2} )$ comparisons and additions suffice to solve the all-pairs shortest path problem for directed graphs on N vertices with nonnegative edge weights. In conjunction with preprocessing, this result is exploited to produce an $o(N^3 )$ algorithm for solving the shortest path problem.

Let X = {x1,...,xN} and Y = {y1,...,yN} be sets of N real numbers. We denote by X + Y the multiset {xi + yj; 1 ≤ i, j ≤ N} of size N2. Berklekamp has posed the problem of sorting X + Y. Harper, Payne, Savage and Strauss [1] show that N21og2N comparisons suffice to sort X + Y, thereby saving a factor of 2 over sorting without exploiting the structure of X + Y. (Given u in X + Y, we assume that we know the i,j indices such that u = xi + yj.) Furthermore, they show that this bound is tight for a restricted class of comparison algorithms. However, without their restriction the order of magnitude comparison complexity of this problem has remained an open question. In this paper we show that X + Y can be sorted with O(N2) comparisons. Our proof is unusual for this type of problem in that we do not explicitly exhibit an algorithm. Instead, it is a particular application of a more general search technique whose behavior is easily related to information theoretic lower bounds. In the context of sorting, this search method translates into an insertion sort, where the insertions are not performed by means of the usual binary search, but rather as off-centered searches designed so that each comparison, roughly speaking, equally divides the space of remaining possibilities. We draw attention to this search technique because it might find application to other problems, and we illustrate this possibility with a second application. Our second application concerns the construction of probabilistically balanced binary search trees.