This innovative new book encourages readers to utilize the “Outside-In” approach to learning the use, design and implementation of data structures. The author introduces every data structure by first narrating its properties and use in applications (the "outside" view).  This provides a clear introduction to data structures with realistic context where it is used. Venugopal then details how to build data structures (the "inside" view); readers learn how to evaluate usability, flexibility, extensibility, and performance in designing and implementing classic data structures.

Table of Contents:
Preface xv 1 Object-Oriented Programming in Java 1 1.1 Objects and Encapsulation . . . . . . . . . . . . . . . . . . . . . . . . . . 2 1.1.1 Objects . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2 1.1.2 Lifetime, State and Messages . . . . . . . . . . . . . . . . . . . . 2 1.1.3 Clients of an Object . . . . . . . . . . . . . . . . . . . . . . . . . 3 1.1.4 Separation of Interface from Implementation . . . . . . . . . . . . 3 1.2 Classes . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3 1.2.1 State and Behavior . . . . . . . . . . . . . . . . . . . . . . . . . . 6 1.2.2 Method Overloading . . . . . . . . . . . . . . . . . . . . . . . . . 6 1.2.3 Object Creation, Constructors, Garbage Collection . . . . . . . . . 7 1.2.4 Method Invocation . . . . . . . . . . . . . . . . . . . . . . . . . . 11 1.2.5 Static Fields and Methods . . . . . . . . . . . . . . . . . . . . . . 12 1.2.6 Object References . . . . . . . . . . . . . . . . . . . . . . . . . . 16 1.3 Inheritance . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 16 1.3.1 Superclass and Subclass . . . . . . . . . . . . . . . . . . . . . . . 17 1.3.2 Inherited and Specialized Fields . . . . . . . . . . . . . . . . . . . 19 1.3.3 Constructors . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 20 ii CONTENTS 1.3.4 Object Creation . . . . . . . . . . . . . . . . . . . . . . . . . . . . 21 1.3.5 Inherited and Specialized Methods . . . . . . . . . . . . . . . . . . 22 1.3.6 Method Overriding . . . . . . . . . . . . . . . . . . . . . . . . . . 22 1.4 The Object Class . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 23 1.4.1 The equals Method . . . . . . . . . . . . . . . . . . . . . . . . . . 24 1.4.2 The toString Method . . . . . . . . . . . . . . . . . . . . . . . . . 26 1.4.3 The clone Method . . . . . . . . . . . . . . . . . . . . . . . . . . 27 1.5 Exceptions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 28 1.5.1 Interpreting an exception message . . . . . . . . . . . . . . . . . . 29 1.5.2 Homegrown error handling . . . . . . . . . . . . . . . . . . . . . . 31 1.5.3 Throwing an exception . . . . . . . . . . . . . . . . . . . . . . . . 37 1.5.4 Catching an exception . . . . . . . . . . . . . . . . . . . . . . . . 39 1.5.5 Exception class . . . . . . . . . . . . . . . . . . . . . . . . . . . . 45 1.6 Input and Output . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 46 1.6.1 Terminal-driven IO . . . . . . . . . . . . . . . . . . . . . . . . . . 47 1.6.2 File-based IO . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 49 1.6.3 String tokenizing . . . . . . . . . . . . . . . . . . . . . . . . . . . 53 1.6.4 Writing an exception class . . . . . . . . . . . . . . . . . . . . . . 55 1.7 Class Packages . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 55 1.7.1 Java packages . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 56 1.7.2 Organizing packages . . . . . . . . . . . . . . . . . . . . . . . . . 58 1.7.3 Name conflict resolution . . . . . . . . . . . . . . . . . . . . . . . 62 1.8 Access control . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 63 1.8.1 Private Access . . . . . . . . . . . . . . . . . . . . . . . . . . . . 64 1.8.2 Package Access . . . . . . . . . . . . . . . . . . . . . . . . . . . . 64 1.8.3 Protected Access . . . . . . . . . . . . . . . . . . . . . . . . . . . 64 CONTENTS iii 1.8.4 Public Access . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 65 1.8.5 An Example . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 65 1.9 Polymorphism . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 66 1.9.1 Polymorphic Reference . . . . . . . . . . . . . . . . . . . . . . . . 67 1.9.2 Casting Up the Class Hierarchy . . . . . . . . . . . . . . . . . . . 68 1.9.3 Casting Down the Class Hierarchy . . . . . . . . . . . . . . . . . . 69 1.9.4 The instanceof Operator . . . . . . . . . . . . . . . . . . . . . . . 70 1.10 Abstract Classes . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 72 1.10.1 Abstract Class Shape . . . . . . . . . . . . . . . . . . . . . . . . . 72 1.10.2 Abstract Class Properties . . . . . . . . . . . . . . . . . . . . . . . 73 1.11 A Game Park Example . . . . . . . . . . . . . . . . . . . . . . . . . . . . 74 1.12 Interfaces . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 77 1.12.1 The Java interface Construct . . . . . . . . . . . . . . . . . . . . . 78 1.12.2 Implementing an interface . . . . . . . . . . . . . . . . . . . . . . 78 1.12.3 Interface as a Type . . . . . . . . . . . . . . . . . . . . . . . . . . 79 1.12.4 The Need for Interfaces . . . . . . . . . . . . . . . . . . . . . . . 79 1.12.5 Extending Interfaces . . . . . . . . . . . . . . . . . . . . . . . . . 81 1.13 Generics . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 82 1.13.1 Using java.util.ArrayList for Collections . . . . . . . . . . . . . . . 83 1.13.2 The java.util.ArrayList Public Interface . . . . . . . . . . . . . . . 85 1.13.3 Implementing a Generic Class . . . . . . . . . . . . . . . . . . . . 86 1.13.4 Implementing a Generic Interface . . . . . . . . . . . . . . . . . . 87 1.13.5 Static Template Methods . . . . . . . . . . . . . . . . . . . . . . . 91 1.14 Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 94 1.15 Exercises . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 96 1.16 Programming Problems . . . . . . . . . . . . . . . . . . . . . . . . . . . . 98 iv CONTENTS 2 The Big Picture 103 2.1 What Are Data Structures? . . . . . . . . . . . . . . . . . . . . . . . . . . 104 2.2 What Data Structures Do We Study? . . . . . . . . . . . . . . . . . . . . . 104 2.3 What are Abstract Data Types? . . . . . . . . . . . . . . . . . . . . . . . . 108 2.4 Why OOP and Java for Data Structures? . . . . . . . . . . . . . . . . . . . 110 2.5 How Do I Choose the Right Data Structures? . . . . . . . . . . . . . . . . 112 3 Efficiency of Algorithms 115 3.1 Polynomial Arithmetic: A Running Example . . . . . . . . . . . . . . . . 116 3.2 Basic Operations . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 118 3.3 Input Size . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 120 3.4 Asymptotic Growth of Functions . . . . . . . . . . . . . . . . . . . . . . . 121 3.5 Order and Big Oh . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 123 3.5.1 Typical Running Time Orders . . . . . . . . . . . . . . . . . . . . 125 3.5.2 Multi-variable Order . . . . . . . . . . . . . . . . . . . . . . . . . 129 3.5.3 Relative Order . . . . . . . . . . . . . . . . . . . . . . . . . . . . 130 3.5.4 Order Arithmetic . . . . . . . . . . . . . . . . . . . . . . . . . . . 130 3.6 Worst-case and Average . . . . . . . . . . . . . . . . . . . . . . . . . . . . 131 3.7 Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 134 3.8 Exercises . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 135 4 Unordered List 141 4.1 Unordered List Properties . . . . . . . . . . . . . . . . . . . . . . . . . . . 142 4.2 Sequential Search . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 143 4.2.1 Average Case Analysis . . . . . . . . . . . . . . . . . . . . . . . . 144 4.2.2 Rearranging Data Based on Search Patterns . . . . . . . . . . . . . 146 4.3 A List Class . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 147 CONTENTS v 4.4 An ExpenseList Class Using List . . . . . . . . . . . . . . . . . . . . . . . 150 4.4.1 Expense Class Interface . . . . . . . . . . . . . . . . . . . . . . . 150 4.4.2 Expense Class . . . . . . . . . . . . . . . . . . . . . . . . . . . . 152 4.4.3 ExpenseList Class Interface . . . . . . . . . . . . . . . . . . . . . 153 4.4.4 ExpenseList Class Implementation . . . . . . . . . . . . . . . . . . 155 4.4.5 Equality of Objects and Searching . . . . . . . . . . . . . . . . . . 157 4.5 Linked List . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 161 4.5.1 Node . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 163 4.5.2 Insertion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 163 4.5.3 Deletion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 165 4.5.4 Access . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 166 4.5.5 Circular Linked List . . . . . . . . . . . . . . . . . . . . . . . . . 167 4.6 A LinkedList class . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 170 4.7 List Class Implementation . . . . . . . . . . . . . . . . . . . . . . . . . . 177 4.8 Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 178 4.9 Exercises . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 179 4.10 Programming Problems . . . . . . . . . . . . . . . . . . . . . . . . . . . . 182 5 Ordered List 187 5.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 188 5.2 Binary Search . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 189 5.2.1 Divide In Half . . . . . . . . . . . . . . . . . . . . . . . . . . . . 189 5.2.2 Algorithm . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 190 5.3 Ordering: Interface java.lang.Comparable . . . . . . . . . . . . . . 193 5.4 An OrderedList Class . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 195 5.5 Merging Ordered Lists . . . . . . . . . . . . . . . . . . . . . . . . . . . . 199 5.5.1 Two-finger Merge Algorithm . . . . . . . . . . . . . . . . . . . . . 201 vi CONTENTS 5.6 List Consolidation Using OrderedList . . . . . . . . . . . . . . . . . . . . 205 5.6.1 Merger: A Utility Class . . . . . . . . . . . . . . . . . . . . . . . 205 5.6.2 A Consolidation Class . . . . . . . . . . . . . . . . . . . . . . . . 208 5.7 OrderedList Class Implementation . . . . . . . . . . . . . . . . . . . . . . 209 5.8 Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 213 5.9 Exercises . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 214 5.10 Programming Problems . . . . . . . . . . . . . . . . . . . . . . . . . . . . 219 6 Queue 223 6.1 Queue Properties . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 224 6.2 UNIX Print Queue . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 225 6.3 A Queue Class . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 226 6.4 A PrintQueue Class Using Queue . . . . . . . . . . . . . . . . . . . . . . . 228 6.5 Queue Class Implementation . . . . . . . . . . . . . . . . . . . . . . . . . 234 6.5.1 Design 1: Using Array-based Storage . . . . . . . . . . . . . . . . 234 6.5.2 Design 2: Using Linked List . . . . . . . . . . . . . . . . . . . . . 237 6.6 Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 239 6.7 Exercises . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 240 6.8 Programming Problems . . . . . . . . . . . . . . . . . . . . . . . . . . . . 242 7 Stack 245 7.1 Stack Properties . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 246 7.2 Stack Applications . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 247 7.2.1 Parentheses Matching . . . . . . . . . . . . . . . . . . . . . . . . 247 7.2.2 Postfix Expression Evaluation . . . . . . . . . . . . . . . . . . . . 248 7.2.3 Infix to Postfix Conversion . . . . . . . . . . . . . . . . . . . . . . 251 7.3 A Stack Class . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 252 CONTENTS vii 7.4 A Postfix Expression Evaluation Package . . . . . . . . . . . . . . . . . . 252 7.4.1 Class PostfixEvaluator . . . . . . . . . . . . . . . . . . . . . . . . 254 7.4.2 Class StatusKeeper . . . . . . . . . . . . . . . . . . . . . . . . . . 256 7.4.3 Class StackKeeper . . . . . . . . . . . . . . . . . . . . . . . . . . 257 7.4.4 Class PostfixEvaluator Implementation . . . . . . . . . . . . . . . 260 7.5 Stack Class Implementation . . . . . . . . . . . . . . . . . . . . . . . . . 262 7.5.1 Design 1: Array List for Storage . . . . . . . . . . . . . . . . . . . 262 7.5.2 Design 2: Linked List for Storage . . . . . . . . . . . . . . . . . . 263 7.6 Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 264 7.7 Exercises . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 265 7.8 Programming Problems . . . . . . . . . . . . . . . . . . . . . . . . . . . . 268 8 Recursion 271 8.1 Recursive Definitions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 272 8.1.1 List . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 272 8.1.2 Ordered List . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 274 8.1.3 Factorial Function . . . . . . . . . . . . . . . . . . . . . . . . . . 275 8.1.4 Fibonacci Sequence . . . . . . . . . . . . . . . . . . . . . . . . . 275 8.2 Recursive Programs and Backing Out . . . . . . . . . . . . . . . . . . . . 276 8.2.1 Computing the Factorial . . . . . . . . . . . . . . . . . . . . . . . 277 8.2.2 Computing the Fibonacci Sequence . . . . . . . . . . . . . . . . . 279 8.2.3 Recursion with Linked Lists . . . . . . . . . . . . . . . . . . . . . 280 8.3 Recursion On An Array: Binary Search . . . . . . . . . . . . . . . . . . . 282 8.4 Towers of Hanoi: An Application . . . . . . . . . . . . . . . . . . . . . . 283 8.4.1 A Recursive Definition . . . . . . . . . . . . . . . . . . . . . . . . 284 8.4.2 A Recursive Program . . . . . . . . . . . . . . . . . . . . . . . . . 286 8.5 Recursion and Stacks . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 287 viii CONTENTS 8.6 Drawbacks of Recursion . . . . . . . . . . . . . . . . . . . . . . . . . . . 288 8.7 Tail Recursion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 289 8.8 Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 291 8.9 Exercises . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 292 8.10 Programming Problems . . . . . . . . . . . . . . . . . . . . . . . . . . . . 294 9 Binary Tree and General Tree 299 9.1 Binary Tree Properties . . . . . . . . . . . . . . . . . . . . . . . . . . . . 300 9.1.1 Components . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 300 9.1.2 Position as Meaning . . . . . . . . . . . . . . . . . . . . . . . . . 301 9.1.3 Structure . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 303 9.1.4 Recursive Definitions . . . . . . . . . . . . . . . . . . . . . . . . . 304 9.2 Binary Tree Traversals . . . . . . . . . . . . . . . . . . . . . . . . . . . . 306 9.3 A BinaryTree Class . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 308 9.4 Storing and Recreating a Binary Tree . . . . . . . . . . . . . . . . . . . . . 312 9.4.1 Signature of a Binary Tree . . . . . . . . . . . . . . . . . . . . . . 313 9.4.2 Building a Binary Tree From Its Signature . . . . . . . . . . . . . . 314 9.5 Huffman Coding . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 318 9.5.1 Statistical and Dictionary Coding . . . . . . . . . . . . . . . . . . 318 9.5.2 Algorithm . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 318 9.5.3 Average Code Length and Prefix Property . . . . . . . . . . . . . . 320 9.5.4 A Huffman Class Using BinaryTree . . . . . . . . . . . . . . . . . 321 9.6 BinaryTree Class Implementation . . . . . . . . . . . . . . . . . . . . . . 329 9.7 Stack-based Traversals . . . . . . . . . . . . . . . . . . . . . . . . . . . . 332 9.7.1 Inorder Traversal of Binary Tree . . . . . . . . . . . . . . . . . . . 333 9.7.2 A Visitor Class . . . . . . . . . . . . . . . . . . . . . . . . . . . . 334 9.8 General Tree . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 335 CONTENTS ix 9.8.1 Example: Hierarchy in a University . . . . . . . . . . . . . . . . . 335 9.8.2 Example: UNIX Filesystem . . . . . . . . . . . . . . . . . . . . . 336 9.8.3 Space Issues in Implementation . . . . . . . . . . . . . . . . . . . 337 9.8.4 Correspondence with Binary Tree . . . . . . . . . . . . . . . . . . 338 9.8.5 Signature of General Tree . . . . . . . . . . . . . . . . . . . . . . 340 9.9 Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 341 9.10 Exercises . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 343 9.11 Programming Problems . . . . . . . . . . . . . . . . . . . . . . . . . . . . 346 10 Binary Search Tree and AVL Tree 351 10.1 Comparison Tree . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 352 10.1.1 Search Time Using Comparison Tree . . . . . . . . . . . . . . . . 353 10.1.2 Height of Comparison Tree . . . . . . . . . . . . . . . . . . . . . . 355 10.2 Binary Search Tree Properties . . . . . . . . . . . . . . . . . . . . . . . . 356 10.3 Binary Search Tree Operations . . . . . . . . . . . . . . . . . . . . . . . . 358 10.3.1 Search . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 358 10.3.2 Insert . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 359 10.3.3 Delete . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 359 10.4 A BinarySearchTree Class . . . . . . . . . . . . . . . . . . . . . . . . . . 362 10.5 Using Class BinarySearchTree . . . . . . . . . . . . . . . . . . . . . . . . 364 10.5.1 Example: Treesort . . . . . . . . . . . . . . . . . . . . . . . . . . 365 10.5.2 Example: Counting Keys . . . . . . . . . . . . . . . . . . . . . . . 366 10.6 BinarySearchTree Class Implementation . . . . . . . . . . . . . . . . . . . 367 10.6.1 Search Implementation . . . . . . . . . . . . . . . . . . . . . . . . 368 10.6.2 Insert Implementation . . . . . . . . . . . . . . . . . . . . . . . . 369 10.6.3 Delete Implementation . . . . . . . . . . . . . . . . . . . . . . . . 370 10.6.4 Convenience Methods and Traversals . . . . . . . . . . . . . . . . 373 x CONTENTS 10.7 AVL Tree . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 374 10.7.1 AVL Tree Structure . . . . . . . . . . . . . . . . . . . . . . . . . . 374 10.7.2 Search, Insert, Delete Overview . . . . . . . . . . . . . . . . . . . 376 10.7.3 Rotation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 376 10.7.4 Insertion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 377 10.7.5 Deletion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 380 10.7.6 Running Times of AVL Tree Operations . . . . . . . . . . . . . . . 385 10.7.7 AVL Insert and Delete: Generalization . . . . . . . . . . . . . . . . 385 10.8 Binary Search: Average Number of Comparisons . . . . . . . . . . . . . . 389 10.9 Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 392 10.10Exercises . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 393 10.11Programming Problems . . . . . . . . . . . . . . . . . . . . . . . . . . . . 397 11 Heap 401 11.1 Heap as Priority Queue . . . . . . . . . . . . . . . . . . . . . . . . . . . . 402 11.2 Heap Properties . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 403 11.2.1 Max and Min Heaps . . . . . . . . . . . . . . . . . . . . . . . . . 403 11.3 Heap Operations . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 404 11.3.1 Insert . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 404 11.3.2 Delete . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 405 11.4 A Heap Class . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 407 11.5 Priority Scheduling with Heap . . . . . . . . . . . . . . . . . . . . . . . . 408 11.5.1 Overview . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 408 11.5.2 A Scheduling Package using Heap . . . . . . . . . . . . . . . . . . 410 11.6 Sorting with the Heap Class . . . . . . . . . . . . . . . . . . . . . . . . . 417 11.6.1 Example: Sorting Integers . . . . . . . . . . . . . . . . . . . . . . 418 11.7 Heap Class Implementation . . . . . . . . . . . . . . . . . . . . . . . . . . 419 CONTENTS xi 11.7.1 Array Storage . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 419 11.7.2 Implementation using ArrayList . . . . . . . . . . . . . . . . . . . 422 11.8 Updatable Heap . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 425 11.8.1 Designing an Updatable Heap . . . . . . . . . . . . . . . . . . . . 425 11.8.2 Handles to heap entries . . . . . . . . . . . . . . . . . . . . . . . . 425 11.8.3 Shared handle array . . . . . . . . . . . . . . . . . . . . . . . . . . 426 11.8.4 Encapsulating handles within heap . . . . . . . . . . . . . . . . . . 427 11.8.5 Recycling free handle space . . . . . . . . . . . . . . . . . . . . . 427 11.9 Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 428 11.10Exercises . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 428 11.11Programming Problems . . . . . . . . . . . . . . . . . . . . . . . . . . . . 431 12 Hash Table 433 12.1 Motivation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 434 12.2 Hashing . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 435 12.3 Collision Resolution . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 436 12.3.1 Linear Probing . . . . . . . . . . . . . . . . . . . . . . . . . . . . 437 12.3.2 Quadratic Probing . . . . . . . . . . . . . . . . . . . . . . . . . . 439 12.3.3 Chaining . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 440 12.3.4 Comparison of Runnning Times . . . . . . . . . . . . . . . . . . . 441 12.4 The java.util.HashMap Class . . . . . . . . . . . . . . . . . . . . . . . . . 442 12.4.1 Table and Load Factor . . . . . . . . . . . . . . . . . . . . . . . . 443 12.4.2 Storage of Entries . . . . . . . . . . . . . . . . . . . . . . . . . . . 444 12.4.3 Adding an Entry . . . . . . . . . . . . . . . . . . . . . . . . . . . 445 12.4.4 Rehashing . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 448 12.4.5 Searching . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 449 12.5 Quadratic Probing: Repetition of Probe Locations . . . . . . . . . . . . . . 450 xii CONTENTS 12.6 Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 450 12.7 Exercises . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 451 12.8 Programming Problems . . . . . . . . . . . . . . . . . . . . . . . . . . . . 453 13 Sorting 455 13.1 Insertion Sort . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 456 13.2 Sorting by Divide and Conquer . . . . . . . . . . . . . . . . . . . . . . . . 459 13.2.1 Quicksort . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 460 13.2.2 Mergesort . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 466 13.3 Heapsort . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 468 13.3.1 Building a Heap in Linear Time . . . . . . . . . . . . . . . . . . . 469 13.3.2 Sorting a Heap . . . . . . . . . . . . . . . . . . . . . . . . . . . . 470 13.4 Radix Sort . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 471 13.5 Implementation: A Quicksort Class . . . . . . . . . . . . . . . . . . . . . 474 13.6 Heap Build: Linear Running Time . . . . . . . . . . . . . . . . . . . . . . 477 13.7 Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 478 13.8 Exercises . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 479 13.9 Programming Problems . . . . . . . . . . . . . . . . . . . . . . . . . . . . 483 14 Graphs I: Algorithms 485 14.1 Modeling Relationships using Graphs . . . . . . . . . . . . . . . . . . . . 486 14.1.1 Undirected Graphs . . . . . . . . . . . . . . . . . . . . . . . . . . 486 14.1.2 Directed Graphs . . . . . . . . . . . . . . . . . . . . . . . . . . . 488 14.1.3 Weighted Graphs . . . . . . . . . . . . . . . . . . . . . . . . . . . 490 14.2 Graph Representation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 491 14.3 Graph Traversals . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 493 14.3.1 Depth-first Search for Undirected Graphs . . . . . . . . . . . . . . 494 CONTENTS xiii 14.3.2 Breadth-first Search for Undirected Graphs . . . . . . . . . . . . . 495 14.3.3 Traversal Driver . . . . . . . . . . . . . . . . . . . . . . . . . . . 497 14.3.4 Traversals for Directed Graphs . . . . . . . . . . . . . . . . . . . . 498 14.4 Topological Sort on a Directed Graph . . . . . . . . . . . . . . . . . . . . 499 14.4.1 Partial and Total Order . . . . . . . . . . . . . . . . . . . . . . . . 500 14.4.2 Topological Numbering . . . . . . . . . . . . . . . . . . . . . . . 501 14.4.3 Topological Sorting Using Depth-first Search . . . . . . . . . . . . 502 14.4.4 Topological Sorting Using Breadth-first Search . . . . . . . . . . . 503 14.5 Connected Components of an Undirected Graph . . . . . . . . . . . . . . . 504 14.6 Shortest Paths in a Weighted Directed Graph . . . . . . . . . . . . . . . . . 505 14.6.1 Dijkstra’s Single-Source Algorithm . . . . . . . . . . . . . . . . . 506 14.7 Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 513 14.8 Exercises . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 514 15 Graphs II: Implementation 519 15.1 A Directed Graph Class: DirGraph . . . . . . . . . . . . . . . . . . . . . . 520 15.1.1 Vertex numbering . . . . . . . . . . . . . . . . . . . . . . . . . . . 520 15.1.2 Neighbor class . . . . . . . . . . . . . . . . . . . . . . . . . . . . 522 15.1.3 Exercising the DirGraph Class . . . . . . . . . . . . . . . . . . . . 524 15.2 An Undirected Graph Class: UndirGraph . . . . . . . . . . . . . . . . . . 525 15.3 A Depth-first Search Class: DFS . . . . . . . . . . . . . . . . . . . . . . . 527 15.3.1 Design and Interface . . . . . . . . . . . . . . . . . . . . . . . . . 528 15.3.2 Visitor Class . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 528 15.3.3 DFS Implementation . . . . . . . . . . . . . . . . . . . . . . . . . 531 15.4 A Topological Sort Class: DFSTopsort . . . . . . . . . . . . . . . . . . . . 532 15.4.1 TopVisitor: Extending the Visitor Class . . . . . . . . . . . . . . . 532 15.4.2 DFSTopsort Implementation . . . . . . . . . . . . . . . . . . . . . 534 xiv CONTENTS 15.5 A Connected Components Class: DFSConncomp . . . . . . . . . . . . . . 534 15.5.1 ConnVisitor: Extending the Visitor Class . . . . . . . . . . . . . . 535 15.5.2 DFSConncomp Implementation . . . . . . . . . . . . . . . . . . . 536 15.6 A Shortest Paths Class: ShortestPaths . . . . . . . . . . . . . . . . . . . . 536 15.6.1 WeightedNeighbor: Extending the Neighbor Class . . . . . . . . . 538 15.6.2 ShortestPaths Implementation . . . . . . . . . . . . . . . . . . . . 538 15.7 Graph Implementation . . . . . . . . . . . . . . . . . . . . . . . . . . . . 543 15.7.1 DirGraph Implementation . . . . . . . . . . . . . . . . . . . . . . 543 15.7.2 UndirGraph Class Implementation . . . . . . . . . . . . . . . . . . 548 15.7.3 Implementation of Weighted Graphs . . . . . . . . . . . . . . . . . 549 15.8 Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 549 15.9 Programming Problems . . . . . . . . . . . . . . . . . . . . . . . . . . . . 550