Data Structures and Algorithms in JavaScript Optimizing Performance and Solving Programming Challenges (Federico Kereki)（Z-Library）

Page 1

® D A T A S T R U C T U R E S A N D A L G O R I T H M S I N J A V A S C R I P T O P T I M I Z I N G P E R F O R M A N C E A N D S O L V I N G P R O G R A M M I N G C H A L L E N G E S F E D E R I C O K E R E K I THE F INEST IN GEEK ENTERTA INMENT ™ nostarch.com ® ® D A T A S T R U C T U R E S A N D A L G O R I T H M S I N JA V A S C R IP T K E R E K I N O T T H E S A M E O L D J A V A S C R I P T $59.99 ($78.99 CDN) Think you know JavaScript? Think again. This isn’t your typical coding book—it’s a deep dive into the powerful world of data structures and algorithms that will transform the way you approach problem solving in JavaScript. Whether you’re a frontend developer tackling complex applications, a backend engineer building scalable systems, or a programmer preparing for technical interviews, this book will revolutionize the way you code. Key features include: • Modern JavaScript techniques: Use the latest language features and functional programming principles for cleaner, more effi cient code. • Performance-focused approach: Analyze and optimize algorithms using Big O notation. • Essential algorithms explained: Implement and fi ne-tune core algorithms like quicksort, merge sort, digital search, and binary search. • Algorithm design strategies: Solve challenging problems with techniques like recursion, dynamic programming, backtracking, and brute-force search. • Advanced data structures: Explore complex structures such as binary search trees, heaps, and graphs. Each chapter is carefully crafted with clear, no-nonsense explanations of complex concepts, real-world coding examples, and challenging questions (with answers at the end) to reinforce your understanding. Ready to break free from ordinary JavaScript? Whether your aim is to build cutting-edge web applications, optimize critical systems, or land your dream job, this book equips you with the advanced JavaScript knowledge that sets true experts apart. A B O U T T H E A U T H O R Federico Kereki is a systems engineer with over three decades of experience as a consultant, developer, and educator. Currently a subject matter expert at Globant, he holds a master’s degree in education and has authored several books, including Mastering JavaScript Functional Programming. His work has appeared in Linux Journal, Linux Magazine, IBM DeveloperWorks, and other leading tech publications.

Page 2

(This page has no text content)

Page 3

PRAISE FOR DATA STRUCTURES AND ALGORITHMS IN JAVASCRIPT “An incredibly useful resource for those of us who did not have a formal computer science background or simply never had the time to properly learn formal aspects of programming in general. It’s a tough book that will make you work, but worth every bit of effort.” — raymond camden, senior developer evangelist for adobe “Finally a book about algorithms and data structures that uses JavaScript! Read this if you want to learn important foundational techniques for writing and analyzing code—how to sort data, how to structure data for efficient lookup, and more. While similar to academic textbooks in its comprehensiveness, it’s much easier to understand.” — axel rauschmayer, javascript specialist, author of the 2ality blog and numerous javascript books

Page 4

(This page has no text content)

Page 5

DATA STRUCTURES AND ALGORITHMS IN JAVASCRIPT

Page 6

(This page has no text content)

Page 7

® D ATA S T R U C T U R E S A N D A L G O R I T H M S I N   J A V A S C R I P T O p t i m i z i n g Pe r f o r m a n c e a n d S o l v i n g P r o g r a m m i n g C h a l l e n g e s by Federico Kereki San Francisco

Page 8

[E] DATA STRUCTURES AND ALGORITHMS IN JAVASCRIPT. Copyright © 2025 by Federico Kereki. All rights reserved. No part of this work may be reproduced or transmitted in any form or by any means, electronic or mechanical, including photocopying, recording, or by any information storage or retrieval system, without the prior written permission of the copyright owner and the publisher. First printing ISBN-13: 978-1-7185-0262-8 (print) ISBN-13: 978-1-7185-0263-5 (ebook) Published by No Starch Press®, Inc. 245 8th Street, San Francisco, CA 94103 phone: +1.415.863.9900 www.nostarch.com; info@nostarch.com Publisher: William Pollock Managing Editor: Jill Franklin Production Manager: Sabrina Plomitallo-González Production Editor: Rachel Monaghan Developmental Editor: Jill Franklin Cover Illustrator: Gina Redman Interior Design: Octopod Studios Technical Reviewer: Daniel Zingaro Copyeditor: Lisa McCoy Proofreader: Scout Festa A catalog record of this book is available from the Library of Congress. For customer service inquiries, please contact info@nostarch.com. For information on distribution, bulk sales, corporate sales, or translations: sales@nostarch.com. For permission to translate this work: rights@nostarch.com. To report counterfeit copies or piracy: counterfeit@nostarch.com. No Starch Press and the No Starch Press iron logo are registered trademarks of No Starch Press, Inc. Other product and company names mentioned herein may be the trademarks of their respective owners. Rather than use a trademark symbol with every occurrence of a trademarked name, we are using the names only in an editorial fashion and to the benefit of the trademark owner, with no intention of infringement of the trademark. The information in this book is distributed on an “As Is” basis, without warranty. While every precaution has been taken in the preparation of this work, neither the author nor No Starch Press, Inc. shall have any liability to any person or entity with respect to any loss or damage caused or alleged to be caused directly or indirectly by the information contained in it. ®

Page 9

To Sylvia Tosar, my wife and constant companion and rock throughout this endeavor. Your unwavering support and love fueled every step of this journey, and I’m endlessly grateful for your presence and companionship. And to my father, Eugenio Kereki, who is no longer here to witness this new book, but whose influence echoes through these pages. I dedicate this book to his memory, knowing his spirit resides in the love and guidance he shared.

Page 10

(This page has no text content)

Page 11

About the Author Federico Kereki is a Uruguayan systems engineer with a master’s degree in education and over 30 years of experience as a consultant, system developer, and writer. Kereki is a subject matter expert at Globant, where he gets to use a variety of development frameworks, programming tools, and operating systems. He has taught several computer science courses at Universidad de la República; Universidad ORT, Uruguay; and Universidad de la Empresa. He specializes in efficiency and optimization, with a particu- lar focus on algorithm and data structure design and usage. He’s also the author of several books: Mastering JavaScript Functional Programming, 3rd edi- tion (Packt, 2023), Modern JavaScript Web Development Cookbook (Packt, 2018), and Essential GWT (Pearson, 2010), as well as multiple articles for Linux Journal, Linux Magazine, IBM DeveloperWorks, the OpenReplay and Globant blogs, and others. About the Technical Reviewer Dr. Daniel Zingaro is an award-winning associate professor of mathematical and computational sciences at the University of Toronto, Mississauga. He is well known for his uniquely interactive approach to teaching and interna- tionally recognized for his expertise in active learning. He is also the author of Learn to Code by Solving Problems and Algorithmic Thinking (both from No Starch Press).

Page 12

(This page has no text content)

Page 13

B R I E F C O N T E N T S Preface . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . xxi Acknowledgments . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . xxiii Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .xxv PART I: THE BASICS . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .1 Chapter 1: Using JavaScript . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3 Chapter 2: Functional Programming in JavaScript . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 23 Chapter 3: Abstract Data Types . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 37 Chapter 4: Analyzing Algorithms . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 49 PART II: ALGORITHMS . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .61 Chapter 5: Designing Algorithms . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 63 Chapter 6: Sorting . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 91 Chapter 7: Selecting . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 121 Chapter 8: Shuffling and Sampling . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 137 Chapter 9: Searching . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 159 PART III: DATA STRUCTURES . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .175 Chapter 10: Lists . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 177 Chapter 11: Bags, Sets, and Maps . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 203 Chapter 12: Binary Trees . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 235 Chapter 13: Trees and Forests . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 283 Chapter 14: Heaps . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 317 Chapter 15: Extended Heaps . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 345

Page 14

xii   Brief Contents Chapter 16: Digital Search Trees . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 387 Chapter 17: Graphs . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 425 Chapter 18: Immutability and Functional Data Structures . . . . . . . . . . . . . . . . . . . . . . . . . 469 Answer Key . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 487 Bibliography . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 545 Index . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 549

Page 15

C O N T E N T S I N D E T A I L PREFACE xxi ACKNOWLEDGMENTS xxiii INTRODUCTION xxv Who Should Read This Book? . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .xxvi What’s the Book’s Approach? . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .xxvi What’s in the Book? . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .xxvi PART I: THE BASICS 1 1 USING JAVASCRIPT 3 Modern JavaScript Features . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4 Arrow Functions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4 Classes . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5 The Spread Operator . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 6 The Destructuring Statement . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 7 Modules . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 8 Closures and Immediately Invoked Function Expressions . . . . . . . . . . . . . . . . 11 JavaScript Development Tools . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 13 Visual Studio Code . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 13 Fira Code Font . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 15 Prettier Formatting . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 16 JSDoc Documentation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 16 ESLint . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 18 Flow and TypeScript . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 18 Online Feature Availability Resources . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 19 Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 21 2 FUNCTIONAL PROGRAMMING IN JAVASCRIPT 23 Why Use Functional Programming? . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 24 JavaScript as a Functional Language . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 25 Functions as First-Class Objects . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 25 Declarative-Style Programming . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 26 Higher-Order Functions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 30 Side Effects . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 32 Impure Functions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 33 Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 35 Questions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 35

Page 16

xiv   Contents in Detail 3 ABSTRACT DATA TYPES 37 The Theory . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 38 Data Types . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 38 Abstraction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 39 Operations and Mutations . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 39 Implementing an ADT . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 40 Implementing ADTs Using Classes . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 41 Implementing ADTs Using Functions (Mutable Version) . . . . . . . . . . . . . . . . . . 43 Implementing ADTs Using Functions (Immutable Version) . . . . . . . . . . . . . . . . 45 Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 46 Questions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 46 4 ANALYZING ALGORITHMS 49 Performance . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 50 Complexity . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 50 Notations for Complexity . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 51 Complexity Classes . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 52 Performance Measurements . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 54 Analysis of Algorithms in Practice . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 55 Time and Space Complexity Trade-offs . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 57 Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 58 Questions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 58 PART II: ALGORITHMS 61 5 DESIGNING ALGORITHMS 63 Recursion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 64 The Divide-and-Conquer Strategy . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 65 The Backtracking Technique . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 69 Dynamic Programming . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 72 Calculating Fibonacci Series with Top-Down DP . . . . . . . . . . . . . . . . . . . . . . 72 Line Breaking with Top-Down DP . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 74 Calculating Fibonacci Series with Bottom-Up DP . . . . . . . . . . . . . . . . . . . . . . 79 Summing Ranges Recursively with Bottom-Up DP . . . . . . . . . . . . . . . . . . . . . . 80 Summing Ranges by Precomputing with Bottom-Up DP . . . . . . . . . . . . . . . . . . 81 Brute-Force Search . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 82 Detecting Tautologies . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 82 Solving Cryptarithmetic Puzzles . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 83 Greedy Algorithms . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 87 How to Make Change . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 87 The Traveling Salesman Problem . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 87 Minimum Spanning Tree . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 88 Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 88 Questions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 88

Page 17

Contents in Detail   xv 6 SORTING 91 The Sorting Problem . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 92 Internal vs . External Sorting . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 92 Adaptive Sorting . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 92 In-Place and Out-of-Place Sorting . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 93 Online and Offline Sorting . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 93 Sorting Stability . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 93 JavaScript’s Own Sort Method . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 95 Sort Performance . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 96 Sorting with Comparisons . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 97 Bubbling Up and Down . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 97 Sorting Strategies for Playing Cards . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 100 Making Bigger Jumps with Comb and Shell Sort . . . . . . . . . . . . . . . . . . . . . 103 Going for Speed with Quicksort . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 105 Merging for Performance with Merge Sort . . . . . . . . . . . . . . . . . . . . . . . . . 110 Sorting Without Comparisons . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 112 Bitmap Sort . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 112 Counting Sort . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 114 Radix Sort . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 115 Inefficient Sorting Algorithms . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 116 Stooge Sort . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 116 Slow Sort . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 116 Permutation Sort . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 117 Bogosort . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 117 Sleep Sort . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 117 Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 117 Questions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 118 7 SELECTING 121 Selection Without Comparisons . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 122 Bitmap Selection . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 122 Counting Selection . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 123 Selecting with Comparisons . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 124 The Quickselect Family . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 125 Quickselect . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 126 Median of Medians . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 127 Repeated Step . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 130 Finding the Median with Lazy Select . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 132 Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 134 Questions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 134 8 SHUFFLING AND SAMPLING 137 Choosing Numbers Randomly . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 138 Shuffling . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 139 Shuffling by Sorting . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 139 Shuffling by Coin Tossing . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 140 Shuffling in Linear Time . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 142

Page 18

xvi   Contents in Detail Sampling . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 146 Sampling with Repetition . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 146 Sampling Without Repetition . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 147 Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 154 Questions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 155 9 SEARCHING 159 Search Definition . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 159 Searching Unsorted Arrays . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 160 JavaScript’s Methods . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 160 Linear Search . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 160 Linear Search with Sentinels . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 161 Searching Ordered Arrays . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 163 Jump Search . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 163 Binary Search . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 166 Exponential Search . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 168 Interpolation Search . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 169 Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 171 Questions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 172 PART III: DATA STRUCTURES 175 10 LISTS 177 Basic Lists . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 178 Implementing Lists with Arrays . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 179 Implementing Lists with Dynamic Memory . . . . . . . . . . . . . . . . . . . . . . . . . . 180 Varieties of Lists . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 184 Stacks . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 184 Queues . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 188 Deques . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 191 Circular Lists . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 195 Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 200 Questions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 200 11 BAGS, SETS, AND MAPS 203 Introducing Bags, Sets, and Maps . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 203 JavaScript’s Solutions for Sets . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 205 Objects as Sets . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 205 Set Objects . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 206 Bitmaps . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 206 Using Lists . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 207 Ordered Lists . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 207 Skip Lists . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 210 Self-Organizing Lists . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 215

Page 19

Contents in Detail   xvii Hashing . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 218 Hashing with Chaining . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 219 Hashing with Open Addressing . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 221 Double Hashing . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 226 Double Hashing with Prime Lengths . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 229 Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 232 Questions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 232 12 BINARY TREES 235 What Are Trees? . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 236 General Trees . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 237 Binary Trees . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 237 Binary Search Trees . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 239 Assured Balanced Binary Search Trees . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 249 AVL Trees . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 249 Weight-Bounded Balanced Trees . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 255 Probabilistic Balance Binary Search Trees . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 261 Randomized Binary Search Trees . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 262 Splay Trees . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 270 Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 278 Questions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 279 13 TREES AND FORESTS 283 Defining Trees and Forests . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 283 Representing Trees with Arrays . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 284 Representing Trees with Binary Trees . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 287 Representing Forests . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 288 Traversing Trees . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 288 B-trees . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 291 Defining B-trees . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 292 Finding a Key in a B-tree . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 293 Traversing a B-tree . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 294 Adding a Key to a B-tree . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 295 Removing a Key from a B-tree . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 298 Considering Performance for B-trees . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 303 Red-Black Trees . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 304 Representing Red-Black Trees . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 305 Adding a Key to a Red-Black Tree . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 306 Restoring a Red-Black Tree Structure . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 307 Removing a Key from a Red-Black Tree . . . . . . . . . . . . . . . . . . . . . . . . . . . 309 Considering Performance for Red-Black Trees . . . . . . . . . . . . . . . . . . . . . . . 313 Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 314 Questions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 314

Page 20

xviii   Contents in Detail 14 HEAPS 317 Binary Heaps . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 318 The Structure Property . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 318 The Heap Property . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 319 Heap Implementation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 320 Priority Queues and Heaps . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 326 Heapsort . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 327 Williams’ Original Heapsort . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 327 Heapsort Analysis . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 329 Floyd’s Heap-Building Enhancement . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 329 Treaps . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 332 Creating and Searching a Treap . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 332 Adding a Key to a Treap . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 333 Removing a Key from a Treap . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 336 Considering the Performance of Treaps . . . . . . . . . . . . . . . . . . . . . . . . . . . 339 Ternary and D-ary Heaps . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 340 Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 341 Questions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 341 15 EXTENDED HEAPS 345 Meldable and Addressable Priority Queues . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 346 Skew Heaps . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 347 Representing a Skew Heap . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 348 Merging Two Skew Heaps . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 348 Adding a Key to a Skew Heap . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 350 Removing the Top Key from a Skew Heap . . . . . . . . . . . . . . . . . . . . . . . . . 350 Considering Performance for Skew Heaps . . . . . . . . . . . . . . . . . . . . . . . . . 350 Binomial Heaps . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 351 Binomial Trees . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 351 Defining Binomial Heaps . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 353 Adding a Value to a Binomial Heap . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 354 Merging Two Binomial Heaps . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 356 Removing a Value from a Binomial Heap . . . . . . . . . . . . . . . . . . . . . . . . . . 358 Changing a Value in a Binomial Heap . . . . . . . . . . . . . . . . . . . . . . . . . . . . 360 Considering Performance for Binomial Heaps . . . . . . . . . . . . . . . . . . . . . . . 362 Lazy Binomial Heaps . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 363 Defining Lazy Binomial Heaps . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 363 Adding a Value to a Lazy Binomial Heap . . . . . . . . . . . . . . . . . . . . . . . . . . 364 Removing a Value from a Lazy Binomial Heap . . . . . . . . . . . . . . . . . . . . . . 365 Changing a Value in a Lazy Binomial Heap . . . . . . . . . . . . . . . . . . . . . . . . 366 Considering Performance for Lazy Binomial Heaps . . . . . . . . . . . . . . . . . . . 367 Fibonacci Heaps . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 367 Representing a Fibonacci Heap . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 368 Merging Two Fibonacci Trees . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 370 Adding a Value to a Fibonacci Heap . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 371 Removing a Value from a Fibonacci Heap . . . . . . . . . . . . . . . . . . . . . . . . . 371 Changing a Value in a Fibonacci Heap . . . . . . . . . . . . . . . . . . . . . . . . . . . 372 Considering Performance for Fibonacci Heaps . . . . . . . . . . . . . . . . . . . . . . 375