elementary-algorithms.pdf

【核心代码】

Contents
I Preface 11
0.1 Why? . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 13
0.2 The smallest free ID problem, the power of algorithms . . . . . . 13
0.2.1 Improvement 1 . . . . . . . . . . . . . . . . . . . . . . . . 14
0.2.2 Improvement 2, Divide and Conquer . . . . . . . . . . . . 15
0.2.3 Expressiveness vs. Performance . . . . . . . . . . . . . . . 16
0.3 The number puzzle, power of data structure . . . . . . . . . . . . 18
0.3.1 The brute-force solution . . . . . . . . . . . . . . . . . . . 18
0.3.2 Improvement 1 . . . . . . . . . . . . . . . . . . . . . . . . 18
0.3.3 Improvement 2 . . . . . . . . . . . . . . . . . . . . . . . . 21
0.4 Notes and short summary . . . . . . . . . . . . . . . . . . . . . . 23
0.5 Structure of the contents . . . . . . . . . . . . . . . . . . . . . . . 24
II Trees 27
1 Binary search tree, the ‘hello world’ data structure 29
1.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 29
1.2 Data Layout . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 30
1.3 Insertion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 33
1.4 Traversing . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 34
1.5 Querying a binary search tree . . . . . . . . . . . . . . . . . . . . 37
1.5.1 Looking up . . . . . . . . . . . . . . . . . . . . . . . . . . 37
1.5.2 Minimum and maximum . . . . . . . . . . . . . . . . . . . 38
1.5.3 Successor and predecessor . . . . . . . . . . . . . . . . . . 38
1.6 Deletion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 40
1.7 Randomly build binary search tree . . . . . . . . . . . . . . . . . 44
2 The evolution of insertion sort 47
2.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 47
2.2 Insertion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 48
2.3 Improvement 1 . . . . . . . . . . . . . . . . . . . . . . . . . . . . 50
2.4 Improvement 2 . . . . . . . . . . . . . . . . . . . . . . . . . . . . 51
2.5 Final improvement by binary search tree . . . . . . . . . . . . . . 53
2.6 Short summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . 54
3
4 CONTENTS
3 Red-black tree, not so complex as it was thought 57
3.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 57
3.1.1 Exploit the binary search tree . . . . . . . . . . . . . . . . 57
3.1.2 How to ensure the balance of the tree . . . . . . . . . . . 58
3.1.3 Tree rotation . . . . . . . . . . . . . . . . . . . . . . . . . 60
3.2 Definition of red-black tree . . . . . . . . . . . . . . . . . . . . . 62
3.3 Insertion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 63
3.4 Deletion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 66
3.5 Imperative red-black tree algorithm ⋆ . . . . . . . . . . . . . . . 74
3.6 More words . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 77
4 AVL tree 81
4.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 81
4.1.1 How to measure the balance of a tree? . . . . . . . . . . . 81
4.2 Definition of AVL tree . . . . . . . . . . . . . . . . . . . . . . . . 81
4.3 Insertion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 84
4.3.1 Balancing adjustment . . . . . . . . . . . . . . . . . . . . 86
4.3.2 Pattern Matching . . . . . . . . . . . . . . . . . . . . . . . 90
4.4 Deletion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 92
4.5 Imperative AVL tree algorithm ⋆ . . . . . . . . . . . . . . . . . . 92
4.6 Chapter note . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 96
5 Radix tree, Trie and Patricia 99
5.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 99
5.2 Integer Trie . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 100
5.2.1 Definition of integer Trie . . . . . . . . . . . . . . . . . . . 101
5.2.2 Insertion . . . . . . . . . . . . . . . . . . . . . . . . . . . . 101
5.2.3 Look up . . . . . . . . . . . . . . . . . . . . . . . . . . . . 103
5.3 Integer Patricia . . . . . . . . . . . . . . . . . . . . . . . . . . . . 104
5.3.1 Definition . . . . . . . . . . . . . . . . . . . . . . . . . . . 105
5.3.2 Insertion . . . . . . . . . . . . . . . . . . . . . . . . . . . . 106
5.3.3 Look up . . . . . . . . . . . . . . . . . . . . . . . . . . . . 111
5.4 Alphabetic Trie . . . . . . . . . . . . . . . . . . . . . . . . . . . . 113
5.4.1 Definition . . . . . . . . . . . . . . . . . . . . . . . . . . . 113
5.4.2 Insertion . . . . . . . . . . . . . . . . . . . . . . . . . . . . 115
5.4.3 Look up . . . . . . . . . . . . . . . . . . . . . . . . . . . . 116
5.5 Alphabetic Patricia . . . . . . . . . . . . . . . . . . . . . . . . . . 117
5.5.1 Definition . . . . . . . . . . . . . . . . . . . . . . . . . . . 117
5.5.2 Insertion . . . . . . . . . . . . . . . . . . . . . . . . . . . . 118
5.5.3 Look up . . . . . . . . . . . . . . . . . . . . . . . . . . . . 123
5.6 Trie and Patricia applications . . . . . . . . . . . . . . . . . . . . 125
5.6.1 E-dictionary and word auto-completion . . . . . . . . . . 125
5.6.2 T9 input method . . . . . . . . . . . . . . . . . . . . . . . 129
5.7 Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 134
6 Suffix Tree 137
6.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 137
6.2 Suffix trie . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 138
6.2.1 Node transfer and suffix link . . . . . . . . . . . . . . . . 139
6.2.2 On-line construction . . . . . . . . . . . . . . . . . . . . . 140
CONTENTS 5
6.3 Suffix Tree . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 144
6.3.1 On-line construction . . . . . . . . . . . . . . . . . . . . . 144
6.4 Suffix tree applications . . . . . . . . . . . . . . . . . . . . . . . . 153
6.4.1 String/Pattern searching . . . . . . . . . . . . . . . . . . . 153
6.4.2 Find the longest repeated sub-string . . . . . . . . . . . . 155
6.4.3 Find the longest common sub-string . . . . . . . . . . . . 157
6.4.4 Find the longest palindrome . . . . . . . . . . . . . . . . . 159
6.4.5 Others . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 159
6.5 Notes and short summary . . . . . . . . . . . . . . . . . . . . . . 159
7 B-Trees 163
7.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 163
7.2 Insertion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 165
7.2.1 Splitting . . . . . . . . . . . . . . . . . . . . . . . . . . . . 165
7.3 Deletion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 172
7.3.1 Merge before delete method . . . . . . . . . . . . . . . . . 172
7.3.2 Delete and fix method . . . . . . . . . . . . . . . . . . . . 180
7.4 Searching . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 186
7.5 Notes and short summary . . . . . . . . . . . . . . . . . . . . . . 187
III Heaps 191
8 Binary Heaps 193
8.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 193
8.2 Implicit binary heap by array . . . . . . . . . . . . . . . . . . . . 193
8.2.1 Definition . . . . . . . . . . . . . . . . . . . . . . . . . . . 194
8.2.2 Heapify . . . . . . . . . . . . . . . . . . . . . . . . . . . . 195
8.2.3 Build a heap . . . . . . . . . . . . . . . . . . . . . . . . . 196
8.2.4 Basic heap operations . . . . . . . . . . . . . . . . . . . . 198
8.2.5 Heap sort . . . . . . . . . . . . . . . . . . . . . . . . . . . 205
8.3 Leftist heap and Skew heap, the explicit binary heaps . . . . . . 207
8.3.1 Definition . . . . . . . . . . . . . . . . . . . . . . . . . . . 208
8.3.2 Merge . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 209
8.3.3 Basic heap operations . . . . . . . . . . . . . . . . . . . . 210
8.3.4 Heap sort by Leftist Heap . . . . . . . . . . . . . . . . . . 211
8.3.5 Skew heaps . . . . . . . . . . . . . . . . . . . . . . . . . . 212
8.4 Splay heap . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 214
8.4.1 Definition . . . . . . . . . . . . . . . . . . . . . . . . . . . 214
8.4.2 Heap sort . . . . . . . . . . . . . . . . . . . . . . . . . . . 220
8.5 Notes and short summary . . . . . . . . . . . . . . . . . . . . . . 220
9 From grape to the world cup, the evolution of selection sort 225
9.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 225
9.2 Finding the minimum . . . . . . . . . . . . . . . . . . . . . . . . 227
9.2.1 Labeling . . . . . . . . . . . . . . . . . . . . . . . . . . . . 228
9.2.2 Grouping . . . . . . . . . . . . . . . . . . . . . . . . . . . 229
9.2.3 performance of the basic selection sorting . . . . . . . . . 230
9.3 Minor Improvement . . . . . . . . . . . . . . . . . . . . . . . . . 231
9.3.1 Parameterize the comparator . . . . . . . . . . . . . . . . 231
6 CONTENTS
9.3.2 Trivial fine tune . . . . . . . . . . . . . . . . . . . . . . . 232
9.3.3 Cock-tail sort . . . . . . . . . . . . . . . . . . . . . . . . . 233
9.4 Major improvement . . . . . . . . . . . . . . . . . . . . . . . . . 237
9.4.1 Tournament knock out . . . . . . . . . . . . . . . . . . . . 237
9.4.2 Final improvement by using heap sort . . . . . . . . . . . 245
9.5 Short summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . 246
10 Binomial heap, Fibonacci heap, and pairing heap 249
10.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 249
10.2 Binomial Heaps . . . . . . . . . . . . . . . . . . . . . . . . . . . . 249
10.2.1 Definition . . . . . . . . . . . . . . . . . . . . . . . . . . . 249
10.2.2 Basic heap operations . . . . . . . . . . . . . . . . . . . . 254
10.3 Fibonacci Heaps . . . . . . . . . . . . . . . . . . . . . . . . . . . 264
10.3.1 Definition . . . . . . . . . . . . . . . . . . . . . . . . . . . 264
10.3.2 Basic heap operations . . . . . . . . . . . . . . . . . . . . 266
10.3.3 Running time of pop . . . . . . . . . . . . . . . . . . . . . 275
10.3.4 Decreasing key . . . . . . . . . . . . . . . . . . . . . . . . 277
10.3.5 The name of Fibonacci Heap . . . . . . . . . . . . . . . . 279
10.4 Pairing Heaps . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 281
10.4.1 Definition . . . . . . . . . . . . . . . . . . . . . . . . . . . 282
10.4.2 Basic heap operations . . . . . . . . . . . . . . . . . . . . 282
10.5 Notes and short summary . . . . . . . . . . . . . . . . . . . . . . 288
IV Queues and Sequences 293
11 Queue, not so simple as it was thought 295
11.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 295
11.2 Queue by linked-list and circular buffer . . . . . . . . . . . . . . 296
11.2.1 Singly linked-list solution . . . . . . . . . . . . . . . . . . 296
11.2.2 Circular buffer solution . . . . . . . . . . . . . . . . . . . 299
11.3 Purely functional solution . . . . . . . . . . . . . . . . . . . . . . 302
11.3.1 Paired-list queue . . . . . . . . . . . . . . . . . . . . . . . 302
11.3.2 Paired-array queue - a symmetric implementation . . . . 305
11.4 A small improvement, Balanced Queue . . . . . . . . . . . . . . . 306
11.5 One more step improvement, Real-time Queue . . . . . . . . . . 308
11.6 Lazy real-time queue . . . . . . . . . . . . . . . . . . . . . . . . . 315
11.7 Notes and short summary . . . . . . . . . . . . . . . . . . . . . . 318
12 Sequences, The last brick 321
12.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 321
12.2 Binary random access list . . . . . . . . . . . . . . . . . . . . . . 322
12.2.1 Review of plain-array and list . . . . . . . . . . . . . . . . 322
12.2.2 Represent sequence by trees . . . . . . . . . . . . . . . . . 322
12.2.3 Insertion to the head of the sequence . . . . . . . . . . . . 324
12.3 Numeric representation for binary random access list . . . . . . . 329
12.3.1 Imperative binary random access list . . . . . . . . . . . . 332
12.4 Imperative paired-array list . . . . . . . . . . . . . . . . . . . . . 335
12.4.1 Definition . . . . . . . . . . . . . . . . . . . . . . . . . . . 335
12.4.2 Insertion and appending . . . . . . . . . . . . . . . . . . . 336
CONTENTS 7
12.4.3 random access . . . . . . . . . . . . . . . . . . . . . . . . 336
12.4.4 removing and balancing . . . . . . . . . . . . . . . . . . . 337
12.5 Concatenate-able list . . . . . . . . . . . . . . . . . . . . . . . . . 339
12.6 Finger tree . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 342
12.6.1 Definition . . . . . . . . . . . . . . . . . . . . . . . . . . . 343
12.6.2 Insert element to the head of sequence . . . . . . . . . . . 345
12.6.3 Remove element from the head of sequence . . . . . . . . 348
12.6.4 Handling the ill-formed finger tree when removing . . . . 349
12.6.5 append element to the tail of the sequence . . . . . . . . . 354
12.6.6 remove element from the tail of the sequence . . . . . . . 355
12.6.7 concatenate . . . . . . . . . . . . . . . . . . . . . . . . . . 356
12.6.8 Random access of finger tree . . . . . . . . . . . . . . . . 361
12.7 Notes and short summary . . . . . . . . . . . . . . . . . . . . . . 373
V Sorting and Searching 377
13 Divide and conquer, Quick sort vs. Merge sort 379
13.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 379
13.2 Quick sort . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 379
13.2.1 Basic version . . . . . . . . . . . . . . . . . . . . . . . . . 380
13.2.2 Strict weak ordering . . . . . . . . . . . . . . . . . . . . . 381
13.2.3 Partition . . . . . . . . . . . . . . . . . . . . . . . . . . . 382
13.2.4 Minor improvement in functional partition . . . . . . . . 385
13.3 Performance analysis for quick sort . . . . . . . . . . . . . . . . . 387
13.3.1 Average case analysis ⋆ . . . . . . . . . . . . . . . . . . . 388
13.4 Engineering Improvement . . . . . . . . . . . . . . . . . . . . . . 391
13.4.1 Engineering solution to duplicated elements . . . . . . . . 391
13.5 Engineering solution to the worst case . . . . . . . . . . . . . . . 398
13.6 Other engineering practice . . . . . . . . . . . . . . . . . . . . . . 402
13.7 Side words . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 403
13.8 Merge sort . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 403
13.8.1 Basic version . . . . . . . . . . . . . . . . . . . . . . . . . 404
13.9 In-place merge sort . . . . . . . . . . . . . . . . . . . . . . . . . . 411
13.9.1 Naive in-place merge . . . . . . . . . . . . . . . . . . . . . 411
13.9.2 in-place working area . . . . . . . . . . . . . . . . . . . . 412
13.9.3 In-place merge sort vs. linked-list merge sort . . . . . . . 417
13.10Nature merge sort . . . . . . . . . . . . . . . . . . . . . . . . . . 419
13.11Bottom-up merge sort . . . . . . . . . . . . . . . . . . . . . . . . 425
13.12Parallelism . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 427
13.13Short summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . 427
14 Searching 431
14.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 431
14.2 Sequence search . . . . . . . . . . . . . . . . . . . . . . . . . . . . 431
14.2.1 Divide and conquer search . . . . . . . . . . . . . . . . . . 432
14.2.2 Information reuse . . . . . . . . . . . . . . . . . . . . . . . 452
14.3 Solution searching . . . . . . . . . . . . . . . . . . . . . . . . . . 479
14.3.1 DFS and BFS . . . . . . . . . . . . . . . . . . . . . . . . . 480
14.3.2 Search the optimal solution . . . . . . . . . . . . . . . . . 516
8 CONTENTS
14.4 Short summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . 545
VI Appendix 549
Appendices
A Lists 551
A.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 551
A.2 List Definition . . . . . . . . . . . . . . . . . . . . . . . . . . . . 551
A.2.1 Empty list . . . . . . . . . . . . . . . . . . . . . . . . . . . 552
A.2.2 Access the element and the sub list . . . . . . . . . . . . . 552
A.3 Basic list manipulation . . . . . . . . . . . . . . . . . . . . . . . . 553
A.3.1 Construction . . . . . . . . . . . . . . . . . . . . . . . . . 553
A.3.2 Empty testing and length calculating . . . . . . . . . . . . 554
A.3.3 indexing . . . . . . . . . . . . . . . . . . . . . . . . . . . . 555
A.3.4 Access the last element . . . . . . . . . . . . . . . . . . . 556
A.3.5 Reverse indexing . . . . . . . . . . . . . . . . . . . . . . . 557
A.3.6 Mutating . . . . . . . . . . . . . . . . . . . . . . . . . . . 559
A.3.7 sum and product . . . . . . . . . . . . . . . . . . . . . . . 569
A.3.8 maximum and minimum . . . . . . . . . . . . . . . . . . . 573
A.4 Transformation . . . . . . . . . . . . . . . . . . . . . . . . . . . . 576
A.4.1 mapping and for-each . . . . . . . . . . . . . . . . . . . . 577
A.4.2 reverse . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 583
A.5 Extract sub-lists . . . . . . . . . . . . . . . . . . . . . . . . . . . 585
A.5.1 take, drop, and split-at . . . . . . . . . . . . . . . . . . . 585
A.5.2 breaking and grouping . . . . . . . . . . . . . . . . . . . . 587
A.6 Folding . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 592
A.6.1 folding from right . . . . . . . . . . . . . . . . . . . . . . . 592
A.6.2 folding from left . . . . . . . . . . . . . . . . . . . . . . . 594
A.6.3 folding in practice . . . . . . . . . . . . . . . . . . . . . . 597
A.7 Searching and matching . . . . . . . . . . . . . . . . . . . . . . . 598
A.7.1 Existence testing . . . . . . . . . . . . . . . . . . . . . . . 598
A.7.2 Looking up . . . . . . . . . . . . . . . . . . . . . . . . . . 599
A.7.3 finding and filtering . . . . . . . . . . . . . . . . . . . . . 599
A.7.4 Matching . . . . . . . . . . . . . . . . . . . . . . . . . . . 602
A.8 zipping and unzipping . . . . . . . . . . . . . . . . . . . . . . . . 604
A.9 Notes and short summary . . . . . . . . . . . . . . . . . . . . . . 607
GNU Free Documentation License 611
1. APPLICABILITY AND DEFINITIONS . . . . . . . . . . . . . . . 611
2. VERBATIM COPYING . . . . . . . . . . . . . . . . . . . . . . . . 613
3. COPYING IN QUANTITY . . . . . . . . . . . . . . . . . . . . . . 613
4. MODIFICATIONS . . . . . . . . . . . . . . . . . . . . . . . . . . . 614
5. COMBINING DOCUMENTS . . . . . . . . . . . . . . . . . . . . . 615
6. COLLECTIONS OF DOCUMENTS . . . . . . . . . . . . . . . . . 616
7. AGGREGATION WITH INDEPENDENT WORKS . . . . . . . . 616
8. TRANSLATION . . . . . . . . . . . . . . . . . . . . . . . . . . . . 616
9. TERMINATION . . . . . . . . . . . . . . . . . . . . . . . . . . . . 617
10. FUTURE REVISIONS OF THIS LICENSE . . . . . . . . . . . . 617
CONTENTS 9
11. RELICENSING . . . . . . . . . . . . . . . . . . . . . . . . . . . . 617
ADDENDUM: How to use this License for your documents . . . . . . 618