.Exercises 29
References 33
3 Lists, Stacks, and Queues 35
3.1. Abstract Data Types (ADTs) 35
3.2. The List AnT 36
3.2.1. Simple Array Implementation of Lists 37
3.2.2. Linked Lists 37
3.2.3. Programming Details 38
3.2.4. Common Errors 43
3.2.5. Doubly Linked Lists 45
3.2.6. Circularly Linked Lists 46
3.2.7. Examples 46
3.2.8. Cursor Implementation of Linked Lists 50
3.3. The Stack ADT 56
3.3.1. Stack Model 56
3.3.2. Implementation of Stacks 57
3.3.3. Applications 65
3.4. The Queue AnT 73
3.4.1. Queue Model 73
3.4.2. Array Implementation of Queues 73
3.4.3. Applications of Queues 78
Summary 79
Exercises 79
4 Trees 83
4.1. Preliminaries 83
4.1.1. Terminology 83
4.1.2. Tree Traversals with an Application 84
4.2. Binary Trees 85
4.2.1. Implementation 86
4.2.2. Expression Trees 87
4.2.3. Tree Traversals 90
4.3. The Search Tree ADT Binary Search Trees 97
4.3.1. MakeEmpty 97
4.3.2. Find 97
4.3.3. FindMin and FindMax 99
4.3.4. Insert 100
4.3.5. Delete 101
4.3.6. Average-Case Analysis 103
4.4. AVL Trees 106
4.4.1. Single Rotation 108
4.4.2. Double Rotation 111
4.5. Splay Trees 119
4.5.1. A Simple Idea (That Does Not Work) 12 0
4.5.2. Splaying 12 2
4.6. B-Trees 128
Summary 133
Exercises 134
References 141
5 Priority Queues (Heaps) 145
5.1. Model 145
5.2. Simple Implementations 146
5.3. Binary Heap 147
5.3.1. Structure Property 147
5.3.2. Heap Order Property 148
5.3.3. Basic Heap Operations 150
5.3.4. Other Heap Operations 154
5.4. Applications of Priority Queues 157
5.4.1. The Selection Problem 157
5.4.2. Event Simulation 159
5.5. d-Heaps 160
5.6. Leftist Heaps 161
5.6.1. Leftist Heap Property 161
5.6.2. Leftist Heap Operations 162
5.7. Skew Heaps 168
5.8. Binomial Queues 170
5.8.1. Binomial Queue Structure 170
5.8.2. Binomial Queue Operations 172
5.8.3. Implementation of Binomial Queues 173
Summary 180
Exercises 180
References 184
6 Sorting 187
6.1. Preliminaries 187
6.2. Insertion Sort 188
6.2.1. The Algorithm 188
6.2.2. Analysis of Insertion Sort 189
6.3. A Lower Bound for Simple Sorting Algorithms 189
6.4. Shellsort 190
6.4.1. Worst-Case Analysis of Shellsort 192
6.5. Heapsort 194
6.5.1. Analysis of Heapsort 196
6.6. Mergesort 198
6.6.1. Analysis of Mergesort 200
6.7. Quicksort 203
6.7.1. Picking the Pivot 204
6.7.2. Partitioning Strategy 205
6.7.3. Small Arrays 20 8
6.7.4. Actual Quicksort Routines 208
6.7.5. Analysis of Quicksort 209
6.7.6. A Linear-Expected-Time Algorithm for Selection 213
6.8. Sorting Large Structures 215
6.9. A General Lower Bound for Sorting 216
6.9.1. Decision Trees 217
6.10. Bucket Sort and Radix Sort 219
6.11. External Sorting 222
6.11.1. Why We Need New Algorithms 222
6.11.2. Model for External Sorting 222
6.11.3. The Simple Algorithm 222
6.11.4. Multiway Merge 224
6.11.5. Polyphase Merge 225
6.11.6. Replacement Selection 226
Summary 227
Exercises 229
7 Hashing 235
7.1. General Idea 235
7.2. Hash Function 237
7.3. Separate Chaining 239
7.4. Open Addressing 244
7.4.1. Linear Probing 244
7.4.2. Quadratic Probing 247
7.4.3. Double Hashing 251
7.5. Rehashing 252
7.6. Extendible Hashing 255
Summary 258
Exercises 259
References 262
8 The Disjoint Set AnT 265
8.1. Equivalence Relations 265
8.2. The Dynamic Equivalence Problem 266
8.3. Basic Data Structure 267
8.4. Smart Union Algorithms 271
8.5. Path Compression 273
8.6. Worst Case for Union-by-Rank and Path Compression 275
8.6.1. Analysis of the Union/Find Algorithm 275
8.7. An Application 281
Summary 281
Exercises 282
References 283
9 Graph Algorithms 285
9.1. Definitions 285
9.1.1. Representation of Graphs 286
9.2. Topological Sort 288
9.3. Shortest-Path Algorithms 292
9.3.1. Unweighted Shortest Paths 293
9.3.2. Dijkstra's Algorithm 297
9.3.3. Graphs with Negative Edge Costs 306
9.3.4. Acyclic Graphs 307
9.3.5. All-Pairs Shortest Path 310
9.4. Network Flow Problems 310
9.4.1. A Simple Maximum-Flow Algorithm 311
9.5. Minimum Spanning Tree 315
9.5.1. Prim's Algorithm 316
9.5.2. Kruskal's Algorithm 318
9.6. Applications of Depth-First Search 3:21
9.6.1. Undirected Graphs 322
9.6.2. Biconnectivity 324
9.6.3. Euler Circuits 328
9.6.4. Directed Graphs 331
9.6.5. Finding Strong Components 333
9.7. Introduction to NP-Completeness 334
9.7.2. The Class NP 336
9.7.3. NP-Complete Problems 337
Summary 339
Exercises 339
References 345
10 Algorithm Design Techniques 349
10.1. Greedy Algorithms 349
10.1.1. A Simple Scheduling Problem 350
10.1.2. Huffman Codes 353
10.1.3. Approximate Bin Packing 359
10.2. Divide and Conquer 367
10.2.1. Running Time of Divide and Conquer Algorithms 368
10.2.2. Closest-Points Problem 370
10.2.3. The Selection Problem 375
10.2.4. Theoretical Improvements for Arithmetic Problems 378
10.3. Dynamic Programming 382
10.3.1. Using a Table Instead of Recursion 382
10.3.2. Ordering Matrix Multiplications 385
10.3.3. Optimal Binary Search Tree 389
10.3.4. All-Pairs Shortest Path 392
10.4. Randomized Algorithms 394
10.4.1. Random Number Generators 396
10.4.2. Skip Lists 399
10.4.3. Primality Testing 401
10.5. Backtracking Algorithms 403
10.5.1. The Turnpike Reconstruction Problem 405
10.5.2. Games 407
Summary 415
Exercises 417
References 424
11 Amortized Analysis 429
11.1. An Unrelated Puzzle 430
11.2. Binomial Queues 430
11.3. Skew Heaps 435
11.4. Fibonacci Heaps 437
11.4.1. Cutting Nodes in Leftist Heaps 430
11.4.2. Lazy Merging for Binomial Queues 441
11.4.3. The Fibonacci Heap Operations 444
11.4.4. Proof of the Time Bound 445
11.5. Splay Trees 447
Summary 451
Exercises 452
References 453
12 Advanced Data Structures and Implementation 455
12.1. Top-Down Splay Trees 455
12.2. Red Black Trees 459
12.2.1. Bottom-Up Insertion 464
12.2.2. Top-Down Red Black Trees 465
12.2.3. Top-Down Deletion 467
12.3. Deterministic Skip Lists 471
12.4. &A-Trees 478
12.5. Treaps 484
12.6. k-d Trees 487
12.7. Pairing Heaps 490
Summary 496
Exercises 497
References 499