Fourth Edition - UOITC

1 Fourth EditionData Structuresand AlgorithmAnalysis inC++This page intentionally left blank Fourth EditionData Structuresand AlgorithmAnalysis inC++Mark Allen WeissFlorida International UniversityBostonColumbusIndianapolisNew YorkSan FranciscoUpper Saddle River Amsterdam Cape Town Dubai LondonMadridMilanMunichParisMontrealToro ntoDelhiMexico City Sao Paulo Sydney Hong Kong Seoul SingaporeTa i p e i To k y oEditorial Director, ECS: Marcia HortonCover Designer: Bruce KenselaarExecutive Editor: Tracy JohnsonPermissions Supervisor: Michael JoyceEditorial Assistant: Jenah Blitz-StoehrPermissions Administrator: Jenell ForschlerDirector of Marketing: Christy LeskoCover Image:c De-kay | Manager: Yez AlayanMedia Project Manager: Renata ButeraSenior Marketing Coordinator: Kathryn FerrantiFull-Service Project Management: Integra SoftwareMarketing Assistant: Jon BryantServices Pvt.

2 Of Production: Erin GreggComposition: Integra Software Services Pvt. Managing Editor: Scott DisannoText and Cover Printer/Binder: Courier WestfordSenior Production Project Manager: Marilyn LloydManufacturing Buyer: Linda SagerArt Director: Jayne ConteCopyrightc 2014, 2006, 1999 Pearson Education, Inc., publishing as Addison-Wesley. All rights in the United States of America. This publication is protected by Copyright, and permission should beobtained from the publisher prior to any prohibited reproduction, storage in a retrieval system, or transmissionin any form or by any means, electronic, mechanical, photocopying, recording, or likewise. To obtainpermission(s) to use material from this work, please submit a written request to Pearson Education, Inc.,Permissions Department, One Lake Street, Upper Saddle River, New Jersey 07458, or you may fax your requestto of the designations by manufacturers and sellers to distinguish their products are claimed as those designations appear in this book , and the publisher was aware of a trademark claim, thedesignations have been printed in initial caps or all of Congress Cataloging-in-Publication DataWeiss, Mark structures and algorithm analysis in C++ / Mark Allen Weiss, Florida International University.

3 CmISBN-13: 978-0-13-284737-7 (alk. paper)ISBN-10: 0-13-284737-X (alk. paper)1. C++ (Computer program language) 2. Data structures (Computer science) 3. Computer algorithms. I. 3 :0-13-284737-XISBN-13: 978-0-13-284737-7To my kind, brilliant, and inspiring page intentionally left blank CONTENTSP reface xvChapter 1 Programming: A General What s This book About? Mathematics Modular ThePWo A Brief Introduction to C++ Extra Constructor Syntax and Separation of Interface and C++ Lvalues, Rvalues, and Parameter Return :: The Big-Five: Destructor, Copy Constructor, Move Constructor, CopyAssignmentoperator=, Move Assignmentoperator= C-style Arrays and Function Class ,Comparable, and an Function Separate Compilation of Class Using The Data Members, Constructor, and Basic [] Big-Five46 Summary46 Exercises46 References48 Chapter 2 Algorithm Mathematical What to Running-Time A Simple General Solutions for the Maximum SubsequenceSum Logarithms in the Running Limitations of Worst-Case Analysis70 Summary70 Exercises71 References76 Chapter 3 Lists, Stacks, and Abstract Data Types (ADTs) The List Simple Array Implementation of Simple Linked the Example.

4 Usingeraseon a Implementation Implementation The Stack Stack Implementation of The Queue Queue Array Implementation of Applications of Queues115 Summary116 Exercises116 ContentsixChapter 4 Implementation of Tree Traversals with an Binary An Example: Expression The Search Tree ADT Binary Search Destructor and Copy Average-Case AVL Single Double Splay A Simple Idea (That Does Not Work) Tree Traversals (Revisited) Sets and Maps in the Standard Implementation ofset and An Example That Uses Several Maps176 Summary181 Exercises182 References189 Chapter 5 General Hash Separate Hash Tables without Linked Linear Quadratic Double Hash Tables in the Standard Hash Tables with Worst-CaseO(1) Perfect Cuckoo Hopscotch Universal Extendible Hashing233 Summary236 Exercises237 References241 Chapter 6 Priority Queues (Heaps)

5 Simple Binary Structure Heap-Order Basic Heap Other Heap Applications of Priority The Selection Event Leftist Leftist Heap Leftist Heap Skew Binomial Binomial Queue Binomial Queue Implementation of Binomial Priority Queues in the Standard Library282 Summary283 Exercises283 References288 Chapter 7 Insertion The STL Implementation of Insertion Analysis of Insertion A Lower Bound for Simple Sorting Worst-Case Analysis of Analysis of Analysis of Picking the Partitioning Small Actual Quicksort Analysis of A Linear-Expected-Time Algorithm for A General Lower Bound for Decision Decision-Tree Lower Bounds for Selection Adversary Lower Linear-Time Sorts: Bucket Sort and Radix External Why We Need New Model for External The Simple Multiway Polyphase Replacement Selection340 Summary341 Exercises341 References347 Chapter 8 The Disjoint Sets Equivalence The Dynamic Equivalence Basic Data Smart Union Path Worst Case for Union-by-Rank and Path Slowly Growing An Analysis by Recursive AnO(Mlog *N) AnO(M (M, N) )

6 An Application372xiiContentsSummary374 Exercises375 References376 Chapter 9 Graph Representation of Topological Shortest-Path Unweighted Shortest Dijkstra s Graphs with Negative Edge Acyclic All-Pairs Shortest Shortest Path Network Flow A Simple Maximum-Flow Minimum Spanning Prim s Kruskal s Applications of Depth-First Undirected Euler Directed Finding Strong Introduction to Easy vs. The Class NP-Complete Problems434 Summary437 Exercises437 References445 Chapter 10 Algorithm Design Greedy A Simple Scheduling Huffman Approximate Bin Divide and Running Time of Divide-and-Conquer Closest-Points The Selection Theoretical Improvements for Arithmetic Dynamic Using a Table Instead of Ordering Matrix Optimal Binary Search All-Pairs Shortest Randomized Random-Number Skip Primality Backtracking The Turnpike Reconstruction Games511 Summary518 Exercises518 References527 Chapter 11 Amortized An Unrelated Binomial Skew Fibonacci Cutting Nodes in Leftist Lazy Merging for Binomial The Fibonacci Heap Proof of the Time Splay Trees551 Summary555 Exercises556 References557 Chapter 12 Advanced Data Structuresand Top-Down Splay Red-Black Bottom-Up

7 Top-Down Red-Black Top-Down Suffix Arrays and Suffix Suffix Suffix Linear-Time Construction of Suffix Arrays and Suffix Pairing Heaps602 Summary606 Exercises608 References612 Appendix A Separate Compilation ofClass Everything in the Explicit Instantiation616 Index 619 PREFACEP urpose/GoalsThe Fourth Edition ofData Structures and Algorithm Analysis in C++describesdata structures,methods of organizing large amounts of data, andalgorithm analysis,the estimation of therunning time of algorithms. As computers become faster and faster, the need for programsthat can handle large amounts of input becomes more acute. Paradoxically, this requiresmore careful attention to efficiency, since inefficiencies in programs become most obviouswhen input sizes are large. By analyzing an algorithm before it is actually coded, studentscan decide if a particular solution will be feasible.

8 For example, in this text students look atspecific problems and see how careful implementations can reduce the time constraint forlarge amounts of data from centuries to less than a second. Therefore, no algorithm or datastructure is presented without an explanation of its running time. In some cases, minutedetails that affect the running time of the implementation are a solution method is determined, a program must still be written. As computershave become more powerful, the problems they must solve have become larger and morecomplex, requiring development of more intricate programs. The goal of this text is to teachstudents good programming and algorithm analysis skills simultaneously so that they candevelop such programs with the maximum amount of book is suitable for either an advanced data structures course or a first-yeargraduate course in algorithm analysis.

9 Students should have some knowledge of inter-mediate programming, including such topics as pointers, recursion, and object-basedprogramming, as well as some background in discrete the material in this text is largely language-independent, programming requiresthe use of a specific language. As the title implies, we have chosen C++for this ++has become a leading systems programming language. In addition to fixing manyof the syntactic flaws of C, C++provides direct constructs (theclassandtemplate)toimplement generic data structures as abstract data most difficult part of writing this book was deciding on the amount of C++toinclude. Use too many features of C++and one gets an incomprehensible text; use too fewand you have little more than a C text that supports approach we take is to present the material in anobject-based such,there is almost no use of inheritance in the text.

10 We use class templates to describe genericdata structures. We generally avoid esoteric C++features and use thevectorandstringclasses that are now part of the C++standard. Previous editions have implemented classtemplates by separating the class template interface from its implementation. Althoughthis is arguably the preferred approach, it exposes compiler problems that have made itxvxviPrefacedifficult for readers to actually use the code. As a result, in this Edition the online coderepresents class templates as a single unit, with no separation of interface and implementa-tion. Chapter 1 provides a review of the C++features that are used throughout the text anddescribes our approach to class templates. Appendix A describes how the class templatescould be rewritten to use separate versions of the data structures, in both C++and Java, are available onthe Internet.