Chapter 1 Introduction 1
1.1 What’s the Book About? 1
1.2 Mathematics Review 2
1.2.1 Exponents 3
1.2.2 Logarithms 3
1.2.3 Series 4
1.2.4 Modular Arithmetic 5
1.2.5 The P Word 6
1.3 A Brief Introduction to Recursion 7
1.4 C++ Classes 11
1.4.1 Basic class Syntax 12
1.4.2 Extra Constructor Syntax and Accessors 12
1.4.3 Separation of Interface and Implementation 15
1.4.4 vector and string 17
1.5 C++ Details 19
1.5.1 Pointers 19
1.5.2 Parameter Passing 21
1.5.3 Return Passing 22
1.5.4 Reference Variables 23
1.5.5 The Big Three: Destructor, Copy Constructor, operator= 23
1.5.6 C-style Arrays and Strings 26
1.6 Templates 29
1.6.1 Function Templates 29
1.6.2 Class Templates 30
1.6.3 Object, Comparable, and an Example 32
1.6.4 Function Objects 34
1.6.5 Separate Compilation of Class Templates 35
1.7 Using Matrices 37
1.7.1 The Data Members, Constructor, and Basic Accessors 37
1.7.2 operator[] 37
1.7.3 Destructor, Copy Assignment, Copy Constructor 39
Summary 39
Exercises 39
References 41
Chapter 2 Algorithm Analysis 43
2.1 Mathematical Background 43
2.2 Model 46
2.3 What to Analyze 46
2.4 Running Time Calculations 49
2.4.1 A Simple Example 49
2.4.2 General Rules 50
2.4.3 Solutions for the Maximum Subsequence Sum Problem 52
2.4.4 Logarithms in the Running Time 58
2.4.5 Checking Your Analysis 62
2.4.6 A Grain of Salt 63
Summary 63
Exercises 64
References 69
Chapter 3 Lists, Stacks, and Queues 71
3.1 Abstract Data Types （ADTs） 71
3.2 The List ADT 72
3.2.1 Simple Array Implementation of Lists 72
3.2.2 Simple Linked Lists 73
3.3 vector and list in the STL 74
3.3.1 Iterators 75
3.3.2 Example: Using erase on a List 77
3.3.3 const iterators 77
3.4 Implementation of vector 79
3.5 Implementation of list 83
3.6 The Stack ADT 94
3.6.1 Stack Model 94
3.6.2 Implementation of Stacks 95
3.6.3 Applications 96
3.7 The Queue ADT 104
3.7.1 Queue Model 104
3.7.2 Array Implementation of Queues 104
3.7.3 Applications of Queues 106
Summary 107
Exercises 108
Chapter 4 Trees 113
4.1 Preliminaries 113
4.1.1 Implementation of Trees 114
4.1.2 Tree Traversals with an Application 115
4.2 Binary Trees 119
4.2.1 Implementation 120
4.2.2 An Example: Expression Trees 121
4.3 The Search Tree ADT—Binary Search Trees 124
4.3.1 contains 125
4.3.2 findMin and findMax 125
4.3.3 insert 129
4.3.4 remove 130
4.3.5 Destructor and Copy Assignment Operator 132
4.3.6 Average-Case Analysis 133
4.4 AVL Trees 136
4.4.1 Single Rotation 139
4.4.2 Double Rotation 142
4.5 Splay Trees 149
4.5.1 A Simple Idea （That Does Not Work） 150
4.5.2 Splaying 152
4.6 Tree Traversals （Revisited） 158
4.7 B-Trees 159
4.8 Sets and Maps in the Standard Library 165
4.8.1 Sets 165
4.8.2 Maps 166
4.8.3 Implementation of set and map 167
4.8.4 An Example That Uses Several Maps 168
Summary 174
Exercises 174
References 181
Chapter 5 Hashing 185
5.1 General Idea 185
5.2 Hash Function 186
5.3 Separate Chaining 188
5.4 Hash Tables Without Linked Lists 192
5.4.1 Linear Probing 193
5.4.2 Quadratic Probing 195
5.4.3 Double Hashing 199
5.5 Rehashing 200
5.6 Hash Tables in the Standard Library 204
5.7 Extendible Hashing 204
Summary 207
Exercises 208
References 211
Chapter 6 Priority Queues （Heaps） 213
6.1 Model 213
6.2 Simple Implementations 214
6.3 Binary Heap 215
6.3.1 Structure Property 215
6.3.2 Heap-Order Property 216
6.3.3 Basic Heap Operations 217
6.3.4 Other Heap Operations 220
6.4 Applications of Priority Queues 225
6.4.1 The Selection Problem 226
6.4.2 Event Simulation 227
6.5 d-Heaps 228
6.6 Leftist Heaps 229
6.6.1 Leftist Heap Property 229
6.6.2 Leftist Heap Operations 230
6.7 Skew Heaps 235
6.8 Binomial Queues 239
6.8.1 Binomial Queue Structure 240
6.8.2 Binomial Queue Operations 241
6.8.3 Implementation of Binomial Queues 244
6.9 Priority Queues in the Standard Library 251
Summary 251
Exercises 251
References 257
Chapter 7 Sorting 261
7.1 Preliminaries 261
7.2 Insertion Sort 262
7.2.1 The Algorithm 262
7.2.2 STL Implementation of Insertion Sort 263
7.2.3 Analysis of Insertion Sort 264
7.3 A Lower Bound for Simple Sorting Algorithms 265
7.4 Shellsort 266
7.4.1 Worst-Case Analysis of Shellsort 268
7.5 Heapsort 270
7.5.1 Analysis of Heapsort 272
7.6 Mergesort 274
7.6.1 Analysis of Mergesort 276
7.7 Quicksort 279
7.7.1 Picking the Pivot 280
7.7.2 Partitioning Strategy 282
7.7.3 Small Arrays 284
7.7.4 Actual Quicksort Routines 284
7.7.5 Analysis of Quicksort 287
7.7.6 A Linear-Expected-Time Algorithm for Selection 290
7.8 Indirect Sorting 292
7.8.1 vector＜Comparabl e＞ Does Not Work 295
7.8.2 Smart Pointer Class 295
7.8.3 Overloading operator＜ 295
7.8.4 Dereferencing a Pointer with 295
7.8.5 Overloading the Type Conversion Operator 295
7.8.6 Implicit Type Conversions Are Everywhere 296
7.8.7 Dual-Direction Implicit Conversions Can Cause Ambiguities 296
7.8.8 Pointer Subtraction Is Legal 297
7.9 A General Lower Bound for Sorting 297
7.9.1 Decision Trees 297
7.10 Bucket Sort 299
7.11 External Sorting 300
7.11.1 Why We Need New Algorithms 300
7.11.2 Model for External Sorting 300
7.11.3 The Simple Algorithm 301
7.11.4 Multiway Merge 302
7.11.5 Polyphase Merge 303
7.11.6 Replacement Selection 304
Summary 305
Exercises 306
References 311
Chapter 8 The Disjoint Set Class 315
8.1 Equivalence Relations 315
8.2 The Dynamic Equivalence Problem 316
8.3 Basic Data Structure 317
8.4 Smart Union Algorithms 321
8.5 Path Compression 324
8.6 Worst Case for Union-by-Rank and Path Compression 325
8.6.1 Analysis of the Union/Find Algorithm 326
8.7 An Application 331
Summary 334
Exercises 335
References 336
Chapter 9 Graph Algorithms 339
9.1 Definitions 339
9.1.1 Representation of Graphs 340
9.2 Topological Sort 342
9.3 Shortest-Path Algorithms 345
9.3.1 Unweighted Shortest Paths 347
9.3.2 Dijkstra’s Algorithm 351
9.3.3 Graphs with Negative Edge Costs 360
9.3.4 Acyclic Graphs 360
9.3.5 All-Pairs Shortest Path 364
9.3.6 Shortest Path Example 365
9.4 Network Flow Problems 367
9.4.1 A Simple Maximum-Flow Algorithm 367
9.5 Minimum Spanning Tree 372
9.5.1 Prim’s Algorithm 373
9.5.2 Kruskal’s Algorithm 376
9.6 Applications of Depth-First Search 378
9.6.1 Undirected Graphs 379
9.6.2 Biconnectivity 381
9.6.3 Euler Circuits 385
9.6.4 Directed Graphs 388
9.6.5 Finding Strong Components 390
9.7 Introduction to NP-Completeness 392
9.7.1 Easy vs.Hard 392
9.7.2 The Class NP 393
9.7.3 NP-Complete Problems 394
Summary 396
Exercises 396
References 404
Chapter 10 Algorithm Design Techniques 409
10.1 Greedy Algorithms 409
10.1.1 A Simple Scheduling Problem 410
10.1.2 Huffman Codes 413
10.1.3 Approximate Bin Packing 419
10.2 Divide and Conquer 427
10.2.1 Running Time of Divide and Conquer Algorithms 428
10.2.2 Closest-Points Problem 430
10.2.3 The Selection Problem 435
10.2.4 Theoretical Improvements for Arithmetic Problems 438
10.3 Dynamic Programming 442
10.3.1 Using a Table Instead of Recursion 442
10.3.2 Ordering Matrix Multiplications 444
10.3.3 Optimal Binary Search Tree 447
10.3.4 All-Pairs Shortest Path 451
10.4 Randomized Algorithms 454
10.4.1 Random Number Generators 455
10.4.2 Skip Lists 459
10.4.3 Primality Testing 461
10.5 Backtracking Algorithms 464
10.5.1 The Turnpike Reconstruction Problem 465
10.5.2 Games 469
Summary 475
Exercises 475
References 485
Chapter 11 Amortized Analysis 491
11.1 An Unrelated Puzzle 492
11.2 Binomial Queues 492
11.3 Skew Heaps 497
11.4 Fibonacci Heaps 499
11.4.1 Cutting Nodes in Leftist Heaps 500
11.4.2 Lazy Merging for Binomial Queues 502
11.4.3 The Fibonacci Heap Operations 506
11.4.4 Proof of the Time Bound 506
11.5 Splay Trees 509
Summary 513
Exercises 513
References 515
Chapter 12 Advanced Data Structures and Implementation 517
12.1 Top-Down Splay Trees 517
12.2 Red-Black Trees 525
12.2.1 Bottom-Up Insertion 526
12.2.2 Top-Down Red-Black Trees 527
12.2.3 Top-Down Deletion 531
12.3 Deterministic Skip Lists 535
12.4 AA-Trees 540
12.5 Treaps 547
12.6 k-d Trees 549
12.7 Pairing Heaps 553
Summary 558
Exercises 558
References 563
Appendix A Separate Compilation of Class Templates 567
A.1 Everything in the Header 568
A.2 Explicit Instantiation 568
A.3 The export Directive 570
Index 571