Data Structures Outside-In with Java

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