Fourth Edition Data Structures and Algorithm Analysis in C ++ This page intentionally left blank Fourth Edition Data Structures and Algorithm Analysis in C ++ Mark Allen Weiss Florida International University Boston Columbus Indianapolis New York San Francisco Upper Saddle River Amsterdam Cape Town Dubai London Madrid Milan Munich Paris Montreal Toronto Delhi Mexico City Sao Paulo Sydney Hong Kong Seoul Singapore Taipei Tokyo Editorial Director, ECS: Marcia Horton Executive Editor: Tracy Johnson Editorial Assistant: Jenah Blitz-Stoehr Director of Marketing: Christy Lesko Marketing Manager: Yez Alayan Senior Marketing Coordinator: Kathryn Ferranti Marketing Assistant: Jon Bryant Director of Production: Erin Gregg Senior Managing Editor: Scott Disanno Senior Production Project Manager: Marilyn Lloyd Manufacturing Buyer: Linda Sager Art Director: Jayne Conte Cover Designer: Bruce Kenselaar Permissions Supervisor: Michael Joyce Permissions Administrator: Jenell Forschler Cover Image: c De-kay | Dreamstime.com Media Project Manager: Renata Butera Full-Service Project Management: Integra Software Services Pvt Ltd Composition: Integra Software Services Pvt Ltd Text and Cover Printer/Binder: Courier Westford Copyright c 2014, 2006, 1999 Pearson Education, Inc., publishing as Addison-Wesley All rights reserved Printed in the United States of America This publication is protected by Copyright, and permission should be obtained from the publisher prior to any prohibited reproduction, storage in a retrieval system, or transmission in any form or by any means, electronic, mechanical, photocopying, recording, or likewise To obtain permission(s) to use material from this work, please submit a written request to Pearson Education, Inc., Permissions Department, One Lake Street, Upper Saddle River, New Jersey 07458, or you may fax your request to 201-236-3290 Many of the designations by manufacturers and sellers to distinguish their products are claimed as trademarks Where those designations appear in this book, and the publisher was aware of a trademark claim, the designations have been printed in initial caps or all caps Library of Congress Cataloging-in-Publication Data Weiss, Mark Allen Data structures and algorithm analysis in C++ / Mark Allen Weiss, Florida International University — Fourth edition pages cm ISBN-13: 978-0-13-284737-7 (alk paper) ISBN-10: 0-13-284737-X (alk paper) C++ (Computer program language) Data structures (Computer science) Computer algorithms I Title QA76.73.C153W46 2014 005.7 3—dc23 2013011064 10 www.pearsonhighered.com ISBN-10: 0-13-284737-X ISBN-13: 978-0-13-284737-7 To my kind, brilliant, and inspiring Sara This page intentionally left blank CO NTE NTS Preface xv Chapter Programming: A General Overview 1.1 What’s This Book About? 1.2 Mathematics Review 1.2.1 Exponents 1.2.2 Logarithms 1.2.3 Series 1.2.4 Modular Arithmetic 1.2.5 The P Word 1.3 A Brief Introduction to Recursion 1.4 C++ Classes 12 1.4.1 Basic class Syntax 12 1.4.2 Extra Constructor Syntax and Accessors 13 1.4.3 Separation of Interface and Implementation 16 1.4.4 vector and string 19 1.5 C++ Details 21 1.5.1 Pointers 21 1.5.2 Lvalues, Rvalues, and References 23 1.5.3 Parameter Passing 25 1.5.4 Return Passing 27 1.5.5 std::swap and std::move 29 1.5.6 The Big-Five: Destructor, Copy Constructor, Move Constructor, Copy Assignment operator=, Move Assignment operator= 30 1.5.7 C-style Arrays and Strings 35 1.6 Templates 36 1.6.1 Function Templates 37 1.6.2 Class Templates 38 1.6.3 Object, Comparable, and an Example 39 1.6.4 Function Objects 41 1.6.5 Separate Compilation of Class Templates 44 1.7 Using Matrices 44 1.7.1 The Data Members, Constructor, and Basic Accessors 44 1.7.2 operator[] 45 vii viii Contents 1.7.3 Big-Five 46 Summary 46 Exercises 46 References 48 Chapter Algorithm Analysis 2.1 2.2 2.3 2.4 51 Mathematical Background 51 Model 54 What to Analyze 54 Running-Time Calculations 57 2.4.1 A Simple Example 58 2.4.2 General Rules 58 2.4.3 Solutions for the Maximum Subsequence Sum Problem 60 2.4.4 Logarithms in the Running Time 66 2.4.5 Limitations of Worst-Case Analysis 70 Summary 70 Exercises 71 References 76 Chapter Lists, Stacks, and Queues 3.1 Abstract Data Types (ADTs) 77 3.2 The List ADT 78 3.2.1 Simple Array Implementation of Lists 78 3.2.2 Simple Linked Lists 79 3.3 vector and list in the STL 80 3.3.1 Iterators 82 3.3.2 Example: Using erase on a List 83 3.3.3 const_iterators 84 86 3.4 Implementation of vector 3.5 Implementation of list 91 3.6 The Stack ADT 103 3.6.1 Stack Model 103 3.6.2 Implementation of Stacks 104 3.6.3 Applications 104 3.7 The Queue ADT 112 3.7.1 Queue Model 113 3.7.2 Array Implementation of Queues 113 3.7.3 Applications of Queues 115 Summary 116 Exercises 116 77 Contents Chapter Trees 121 4.1 Preliminaries 121 4.1.1 Implementation of Trees 122 4.1.2 Tree Traversals with an Application 123 4.2 Binary Trees 126 4.2.1 Implementation 128 4.2.2 An Example: Expression Trees 128 4.3 The Search Tree ADT—Binary Search Trees 132 4.3.1 contains 134 4.3.2 findMin and findMax 135 4.3.3 insert 136 4.3.4 remove 139 4.3.5 Destructor and Copy Constructor 141 4.3.6 Average-Case Analysis 141 4.4 AVL Trees 144 4.4.1 Single Rotation 147 4.4.2 Double Rotation 149 4.5 Splay Trees 158 4.5.1 A Simple Idea (That Does Not Work) 158 4.5.2 Splaying 160 4.6 Tree Traversals (Revisited) 166 4.7 B-Trees 168 4.8 Sets and Maps in the Standard Library 173 4.8.1 Sets 173 4.8.2 Maps 174 4.8.3 Implementation of set and map 175 4.8.4 An Example That Uses Several Maps 176 Summary 181 Exercises 182 References 189 Chapter Hashing 5.1 5.2 5.3 5.4 General Idea 193 Hash Function 194 Separate Chaining 196 Hash Tables without Linked Lists 201 5.4.1 Linear Probing 201 5.4.2 Quadratic Probing 202 5.4.3 Double Hashing 207 5.5 Rehashing 208 5.6 Hash Tables in the Standard Library 210 193 ix Index Borodin, A., 529 Boruvka, O., 445 Bottom-up insertion in red-black trees, 567–568 Bound times, amortized, 533, 551–552 Bounds of function growth, 52 Boyer, R S., 243 Braces ({ }), balancing, 104–105 Brackets ([ ]) balancing, 104–105 operator See Operators Breadth-first searches, 389 Bright, J D., 289 Brodal, G S., 289 Broder, A., 242 Brown, D J., 531 Brown, M R., 289, 558 Brualdi, R A., 48 Bucket sort, 331–336 buildBinomialQueue function, 537 buildHeap function for binary heaps, 248, 255–257 for heapsorts, 301 for Huffman algorithm, 458–459 for leftist heaps, 265 Burch, N., 531 C C++ call-by-rvalue-reference, 27 copy-and-swap idiom, 34 decltype, 86, 294 lvalue, 23–24, 26–29, 31 lvalue reference, 23–24, 26, 28 move assignment operator, 30–31, 33, 35 move constructor, 30–32, 34–35, 87 range for loop, 21, 25, 177 rvalue, 23–24, 27–29, 31 rvalue reference, 23–24, 27–28 size_t, 197–199, 205, 212, 220–221, 226 std::move, 29–30 std::swap, 29–30 unordered_map, 181, 210–212, 405 unordered_set, 210–212 C-style arrays and strings, 35–36 call-by-rvalue-reference, 27 Calls, stacks for, 110–112 capacity function for binomial queues, 277 for vectors, 81, 90–91 Carlsson, S., 289 Carmichael numbers, 504 Carter, J L., 242, 244 Carter-Wegman trick, 233 Cartesian trees, 612 Cascading cuts for Fibonacci heaps, 548 CaseInsensitiveCompare class, 174 Catalan numbers, 487 Chaining for hash tables, 196–200 Chang, H., 613 Chang, L., 529 Chang, S C., 289 change function, 84 Chanzy, P., 613 Character sets, 454 Character substitution problem, 176–181 Characters, arrays of, 34 Chazelle, B., 446 Checkers, 514 Chen, J., 289 Cheriton, D., 289, 446 Cheriyan, J., 446 Chess, 514, 526 Children in trees, 121–123 Christofides, N., 529 Circle packing problem, 522 Circular arrays, 113 Circular linked lists, 120 Circular logic, recursion as, Classes and class templates, 12, 38–39 accessors for, 15 compilation, 44, 615–616 explicit instantiation, 616–618 constructors for, 13–16, 31 defaults for, 31–35 destructors for, 30–31 interface/implementation separation in, 16–18 string and vector, 19–21 syntax for, 20 clear function 621 for containers, 81 for lists, 93–94 for priority queues, 282–283 for vectors, 87–88 Cleary, J G., 528 Clique problem, 444 Clocks for event simulation, 259–260 for random numbers, 496 clone function for binary search trees, 142 for binomial queues, 277 for leftist heaps, 265 for red-black trees, 571 for top-down splay trees, 563 Closest points problem divide and conquer strategy, 467–482 references for, 527 Clustering in hash tables, 201, 207 Code bloat, 37 Cohen, J., 242 Coin changing problem, 392 Collections, 80 Collisions in hashing, 194–196, 200 double hashing, 207–208 linear probing, 201–202, 209 quadratic probing, 202–207 Coloring graphs, 436 combineSiblings function, 603, 606 combineTrees function, 277–280 Comer, D., 190 Commands, preprocessor, 16–18 Comparable objects, 39–41 for binary search trees, 132 compareAndLink function, 603 Comparison-based sorting, 291 Comparisons arrays, 17 with iterators, 83 pointers, 21 in selection problem, 477–478 strings, 17 Compilation, 44–46, 615–616 explicit instantiation in, 616–618 hash tables for, 237 for header information, 616 622 Index Complete binary trees, 247, 254 Complete graphs, 380 Compound interest rule in recursion, 11 Compression file, 453 path, 360–371 Computational geometry in divide and conquer strategy, 468 turnpike reconstruction, 506–511 Computational models, 54 computeAdjacentWords function, 178–180 Congruential generators, 496, 499 Connected graphs, 380 Connectivity biconnected graphs, 421 electrical, 351 undirected graphs, 420–421 Consecutive statements in running time, 58 const keyword, 18 const_iterators, 83–86, 92–93, 96–97 Constant growth rate, 53 Constant member functions, 15–16 Constant reference parameter passing by, 26 returning values by, 25 Constructors, 13 copy, 31, 141 default parameters, 13 explicit, 15 for iterators, 82–83 for matrices, 44–45 Containers, 80–81, 83 See also Lists; Queues; Stacks contains function for binary search trees, 135 for binary searches, 68 for hash tables, 196, 200, 205–206 for top-down splay trees, 563 continue reserved word, 132 Contradiction, proofs by, 7–8 Convergent series, Conversions infix to postfix, 108–110 type, 14 Convex hulls, 523 Convex polygons, 523 Cook, S., 436, 446 Cook’s theorem, 436 Copies for vectors, 89 Coppersmith, D., 529 copy-and-swap idiom, 34 Copy assignment operators, 31–33 for binary search trees, 141 for matrices, 46 Copy constructors, 24 for iterators, 77 for matrices, 39 copy function, 45 Copying matrices, 45 shallow and deep, 32–33 Costs, graph edges, 379 Counterexample, proofs by, Counters in mergesorts, 304–305 Counting radix sort, 332–336 countingRadixSort method, 334 Crane, C A., 288, 289 createSuffixArray routines, 593–599 Critical paths, 404 Cross edges, 429 Cryptography gcd algorithm in, 71 prime numbers for, 503–504 Cubic growth rate, 53 Cuckoo hashing, 215–217, 222–224, 226 CuckooHashTable class, 221–227 Culberson, J., 189, 190 Culik, K., 190 Current nodes for lists, 92 Cutting nodes in leftist heaps, 542–544 D d-heaps, 260–261 DAGs (directed acyclic graphs), 379–380 Data members for matrices, 44–45 Day, A C., 613 Deap queues, 288 Decision trees for lower bounds, 323–325 references for, 348 Declaring objects, 18 pointers, 21 decltype, 86, 294 decreaseKey function for binary heaps, 254 for binomial queues, 278 for Dijkstra’s algorithm, 399 for Fibonacci heaps, 542–544, 548–551 for pairing heaps, 602–606 Deep copies vs shallow, 32 for vectors, 87 Defaults for constructor parameters, 13–14 problems with, 33–35 Definitions, recursion in, delete function for binary search trees, 141 for lists, 100 Delete operations 2-d trees, 549–552 AVL trees, 144–158 binary heaps, 247–257 binary search trees, 67–68, 126, 132–144 binomial queues, 271–281, 535 d-heaps, 260–261 destructors with, 23–24 Fibonacci heaps, 399–400 hash tables, 194–196 heapsorts, 273–274 leftist heaps, 261–268, 543 linked lists, 73–74 lists, 72, 85, 87, 92–93 multiway merges, 338–339 pairing heaps, 258, 553–559, 563 pointers, 19–20 priority queues, 245–283 red-black trees, 566–576 sets, 165–166 skew heaps, 269–271 skip lists, 459–461 Index splay trees, 158–166 treaps, 576–579 vectors, 28, 86–91 deleteKey function, 254 deleteMax function, 300, 301, 303 deleteMin function binary heaps, 251–253 binomial queues, 271–276 d-heaps, 260–261 Dijkstra’s algorithm, 391–400 Fibonacci heaps, 548–549 heapsorts, 273–274 Huffman algorithm, 453–459 Kruskal’s algorithm, 417–419 leftist heaps, 261–268, 543 multiway merges, 338–339 pairing heaps, 258, 553–559, 563 priority queues, 245–283 skew heaps, 269–271 Demers, A., 529 Dense graphs, 404, 417, 491 Deo, N., 446 Depth-first searches, 419–420 biconnected graphs, 421–425 directed graphs, 429–430 Euler circuits, 425–429 for strong components, 431–432 undirected graphs, 420–421 Depth of trees, 122 Deques with heap order, 557 Dequeue operations, 113, 115, 245 Dereferencing pointers, 398 Descendants in trees, 122 Design rule in recursion, 11 Destructors, 30–31 for binary search trees, 139–140 for matrices, 46 Devroye, L., 242 dfs function, 420 Diamond dequeues, 288 Dictionaries, recursion in, 10 Dietzfelbinger, M., 243 Digraphs, 379 all-pairs shortest paths in, 491–494 depth-first searches, 429–430 representation of, 380–382 Dijkstra, E W., 48 dijkstra function, 398–399 Dijkstra’s algorithm, 391–400 for all-pairs shortest paths, 491–494 and Prim’s algorithm, 414–417 time bound improvements for, 541–542 Dimensions for k-d trees, 602 Diminishing increment sorts See Shellsort Ding, Y., 289, 613 Dinic, E A., 446 Directed acyclic graphs (DAGs), 379–380 Directed edges, 121 Directed graphs, 379–380 all-pairs shortest paths in, 491–494 depth-first searches, 429–430 representation of, 380–382 Directories in extendible hashing, 233–236 trees for, 123, 125 Disjoint sets, 351–374 dynamic equivalence problem in, 352–353 equivalence relations in, 351 for maze generation, 372–374 path compression for, 360–371 references for, 376–377 smart union algorithms for, 357–359 structure of, 353–357 worst case analysis for union-by-rank approach, 361–372 DisjSets class, 355–356, 359, 361, 419 Disk I/O operations in extendible hashing, 233–236 and running times, 57–70 in sorting, 291 Distances, closest points problem, 470–475 Divide and conquer strategy, 305, 467–482 closest points problem, 470–475 components, 427–428 integer multiplication, 478–480 matrix multiplication, 480–482 623 maximum subsequence sum, 60–66 in mergesorts, 304–309 quicksort See Quicksort running time of, 468–470 selection problem, 475–478 Dor, D 348, 529 Dosa, G., 529 Double hashing, 207–208 Double rotation operations, 149–158 doubleWithLeftChild function, 155, 157 Doubly linked lists, 80–81, 91–93, 100–101, 117, 128, 196 Doyle, J., 377 drand48 function, 499 Dreyfus, S E., 528 Driscoll, J R., 289 Du, H C., 243 Due, M W., 289 Dumey, A I., 243 dumpContents function, 282 Duplicate elements in quicksorts, 295 Dynamic equivalence problem, 352–353 Dynamic objects, 22 Dynamic programming, 482–494 all-pairs shortest path, 491–494 optimal binary search trees, 487–491 ordering matrix multiplications, 485–487 references for, 527 tables vs recursion, 483–485 E Eckel, B., 48 Edelsbrunner, H., 529 Edges in depth-first searches, 429–430 graph, 379–380 tree, 121 Edmonds, J., 446 Eight queens problem, 525 Eisenbath, B., 190 Electrical connectivity, 351 624 Index Employee class, 198–199, 239 empty function for containers, 81 for maps, 174 for priority queues, 282 for sets, 173 for vectors, 91–92 Empty lists, 78 Enbody, R J., 243 end function for iterators, 82, 85–86, 90 for lists, 94 for maps, 174 for sets, 173 #endif preprocessor, 16, 18, 45, 616 Enqueue operations, 113–115 Eppinger, J L., 190 Eppstein, D., 529 Equivalence in disjoint sets, 352–353 erase function for iterators, 83 for lists, 93, 95, 100–101 for maps, 174 Erase operations See Delete operations Eriksson, P., 290 Euclidean distance, 470 Euclid’s algorithm running time, 68–69 Euler circuits, 425–429 Euler’s constant, 5, 189, 321 eval function, 526–527 Even, S., 446 Event-node graphs, 402 Event simulation, 259–260 Explicit constructors, 15 Explicit instantiation, 616–618 Exponential growth rate, 52, 60 Exponents and exponentiation formulas for, running time for, 69–70 Expression trees, 128–131 Extendible hashing, 233–236 External sorting, 336–341 algorithm, 336, 337–338 model for, 336 need for, 336 references for, 348 replacement selection in, 340–341 F Factorials, recursion for, 59 Fagin, R., 243 Farach, M., 613 Fermat’s lesser theorem, 504 fib function, 483 fibonacci function, 483 Fibonacci heaps, 399–400 cutting nodes in leftist heaps, 542–544 for Dijkstra’s algorithm, 400 lazy merging for binomial queues, 544–548 operations, 548–549 for priority queues, 288 time bound proof for, 549–551 Fibonacci numbers in polyphase merges, 340 proofs for, recursion for, 59–60, 482–485 File compression, 453 File servers, 115 Find operations See also Searches biconnected graphs, 421–425 binary heaps, 249–257 binary search trees, 175–176 binomial queues, 271–281 disjoint sets, 351–374 hash tables, 205–206 lists, 78–79 maps, 174 shortest-path algorithms, 365–366 top-down splay trees, 563 findArt function, 425 findChain function, 406 findCompMove function, 513, 515–516 findHumanMove function, 513, 515 findKth operations, 79 findMax function, 22 for binary search trees, 132–133, 136–137 for function objects, 41–43 template for, 37–38 for top-down splay trees, 563 findMin function, 135–136, 193, 249 for binary heaps, 248–249 for binary search trees, 137 for binomial queues, 277 for leftist heaps, 265 for top-down splay trees, 563 findMinIndex function, 277, 280–281 findNewVertexOfIndegreeZero function, 383–384 findPos function, 204, 206, 220 First fit algorithm, 462–463 First fit decreasing algorithm, 464–465 Fischer, M J., 377, 531 Flajolet, P., 190, 243, 613 Flamig, B., 613 flip function, 521 Floyd, R W., 289, 348, 529 for loops in running time, 67, 515 Ford, L R., 348, 446 Forests for binomial queues, 271 in depth-first spanning, 422 for disjoint sets, 354 for Kruskal’s algorithm, 416 Forward edges, 429 Fotakis, D., 243 Fredman, M L., 243, 289, 377, 446, 529, 558, 612, 613 Friedman, J H., 613 friend declarations, 96 Frieze, A., 243 front function, 81, 93 Fulkerson, D R., 446 Full nodes, 183–184 Full trees, 455 Fuller, S H., 191 Function objects, 41–42 Function templates, 37–38 Functions and function calls member, 12 recursive, 8–9, 484 stacks for, 111–114 Fussenegger, F., 348 Index G Gabow, H N., 289, 348, 377, 446 Gajewska, H., 558 Galambos, G., 528 Galil, Z., 446, 528, 529 Galler, B A., 377 Games, 511 alpha-beta pruning, 513–517 hash tables for, 237 minimax algorithm, 511–514 Garbage collection, 22 Garey, M R., 446, 529 gcd (greatest common divisor) function, 51, 68 General-purpose sorting algorithms, 291, 309, 331 Geometric series, getChainFromPrevMap function, 406 getName function, 199 Giancarlo, R., 529 Global optimums, 449 Godbole, S., 529 Goldberg, A V., 446 Golin, M., 348 Gonnet, G H., 190, 243, 289, 348 Graham, R L., 48, 529 Grandchildren in trees, 122 Grandparents in trees, 122 Graph class, 398–399 Graphs, 379–437 bipartite, 439 breadth-first searches, 389 coloring, 436 definitions for, 379–382 depth-first searches See Depth-first searches k-colorable, 442 minimum spanning tree, 413–419 multigraphs, 442 network flow problems, 406–413 NP-completeness, 432–436 planar, 400 references for, 445–448 representation of, 380–382 shortest-path algorithms for acyclic graph, 400–404 all pairs, 404 Dijkstra’s algorithm, 391–400 example, 404–405 negative edge costs, 400 single source, 385–387 unweighted, 388–393 topological sorts for, 382–385 traveling salesman, 522 Greatest common divisor (GCD) function, 51, 68 Greedy algorithms, 449–467 approximate bin packing See Approximate bin packing for coin changing problem, 451 Dijkstra’s algorithm, 392 Huffman codes, 453–459 Kruskal’s algorithm, 416–418 maximum-flow algorithms, 409 minimum spanning tree, 413–419 processor scheduling, 450–453 Gries, D., 48 Growth rate of functions, 52–54 Gudes, E., 190 Guibas, L J., 191, 243, 613 Gupta, R., 529 Gusfield, D., 613 H h files, 16 Hagerup, T., 446 Haken, D., 528 Halting problems, 433 Hamiltonian cycle, 429, 434–436 Han, Y., 529 handleReorient function, 570 Harary, F., 446 Harmonic numbers, Harries, R., 243 hash class template, 197–199 hash function, 194–196 hash_map function, 233 hash_set function, 233 Hash tables, 193 Carter-Wegman trick, 233 cuckoo hashing, 215–217, 222–224, 226 double hashing in, 207–208 extendible hashing, 233–236 hash function, 194–196 625 hopscotch hashing, 227–230 linear probing in, 201–203 overview, 193–195 perfect hashing, 213–215 quadratic probing in, 202–206 references for, 242–243 rehashing for, 208–210 separate chaining for, 196–200 in Standard Library, 210–212 universal hashing, 230–233 Hasham, A., 289 HashEntry class, 204–205 HashTable class, 197, 205–206, 222, 241 header files, 16–17 Header information, compilation of, 616 Header nodes for lists, 92, 563 Heap order, deques with, 557 Heap-order property, 248–249 Heaps 2-d, 610 binary See Binary heaps leftist See Leftist heaps pairing, 602–606 priority See Priority queues skew, 269–271 Heapsort analysis, 303–305 comparing, 306 implementation, 300–303 references for, 347 heapsort function, 302–303 Heavy nodes in skew heaps, 540 Height of trees, 122 AVL, 154 binary tree traversals, 167 complete binary, 247 Hibbard, T H., 191, 348 Hibbard’s increments, 298–299 Hiding information, 12 Hirschberg, D S., 530 Hoare, C A R., 348, 475 Hoey, D., 531 Homometric point sets, 521, 528 Hopcroft, J E., 76, 190, 377, 445, 446, 447 Hopscotch hashing, 227–230 Horvath, E C., 348 Hu, T C., 529 626 Index Huang, B., 348 Huffman, D A., 529 Huffman codes, 453–459 Hulls, convex, 523 Hutchinson, J P., 48 Hypotheses in induction, 6–7 I if/else statements in running time, 59 Implementation/interface separation, 16–18 Implicit type conversions with constructors, 15 Impossible problems, 433 Incerpi, J., 348 #include preprocessor, 16 increaseKey function, 254 Increment sequences in Shellsorts, 296–300 Indegrees of vertices, 382–383 Inductive proofs process, 6–7 recursion in, 10–11 Infinite loop-checking programs, 433 Infix to postfix conversion, 108–110 Information hiding, 12 Information-theoretic lower bounds, 325 Inheritance for lists, 93 init function, 95, 98–99 Initialization list for constructors, 14 Inorder traversal, 129, 166 Input size in running time, 56–58 insert function and insert operations 2-d trees, 599–601 AVL trees, 144–158 double rotation, 149–158 single rotation, 158–160 B-trees, 168–173 binary heaps, 249–257 binary search trees, 132–135, 137–138 binary searches, 68 binomial queues, 273–275, 277, 534–539 d-heaps, 260–261 extendible hashing, 22 Fibonacci heaps, 547, 551 hash tables, 196–197, 199, 207 Huffman algorithm, 459 iterators, 83 leftist heaps, 262–263, 265 linked lists, 79–80 lists, 78, 92, 93, 100–101 maps, 174 multiway merges, 338 pairing heaps, 602, 605 priority queues, 245–246 red-black trees, 567–568, 574–575 sets, 173–174 skew heaps, 253, 541 skip lists, 502–503 splay trees, 161–163, 563, 565 treaps, 576–579 Insertion sorts, 292–295 algorithm, 292–293 analysis, 294–295 implementation, 293–294 insertionSort function, 293–294, 317, 322, 343 Instantiation, explicit, 616–618 IntCell class constructors for, 12–15 defaults for, 31–34 interface/implementation separation in, 15–17 pointers in, 21–23 Integers greatest common divisors of, 69–70 multiplying, 478–479 Interface/implementation separation, 16–18 Internal path lengths, 141 Inversion in arrays, 295–296 isActive function, 204 isEmpty function for binary heaps, 248 for binary search trees, 133 for binomial queues, 277 for leftist heaps, 265 for top-down splay trees, 563 isLessThan function, 41 Isomorphic trees, 188 isPrime function, 505 Iterated logarithm, 362 Iterators, 82 const_iterator, 84–86 for container operations, 83 erase, 84 getting, 82 for lists, 82–83 for maps, 174–175 methods for, 82–83 for sets, 173–174 stale, 118 Iyengar, S S., 613 J Janson, S., 349 Jiang, T., 349 Johnson, D B., 289, 447 Johnson, D S., 446, 529 Johnson, S M., 348 Jonassen, A T., 191 Jones, D W., 614 Josephus problem, 117 K k-colorable graphs, 442 k-d trees, 596–601 Kaas, R., 290 Kaehler, E B., 191 Kahn, A B., 447 Kane, D., 242 Karatsuba, A., 529 Karger, D R., 447, 529 Karlin, A R., 242 Karlton, P L., 191 Karp, R M., 243, 377, 446, 447 Kärkkäinen, J., 614 Karzanov, A V., 447 Kasai, T., 614 Kayal, N., 528 Kernighan, B W., 48, 447 Kevin Bacon Game, 444 Keys in hashing, 193–196 for maps, 174–178 Khoong, C M., 289, 558 King, V., 447 Index Kirsch, A., 243 Kishimoto, A., 531 Kitten puzzle, 534 Klein, P N., 447 Knapsack problem, 436 Knight’s tour, 525 Knuth, D E., 48, 49, 76, 191, 243, 289, 349, 377, 447, 530 Ko, P., 614 Komlos, J., 243 Korsh, J., 529 Kruskal, J B., Jr., 447 kruskal function, 418–419 Kruskal’s algorithm, 417–419 Kuhn, H W., 447 Kurtz, S., 613 L Labels for class members, 12 Ladner, R E., 289 Lajoie, J., 49 Lake, R., 531 LaMarca, A., 289 Landau, G M., 530 Landis, E M., 144, 190 Langston, M., 348 LaPoutre, J A., 377 Larmore, L L., 530 Last in, first out (LIFO) lists See Stacks Lawler, E L., 447 Lazy binomial queues, 545–546 Lazy deletion AVL trees, 156 binary search trees, 140 hash tables, 204 leftist heaps, 286 lists, 118–119 Lazy merging, 542 binomial queues, 544–548 Fibonacci heaps, 542 Leaves in trees, 122 Lee, C C., 531 Lee, D T., 531, 614 Lee, G., 614 Lee, K., 530 leftChild function, 277–278, 281, 302, 304, 604–606 Leftist heaps, 261–268, 543 cutting nodes in, 542–544 merging with, 266–267 path lengths in, 261–262 references for, 287 skew heaps, 266–270 LeftistHeap class, 265–266 LeftistNode structure, 265 Lehmer, D., 496 Lelewer, D A., 530 Lemke, P., 531 Lempel, A., 531 Length in binary search trees, 141 graph paths, 379 tree paths, 122 Lenstra, H W., Jr., 530 Leong, H W., 289, 558 Level-order traversal, 168 Lewis, T G., 243 L’Hôpital’s rule, 53 Li, M., 349 Liang, F M., 530 LIFO (last in, first out) lists See Stacks Light nodes in skew heaps, 540 Limits of function growth, 53 Lin, S., 447 Linear congruential generators, 496, 499–500 Linear-expected-time selection algorithm, 321–323 Linear growth rate, 53–54 Linear probing, 201–202, 209 Linear worst-case time in selection problem, 475 Linked lists, 79–80 circular, 119 priority queues, 246 skip lists, 499–501 stacks, 104 Lippman, S B., 49 List class, 91–94 listAll function, 124 Lists, 78 adjacency, 381 arrays for, 78–79 implementation of, 91–102 linked See Linked lists queues See Queues skip, 500–503 627 stacks See Stacks in STL, 80–81 vectors for See Vectors Load factor of hash tables, 203 Local optimums, 449 Log-squared growth rate, 53 Logarithmic growth rate, 53 Logarithmic running time, 66 for binary searches, 66–68 for Euclid’s algorithm, 70–71 for exponentiation, 69–70 Logarithms, formulas for, 3, 66–70, 362 Longest common prefix (LCP), 581–586, 594 Longest common subsequence problem, 529 Longest increasing subsequence problem, 524 Look-ahead factors in games, 514 Loops graph, 379 in running time, 56 Lower bounds, 323–328 of function growth, 52 maximum and minimum, 328–331 selection, 325–328 for sorting, 295–296 Lu, P., 531 Lueker, G., 243 lvalue, 23–24, 26–29, 31 lvalue reference, 23–24, 26, 28 M M-ary search trees, 169 Mahajan, S., 530 Main memory, sorting in, 291 Majority problem, 75 makeEmpty function for binary heaps, 248 for binary search trees, 133, 140–141 for binomial queues, 277 for hash tables, 196, 200, 206 for leftist heaps, 265 for lists, 78 for top-down splay trees, 563, 566 628 Index makeLCPArray, 609 Manacher, G K., 349 Manber, U., 614 map class, 121 Maps example, 176–181 for hash tables, 193–194 implementation, 175–176 operations, 174–175 Margalit, O., 528 Marsaglia, G., 530 Martin, W A., 614 Mathematics review, 2–8 for algorithm analysis, 51–54 exponents, logarithms, modular arithmetic, 5–6 proofs, 6–8 recursion, 7–11 series, 4–5 Matrices, 44 adjacency, 380–381 data members, constructors, and accessors for, 44 destructors, copy assignment, and copy constructors for, 46 multiplying, 379–382, 484–487 operator[] for, 44–46 matrix class, 44–45, 89 Matsumoto, M., 530 Maurer, W D., 243 max-heaps, 300–301 Maximum and minimum, 328–331, 345, 348, 557 Maximum-flow algorithms, 408–413 Maximum subsequence sum problem analyzing, 54–56 running time of, 60–68 MAXIT game, 526–527 Maze generation, 372–374 McCreight, E M., 190, 614 McDiarmid, C J H., 289 McElroy, M D., 348 McKenzie, B J., 243 Median-of-median-of-five partitioning, 476–477, 519 Median-of-three partitioning, 313, 316 median3 function, 316–317, 322 Medians samples of, 475 in selection problem, 258 Melhorn, K., 190, 191, 242, 445, 447 Melsted, P., 243 Member functions, 12 constant, 15 signatures for, 16 Memory address-of operator for, 23 in computational models, 54 sorting in, 291 for vectors, 87 Memory leaks, 22, 33, 36 MemoryCell class compilation of, 615–618 template for, 37–38 merge function and merge operations binomial queues, 277–280, 534–539 d-heaps, 260 Fibonacci heaps, 542, 550 leftist heaps, 261–267 mergesorts, 307 pairing heaps, 602–604 skew heaps, 539–541 mergeSort function, 306 analysis of, 306–309 external sorting, 337–340 implementation of, 303–305 multiway, 338–339 polyphase, 339–340 references for, 347 Mersenne Twister, 500 Methods, 12 Meyers, S., 49 Miller, G L., 530 Miller, K W., 530 Min-cost flow problems, 413, 445 min-heaps, 283 Min-max heaps, 285, 288 Minimax algorithm, 511–514 Minimum spanning trees, 412–413, 522 Kruskal’s algorithm, 416–417 Prim’s algorithm, 414–417 references for, 444 Mitzenmacher, M., 242, 243 Modular arithmetic, 5–6 Moffat, A., 558 Molodowitch, M., 243 Monier, L., 530 Moore, J S., 242 Moore, R W., 530 Moret, B M E., 447, 614 Morin, P., 242 Morris, J H., 243 Motwani, R., 530 move assignment operator, 30–31, 33, 35 move constructor, 30–32, 34–35, 87 Müller, M., 531 Mulmuley, K., 530 Multigraphs, 442 Multiplying integers, 478–479 matrices, 479–482, 484–487 Multiprocessors in scheduling problem, 451–452 Multiway merges, 338–339 Munro, J I., 190, 289, 529 Musser, D R., 49, 349 Mutator functions, 15 Myers, G., 614 myHash function, 198, 220 N Naor, M., 242 Negative-cost cycles, 386–387 Negative edge costs, 400 Ness, D N., 614 Nested loops in running time, 58 Network flow, 406–413 maximum-flow algorithm, 408–413 references for, 444 Networks, queues for, 115 new operator Index for pointers, 21–22 for vectors, 87 Newline characters, 454–455 Next fit algorithm, 461–462 Nievergelt, J., 191, 243, 614 Nishimura, T., 530 Node class for lists, 92–93, 96 Nodes binary search trees, 132–133 binomial trees, 534 decision trees, 323 expression trees, 128 leftist heaps, 262–264, 542–544 linked lists, 79–80 lists, 91–92 pairing heaps, 600 red-black trees, 567 skew heaps, 540–541 splay trees, 551, 560 treaps, 576 trees, 121–122 Nondeterministic algorithms, 408 Nondeterminism, 434 Nonpreemptive scheduling, 450 Nonprintable characters, 453 Nonterminating recursive functions, NP-completeness, 432 easy vs hard, 433–434 NP class, 434 references for, 445 traveling salesman problem,434-436 Null paths in leftist heaps, 261–262, 264 nullptr, 132 Null-terminator characters, 36 numcols function, 46 numrows function, 46 O Object type, 174 Objects, 12 declaring, 18 dynamic, 21–22 function, 41–43 passing, 23–24 Odlyzko, A., 190 Off-line algorithms approximate bin packing, 464–467 disjoint sets, 352 Ofman, Y., 529 Ohlebush, E., 613 On-line algorithms approximate bin packing, 460–461 definition, 65 disjoint sets, 352 One-dimensional circle packing problem, 522 One-parameter set operations, 173–174 oneCharOff function, 178–179 Operands in expression trees, 128 Operators in expression trees, 128–131 operator!= function hash tables, 199–200 lists, 96–97 operator() function, 41–43 operator* function lists, 96–98 matrices, 479–480 operator++ function, 96–98 operator< function in Comparable type, 39 in Square, 39–40 sets, 174 operator[...]... A.1 Everything in the Header 616 A.2 Explicit Instantiation 616 Index 619 586 615 P R E FAC E Purpose/Goals The fourth edition of Data Structures and Algorithm Analysis in C++ describes data structures, methods of organizing large amounts of data, and algorithm analysis, the estimation of the running time of algorithms As computers become faster and faster, the need for programs that can handle large... first line of the interface file 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 #ifndef IntCell_H #define IntCell_H /** * A class for simulating an integer memory cell */ class IntCell { public: explicit IntCell( int initialValue = 0 ); int read( ) const; void write( int x ); private: int storedValue; }; #endif Figure 1.7 IntCell class interface in file IntCell.h 3 Data members can be marked mutable to indicate... chapters Included is a discussion of the STL set and map classes, including a significant example that illustrates the use of three separate maps to efficiently solve a problem Chapter 5 discusses hash tables, including the classic algorithms such as separate chaining and linear and quadratic probing, as well as several newer algorithms, namely cuckoo hashing and hopscotch hashing Universal hashing is... class interface for IntCell, Figure 1.8 shows the implementation, and Figure 1.9 shows a main routine that uses the IntCell Some important points follow Preprocessor Commands The interface is typically placed in a file that ends with h Source code that requires knowledge of the interface must #include the interface file In our case, this is both the implementation file and the file that contains main Occasionally,... 22 23 24 #include "IntCell.h" /** * Construct the IntCell with initialValue */ IntCell::IntCell( int initialValue ) : storedValue{ initialValue } { } /** * Return the stored value */ int IntCell::read( ) const { return storedValue; } /** * Store x */ void IntCell::write( int x ) { storedValue = x; } Figure 1.8 IntCell class implementation in file IntCell.cpp 1 2 3 4 5 6 7 8 9 10 11 12 13 #include ... amortized analysis Three data structures from Chapters 4 and 6 and the Fibonacci heap, introduced in this chapter, are analyzed Chapter 12 covers search tree algorithms, the suffix tree and array, the k-d tree, and the pairing heap This chapter departs from the rest of the text by providing complete and careful implementations for the search trees and pairing heap The material is structured so that the instructor... constructs in C++ class design Chapter 2 deals with algorithm analysis This chapter explains asymptotic analysis and its major weaknesses Many examples are provided, including an in- depth explanation of logarithmic running time Simple recursive programs are analyzed by intuitively converting them into iterative programs More complicated divide -and- conquer programs are introduced, but some of the analysis. .. for simulating an integer memory cell */ class IntCell { public: /** * Construct the IntCell * Initial value is 0 */ IntCell( ) { storedValue = 0; } /** * Construct the IntCell * Initial value is initialValue */ IntCell( int initialValue ) { storedValue = initialValue; } /** * Return the stored value */ int read( ) { return storedValue; } /** * Change the stored value to x */ void write( int x ) { storedValue... complex initializations In some cases it is required For instance, if a data member is const (meaning that it is not changeable after the object has been constructed), then the data member’s value can only be initialized in the initialization list Also, if a data member is itself a class type that does not have a zero-parameter constructor, then it must be initialized in the initialization list Line 8 in. .. and suffix arrays, including the linear-time suffix array construction algorithm by Karkkainen and Sanders (with implementation) The sections covering deterministic skip lists and AA-trees have been removed r Throughout the text, the code has been updated to use C++11 Notably, this means use of the new C++11 features, including the auto keyword, the range for loop, move construction and assignment, and