# Handbook of Data Structures and Applications (Chapman & Hall/CRC Computer and Information Science Series)

Language: English

Pages: 1392

ISBN: 1584884355

Format: PDF / Kindle (mobi) / ePub

Although there are many advanced and specialized texts and handbooks on algorithms, until now there was no book that focused exclusively on the wide variety of data structures that have been reported in the literature. The Handbook of Data Structures and Applications responds to the needs of students, professionals, and researchers who need a mainstream reference on data structures by providing a comprehensive survey of data structures of various types.

Divided into seven parts, the text begins with a review of introductory material, followed by a discussion of well-known classes of data structures, Priority Queues, Dictionary Structures, and Multidimensional structures. The editors next analyze miscellaneous data structures, which are well-known structures that elude easy classification. The book then addresses mechanisms and tools that were developed to facilitate the use of data structures in real programs. It concludes with an examination of the applications of data structures.

The Handbook is invaluable in suggesting new ideas for research in data structures, and for revealing application contexts in which they can be deployed. Practitioners devising algorithms will gain insight into organizing data, allowing them to solve algorithmic problems more efficiently.

stated as follows: Graphs 4-23 for l ← 1 to n do for i ← 1 to n do if wil = ∞ then for j ← 1 to n do wij ← min{wij , wil + wlj } end for end if end for end for FIGURE 4.20: All-pairs shortest distance algorithm. If the network has no negative-weight cycle, the diagonal entries w (n) ii represent the length (n) of shortest cycles passing through vertex i. The oﬀ-diagonal entries w ij are the shortest distances. Notice that negative weight of an individual edge has no eﬀect on this

depicted in Figure 7.2(c): Bk consists of a root and subtrees (in order from left to right) Bk−1 , Bk−2 , · · · , B0 . The root of the binomial tree Bk has k children, and the tree is said to have rank k. We also observe that the height of Bk (maximum number of edges on any path directed away from the root) is k. The k descendants name “binomial heap” is inspired by the fact that the root of Bk has j at distance j. Binomial, Fibonacci, and Pairing Heaps (a) Recursion for binomial trees. 7-3

Workshop on Algorithms and Data Structures (1991), 400–411. [12] S. Pettie and V. Ramachandran, An Optimal Minimum Spanning Tree Algorithm, Journal of the ACM 49 (2002), 16–34. [13] J. Vuillemin, A Data Structure for Manipulating Priority Queues, Communications of the ACM , 21 (1978), 309–314. [14] M. A. Weiss, Data Structures and Algorithms in C , 2d ed., Addison-Wesley, Reading MA., 1997. 8 Double-Ended Priority Queues 8.1 8.2 8.3 Deﬁnition and an Application . . . . . . . . . . . . . . . .

the left subtree, we use the standard min-heap trickle-up process beginning at node i. This results in the conﬁguration of Figure 8.23. To insert newElement = 19 into the deap of Figure 8.22, we check the correspondence property between 15 and 19. The property is satisﬁed. So, we use the trickle-up process for max heaps to correctly position newElement in the max heap. Figure 8.24 shows the result. Since the height of a deap is Θ(log n), the time to insert into a deap is O(log n). 8-18

searching the table positions x0 , x1 , x2 . . . in order. Perfect hash functions seem to have been ﬁrst studied by Sprugnoli [58] who gave some heuristic number theoretic constructions of minimal perfect hash functions for small data sets. Sprugnoli is responsible for the terms “perfect hash function” and “minimal perfect hash function.” A number of other researchers have presented algorithms for discovering minimal and near-minimal perfect hash functions. Examples include Anderson and Anderson