书名：高级算法和数据结构
ISBN：978-7-115-61457-5
本书由人民邮电出版社发行数字版。版权所有，侵权必究。
您购买的人民邮电出版社电子书仅供您个人使用，未经授权，不得以任何方式复制和传播本书内容。
我们愿意相信读者具有这样的良知和觉悟，与我们共同保护知识产权。
如果购买者有侵权行为，我们可能对该用户实施包括但不限于关闭该帐号等维权措施，并可能追究法律责任。
著 [意] 马塞洛·拉·罗卡（Marcello La Rocca）
责任编辑 吴晋瑜
人民邮电出版社出版发行 北京市丰台区成寿寺路11号
邮编 100164 电子邮件 315@ptpress.com.cn
网址 http://www.ptpress.com.cn
读者服务热线：(010)81055410
反盗版热线：(010)81055315
这是一本关于“高级/进阶”算法和数据结构的图书，主要介绍了用于Web应用程序、系统编程和数据处理领域的各种算法，旨在让读者了解如何用这些算法应对各种棘手的编码挑战，以及如何将其应用于具体问题，以应对新技术浪潮下的“棘手”问题。
本书对一些广为人知的基本算法进行了扩展，还介绍了用于改善优先队列、有效缓存、对数据进行集群等的技术，以期读者能针对不同编程问题选出更好的解决方案。书中示例大多辅以图解，并以不囿于特定语言的伪代码以及多种语言的代码样本加以阐释。
学完本书，读者可以了解高级算法和数据结构的相关内容，并能运用这些知识让代码具备更优性能，甚至能够独立设计数据结构，应对需要自定义解决方案的情况。
本书可作为高等院校计算机相关专业本科高年级学生以及研究生的学习用书，也可供从事与算法相关工作的开发者参考。
理论之美与前沿技术激动人心的融合，其核心就是算法与数据结构。可以说，如果把硬件作为计算进步的“主体”（躯干），那么对算法和数据结构的研究就是其“大脑”。正是因为可以有效利用计算资源来解决问题，最近的许多技术进步才得以实现，而这往往都归功于对算法的有效开发和实现，以及对数据结构的巧妙使用。
计算机科学家、软件开发人员、数据科学家或任何依赖计算能力工作的人，都应精通算法和数据结构。正因如此，IT公司在面试中最常提问的问题大多与算法和数据结构相关。
即使对于专家来说，要掌握并记住现有算法的所有细节也是相当困难的。不过，真正重要的是对这些算法保持良好的直觉。只有这样，我们才可以像搭积木一样，运用这些算法完成大型项目或者解决各种问题。要有这种直觉，就必须有严谨的理论和数学基础、扎实的编程知识储备，以及对核心概念的深刻理解。
希望本书能帮助你建立起这种直觉。在本书中，Marcello将严谨的理论与广泛的实际应用相结合，以叙事笔触描述了有趣的故事和现实生活中的例子。
Marcello曾在多家知名技术公司担任过开发人员和机器学习科学家，他利用自己丰富的工作经验，以一种清晰、简洁而又不失全面的方式向读者介绍算法与数据结构。这些算法和数据结构已广泛应用于各个行业和研究领域。
凭借广泛适用的方法、友好的语言和有趣的类比，Marcello像展示基础知识中的树和堆那样，为我们揭开了多个复杂主题的神秘面纱，如MapReduce模型、遗传算法以及模拟退火算法。如果读者想要深入了解计算机科学中的构建原理，那么建议你阅读本书。读完本书后，我脑子里唯一的想法是，“我在硅谷准备第一次面试时，要是有这本书就好了！”
——Luis Serrano博士
量子人工智能研究科学家
Zapata Computing公司
欢迎阅读《高级算法和数据结构》！
很高兴你能加入探索数据结构和算法世界的旅程！希望这段旅程对你和我们所有人来说都足够激动人心。
本书讨论的主题不但对推动软件工程的发展做出了贡献，而且切切实实地改变了我们的世界，至今仍时时刻刻地影响着我们。平均而言，你每天都会接触到数十种使用这些算法的设备和服务。
对算法的研究早在计算机科学诞生以前就开始了。想想看，欧拉法和图论领域已有长达三个世纪的历史。但是，如果与两千多年前就已发明出来的埃拉托色尼筛法（用来制作素数表）相比，这似乎有点小巫见大巫了。
然而，相当长一段时间内，算法通常都被归于学术范畴，而业界也只有一些像贝尔实验室这样的机构才能够参与其中。20世纪50年代到90年代，贝尔实验室的研发团队在算法领域取得了巨大的进步，其主要成就有动态规划、贝尔曼-福特算法以及用于图像识别的卷积神经网络。
幸运的是，和那个时代相比，现在的许多事情都发生了变化。2000年之后，数学家和计算机科学家日益受到大型软件公司的青睐。机器学习等新领域开始出现，人工智能和神经网络等其他领域在经历漫长的寒冬后重新焕发生机。
我是从上大学时迷上算法的。虽然早在高中时期我就学习了搜索和排序算法，但是直到学习了树和图，我才意识到它们可以带来的改变以及我对这些主题有多么喜爱。
那是我第一次发觉代码可运行并不是编程的唯一目标，甚至不是主要目标。这些代码的工作方式、运行效率以及整洁程度，和它们能够工作同等重要，甚至可以说更为重要。（遗憾的是，又过了若干年，我才对测试有了同样的感悟。）
这本书的写作花费了我大量的时间，远远超出我在4年前向编辑提出这个想法时的预期。这本书的出版故事（至少现在回想起来）非常有趣，但我并不打算在这里长篇大论地絮叨。你只需要知道在写这本书的4年里，我换了3份工作，在两个国家待过，搬过5次家！
虽然写这本书付出的努力颇多，但是收获也颇多。首先也是最重要的，写一本书意味着开始一条成长之路。因为无论你在一个主题上工作了多久，或是你对这个主题有多么了解，要写出来，你就得强迫自己质疑已经对这个主题所知道的一切，深入研究之前在应用时可能忽略的每个细节，花大量的时间来研究、消化和处理各种概念，直到你有足够的信心可以把这个主题解释给对它一无所知的人。通常来说，一个很好的检验标准就是让某个不在相关领域工作的家人听你进行介绍。对了，请记得选一位非常有耐心的家人。
感谢一路走来给予我帮助的所有人。
首先，感谢Manning出版社的两位编辑，他们是负责帮助我将手稿从最初的稿件转换为符合出版社要求的Helen Stergius，以及在过去几年里一直致力于推进本书出版的Jennifer Stout。没有他们的帮助，就没有本书的顺利付梓。很高兴能与你们合作，感谢你们的帮助、所提的宝贵建议以及对我的耐心！
感谢本书的两位技术编辑！非常感谢已经加入团队好几年的Arthur Zubarev，你提供了大量出色的反馈，并不断鞭策着我前进，非常荣幸能与你合作。特别感谢我的朋友Aurelio De Rosa。在着手写作本书之前，我们曾一起在一个JavaScript网站上发表帖子，我也有幸让他担任了那里的编辑。除了教给我很多关于技术写作的知识，他对本书的贡献也是巨大的。他是本书的第一位技术编辑，除了为整本书指明方向，他还指出了需要纳入其中的主题，并对代码进行了审查。此外，当我找出版商时，他向我推荐了Manning出版社。
还要感谢Manning出版社的其他所有人，他们与我一起参与了本书的制作和推广，本书的成功离不开整个团队的努力。感谢审稿人Andrei Formiga、Christoffer Fink、Christopher Haupt、David T. Kerns、Eddu Melendez、George Thomas、Jim Amrhein、John Montgomery、Lucas Gerardo Tettamanti、Maciej Jurkowski、Matteo Gildone、Michael Jensen、Michael Kumm、Michelle Williamson、Rasmus Kirkeby Str b k、Riccardo Noviello、Rich Ward、Richard Vaughan、Timmy Jose、Tom Jenice、Ursula Cervantes、Vincent Zaballa以及Zachary Fleischmann。感谢你们早在手稿的编写阶段花费大量的时间阅读并给出宝贵建议。
感谢我的家人和朋友，感谢你们这些年来对我的支持和耐心。写这本书花了我大量的时间！如果你也有过这样的体验，就会明白这意味着占用许多可以去郊游、与朋友聚会或做家务的晚上、假期及周末，因为所有的这些时间都需要用于手稿上。如果没有家人及朋友的帮助和理解，我是不可能完成本书的。
最后，我还要特别提及一些人。正是因为他们，我才能成为计算机科学家。
感谢我在卡塔尼亚大学求学期间遇到的老师们。想要感谢的老师太多了，囿于篇幅，在此我只列出如下三位导师：Gallo教授、Cutello教授以及Pappalardo教授。在这个大学学位的含金量受到质疑的时代，人们总想找到比取得大学学位更快、更实用的替代方案，但我仍然认为对导师和母校这么多年来所做的出色工作给予认可是非常重要的。大规模开放在线课堂（Massive Open Online Course，MOOC）和代码训练营的确是很好的替代之法，正是因为它们对授课地点和学生身份不设限，才让教育朝着惠及大众的方向迈出了一大步。但我觉得，如果没有上大学的经历，我一定会错过对批判性态度的培养。批判性态度让我们能够知道如何推理问题，以及如何获得更全面的技能知识，而不仅仅是满足找工作的需要。
不得不承认，我也曾对像线性代数这样的数学课程持怀疑态度。在从事开发工作时，我根本意识不到会在什么时候用到它们。不过在毕业若干年后，当我开始接触机器学习时，所有的这些数学知识都派上了用场。
最重要的是，我要感谢在我早年的生活和学习中不断支持我的一个人——我的母亲。为了能让我完成学业，以及满足我继续深造的愿望，她做出了巨大的牺牲。有了她的支持，我才能实现自己职业生涯中的所有目标，包括写这本书。因此，从某种意义上讲，这本书的成功和她密不可分。
谈及为什么需要花时间学算法，我至少可以列举出三个很好的理由。
（1）性能：选择正确的算法可以显著提升应用程序的速度。仅就搜索来说，用二分查找替换线性搜索就能为我们带来巨大的收益。
（2）安全性：如果你选用了错误的算法，攻击者就可以利用它使你的服务器、节点或应用程序崩溃。比如哈希碰撞拒绝服务攻击，就利用了作为字典来存放POST请求以提交参数的哈希表，并使用有可能导致大量碰撞的序列来让这个哈希表退化，进而使整个服务器停止响应。另一个关于安全性的有趣例子是，曾有黑客成功使用有缺陷的随机数生成器入侵在线扑克网站。[1]
[1] “How we learned to cheat at online poker: A study in software security”（“在线扑克如何作弊：一次软件安全研究”），Brad Arkin等，developer.com期刊，1999年。
（3）设计代码的效率：如果有合适的构建模块可用来完成各种事情（特别是如果还能重用代码的话），你就能更快地实现代码的编写，而且会让代码更整洁。
那么，为什么推荐你阅读本书呢？一个很重要的原因就是，在本书中，我精挑细选地为你准备了一个具有战略意义的“高级算法库”，其中的算法能够帮助你改进代码，进而应对现代系统面临的各种挑战。
此外，我试着用一种不同于普通教材的方法来介绍这些算法。虽然本书也会解释算法背后的理论，但更侧重于给出使用这些算法的实际应用程序的相关背景信息，以及在什么时候应该使用这些算法的建议。
在日常工作中，你通常要做的是处理某个大型软件（也可能是遗留软件）上的某个特定部分。但是，在整个职业生涯中，你肯定会遇到需要设计大型软件的情况。到了那时，你就会用上本书讨论的大部分内容了。我将尽可能地给出有关如何编写简洁且高效代码的建议，以帮助你解决将来要面对的相关问题。
正是因为采用了这 种新的方式来介绍算法，所以在每一章中，我都会列举有助于解决某些问题的数据结构。这是一本当你需要用以提高应用程序性能的建议时，可以随时参考的辅助性手册。
最后要说的是，如果你碰巧读过Aditya Y. Bhargava撰写的《算法图解》（人民邮电出版社，2017年），并且十分喜欢里面的内容；那么只要你还想继续学习算法，就可以通过阅读《高级算法和数据结构》得到进一步提升。如果你还没有读过《算法图解》，我强烈推荐你看一看，这本书是你了解算法相关主题的绝佳选择，它能广受欢迎绝非偶然。希望我的这本书也能达到同样的效果。
本书的大部分章节是为对算法、编程和数学已有一些基本了解的读者编写的。如果你想复习一下这些基本内容或者希望快速了解这部分知识，请参阅本书的附录部分。
如果你事先熟悉了如下概念，则可以更好地掌握本书的内容。
● 良好的数学和代数基础，大O符号（见附录B）以及渐近分析的相关内容。
● 简单的数据结构。
● 附录C中的概念。
❏ 基本的像数组和链表这样的存储结构。
❏ 哈希表和哈希算法。
❏ 树。
❏ 容器（队列和堆栈）。
❏ 递归的基本概念。
第1章定义了算法和数据结构，阐释了它们的区别，并通过一个例子探究了用不同算法解决问题的过程，以及如何利用这些算法来找到更好的解决方案。
从第2章开始，本书剩余的内容将分为三大部分以及附录。每一部分会集中介绍一大类内容——可以是某个抽象的目标，也可以是我们需要解决的某类问题。
第一部分探讨了一些高级数据结构，目的是让你进一步掌握像跟踪一个或一组事物这样的基本操作。这一部分旨在让你熟悉这样一种思维模式：对数据执行操作的方法有很多，而最好的方法取决于上下文和需求。
第2章介绍了二叉堆的高级变体——d叉堆，还描述了第一部分各章中用来介绍各种主题的编撰结构。
第3章利用树堆进一步探讨了堆的高级用法。树堆是二叉搜索树和堆的混合体，可以在不同的上下文中提供帮助。
第4章介绍了布隆过滤器。这是哈希表的一种高级形式，可以帮助我们节省内存，同时将查找操作的平摊时间复杂度维持在常数级别。
第5章介绍了一些用来跟踪不交集的替代数据结构。不交集是构建高级算法的基石，已用在若干实际应用中。
第6章介绍了两种在存储和查找字符串方面都优于通用容器的数据结构：trie（前缀树）和基数树（又称为压缩前缀树）。
第7章基于前面介绍的数据结构构建了一种能有效处理缓存的组合数据结构：LRU缓存，还详细讨论了LFU缓存（LRU缓存的变体）以及如何在多线程环境中同步共享容器的问题。
第二部分探讨搜索算法的一种特殊情况：处理多维数据时应该如何索引这些数据，以及如何执行空间查询。本书将再次展示一些比使用基本搜索算法有更大改进的专用数据结构。不仅如此，这一部分还将描述另一个重要的主题——聚类。聚类用到了大量的空间查询，还用到了MapReduce这样的分布式计算模型。
第8章探讨了最近邻问题。
第9章描述了k-d树—— 一种支持在多维数据集上进行高效搜索的解决方案。
第10章介绍了树的更多高级版本，如SS树和R树。
第11章深入探讨了如何基于需要派送的客户地址找到最近的仓库，还着重介绍了最近邻搜索的应用。
第12章介绍了三种旨在高效实现最近邻搜索的聚类算法：k均值算法、DBSCAN算法和OPTICS算法。
第13章介绍了MapReduce（一种强大的分布式计算模型），并探讨了如何将其应用到第12章所讨论的聚类算法上。
第三部分只关注一种数据结构——图。这部分内容将介绍各种旨在推动当今人工智能和大数据发展的算法。
第14章介绍了图数据结构的基础知识，还介绍了深度优先遍历（DFS）、广度优先遍历（BFS）、迪杰斯特拉算法以及A*算法，并描述了如何使用它们来解决“最短路径”问题。
第15章介绍了图嵌入、平面性以及稍后几章将要尝试解决的几个问题，例如如何找到对图进行嵌入时的最小交叉数，以及如何更好地绘制图。
第16章描述了一种我们在机器学习中经常要用到的基本算法——梯度下降算法，并展示了如何将这种算法应用于图以及图嵌入。
第17章在第16章的基础上介绍了模拟退火算法——这是一种更强大的优化技术。在处理不可微函数或是具有多个局部最小值的函数时，这种算法能够克服梯度下降算法的缺点。
第18章描述了遗传算法——这是一种十分高级的优化技术，有助于加快收敛速度。
本书各章会按照“提出问题→设计数据结构作为解决方案→实现解决方案并分析运行时间和内存需求”这一结构来安排内容。
最后，附录部分涵盖了阅读本书所必须掌握的那些关键主题。附录不是基于示例来讲解的，而是采用了与正文不同的内容组织方式。附录旨在向读者提供在开始阅读正文之前就应该熟悉的各种知识的摘要，其中的大部分主题是基础算法课程中的内容。我们建议读者在阅读第2章之前浏览一遍附录中的内容。
附录A介绍了用来描述算法的伪代码的各种符号。
附录B提供了对大O符号以及时间分析与空间分析的总结。
附录C和附录D给出了各种核心数据结构的摘要。这些数据结构是本书将要介绍的各种高级数据结构的基础模块。
附录E解释了递归。递归是一种比较具有挑战性的编程技术，旨在对算法进行更明确、更简洁的定义。当然，在采用递归时，我们需要对利弊进行权衡。
附录F给出了不同类型的随机算法的定义，包括蒙特卡罗算法、拉斯维加斯算法，还介绍了各种分类问题和随机解决方案的评估指标。
本书中的算法是用伪代码加以解释的，因此读者不需要有特定编程语言的背景知识。
不过，我们还是希望读者对基本的、与语言无关的编程概念有一定的了解，例如循环、条件、布尔运算符、变量以及赋值的相关概念。
附录A提供了一份简短的指南，对本书用到的语法（或者更确切地说，伪语法）进行了介绍。我们建议读者能够在开始阅读第1章之前浏览一遍附录A。当然，如果你对自己非常有信心，可以直接阅读正文中的代码，当觉得对其中使用的语法不甚了解时，再参考附录A中的内容。
本书给出了伪代码，如果你对特定的编程语言感兴趣，或者想要弄清楚书中的概念是如何用真实的可执行代码来实现的，可访问本书的GitHub仓库，以了解如何使用不同的编程语言（如Java、Python、JavaScript）实现本书介绍的各种数据结构。
Marcello La Rocca现为一家电商公司的高级软件工程师，曾参与开发Twitter、微软和苹果等公司的大型Web应用程序和数据基础设施，并发明了NeatSort这一自适应排序算法。他的主要研究领域为图、算法优化、机器学习和量子计算。
本书封面上的人物插图名为“Femme de Fiume”或“河边的女士”。这幅插图出自法国1797年出版的Costumes de Différents Pays（由 Jacques Grasset de Saint-Sauveur撰写），这本书中有身着不同国家及地区服饰的人物画像，且其中所有插图都是手工精细绘制和着色的。这些丰富多彩的插图生动再现了200多年前，世界上不同地区、城镇、村庄和社区在文化上的巨大差异。人们讲着不同的语言和方言，无论是在街上还是在乡下，只要通过着装，就很容易辨认出他们住在哪里，甚至能够看出他们的职业或身份。
后来，人们的着装发生了变化，彼时那般丰富的地区多样性逐渐消失。现在，我们已经很难区分来自不同国家的人，更不用说来自不同地区或城镇的人了。也许，我们以牺牲文化多样性为代价换来了如今个人生活的更加多样化，当然还有更加多样化和快节奏的科技化生活。
在这个计算机图书同质化的时代，Manning出版社选择Costumes de Différents Pays中的插画作为封面，将200多年前丰富多样的地区生活还原出来，以此颂扬计算机行业的创造性、积极性和趣味性。
本章主要内容
● 为什么需要了解数据结构和算法
● 算法和数据结构的区别
● 对问题进行抽象
● 从问题到解决方案
学习算法与数据结构是一个非常好的决定！
如果你还在犹豫不决，我们希望本章介绍的内容能打消你的疑虑并激发你对这个主题的兴趣。
为什么要学习数据结构和算法？简单来说，想要成为更优秀的软件开发人员，学习数据结构和算法能让我们事半功倍。
你有没有听说过“马斯洛的锤子”（又称为“工具规律”）？这是一个通过观察得到的假设，意味着只知道一种做事方式的人，想把这种方式运用到所有情况之下，而不关注情况的差异性。
如果只有锤子这一个工具，那么容易把所有东西当作钉子。类似地，如果只知道可以对列表进行排序，那么在向任务列表中添加新的任务或者选择下一个需要处理的任务时，通常就会尝试对任务列表进行排序，而不会根据上下文来获得更高效的解决方案。
本书旨在为你提供更多用于解决问题的“工具”。我们将以计算机科学专业基础课通常都会介绍的基本算法作为基础，向你介绍更高级的内容。
读完本书，你应该能够知道在什么情况下，可以使用特定的数据结构和（或）算法来提高代码的性能。
当然，我们并不期望你能把后面将要讨论的所有数据结构的每个细节都熟记于心，而更希望你能够了解如何推理问题，进而找到可以解决问题的相关算法。作为一本类似于菜谱的手册，本书会把各种问题归纳到常见的几个大类里，并给出可以解决这几大类问题的最佳数据结构。
需要注意的是，本书的某些主题较为超前。因此，在深入研究具体细节时，你可能需要反复阅读才能真正理解所有的内容。本书会给出多层次的深入分析，并将高级的部分放在各章的末尾。因此，如果只是想要了解这些主题，那么你可以忽略这些针对理论而进行的深入研究。
首先，我们需要使用一种统一的方式来描述并评估算法。
一种非常标准的描述方式如下：算法会根据所接收的输入以及所提供的输出进行描述。算法的具体细节可以用伪代码（忽略编程语言的实现细节）或者实际代码加以说明。
数据结构虽然与算法类似，但稍有不同，因为在其中还必须描述对数据结构所能执行的操作。通常来说，每个操作都会像算法那样，通过输入和输出进行描述。除此之外，对于数据结构来说，这些操作的副作用也需要描述，因为这些操作可能会对数据结构本身进行修改。
要彻底了解为什么会有副作用产生，你首先需要正确地对数据结构进行定义。
数据结构（data structure）是一种对数据进行组织的特定解决方案，不仅可以为元素提供存储空间，还提供了存放和获取这些元素的功能[1]。
[1] 具体来说，至少会有一个将新元素添加到数据结构的方法，以及另一个可以获取特定元素或者查询数据结构的方法。
最简单的数据结构就是数组。比如，字符数组可以为有限数量的字符提供存储空间，并且提供了根据位置来获取字符数组中各个字符的方法。图1.1展示了array = ['C', 'A', 'R']是如何存储的。对于存放了字符'C'、'A'和'R'的字符数组来说，array[1]对应的值就是'A'。
图1.1 数组的（简化的）内部表示。数组中的每个元素都对应着内存[2]中的一个字节。位于这些元素下方的是内存地址，位于其上方的则是对应的索引。数组是通过连续的内存块进行存储的，因此可以通过元素在数组里的索引并加上数组中第一个元素的偏移量来得到其地址。例如，数组中第4个字符（array[3]，图中为空）的地址就是0xFF00 + 3 = 0xFF03
[2] 在现代架构或编程语言中，数组元素可能会对应内存中的一个字（word）而不是一个字节（byte）。但是为了简便，这里假设字符数组被存放在一系列的字节中。
数据结构既可以是抽象的，也可以是具体的。
● 抽象数据类型（Abstract Data Type，ADT）会指定对某些数据可以执行的操作以及这些操作的计算复杂度，但不会提供有关如何存储数据或者如何使用物理内存的详细信息。
● 数据结构是基于抽象数据类型所提供的规范而得到的具体实现。
什么是抽象数据类型？
抽象数据类型可以理解为蓝图，而数据结构则会把其中的规范转换为真实代码。
抽象数据类型是从使用者的角度定义的，因此其行为会使用可能的值、可能的操作以及与这些操作对应的输出和副作用加以描述。
如果要更正式地来描述抽象数据类型，那么应该是“由一组类型、这组类型的指定类型、一组功能以及一组公理构成的合集”。
对于数据的具体表示——数据结构来说，数据结构则是从实现者而非使用者的角度描述的。
对于上面这个数组来说，一种可能的静态数组的抽象数据类型如下：“数组是一个可以存储固定数量元素的容器，其中的每个元素都有一个与之对应的索引（数组中元素的位置），可通过元素的位置来访问任何元素（随机访问）”。
要实现静态数组，还需要注意以下细节。
● 数组的大小在数组创建之后是固定不变的，还是可以修改的？
● 数组使用的内存是静态分配的，还是动态分配的？
● 数组只能包含单一类型的元素，还是可以包含多种类型的元素？
● 数组会实现为原始的内存块，还是实现为对象？如果实现为对象的话，数组会有哪些属性？
即使对于像数组这样的简单数据结构，不同的编程语言也会对上面的问题做出不同的选择。但是，所有的编程语言都会确保对数组的实现能够满足上面对数组的抽象数据类型所做的描述。
堆栈是另一个可以用来了解抽象数据类型和数据结构之间差异的好例子。我们将在附录C和附录D中对堆栈进行描述。当然，你应该听说过堆栈这种数据结构。
堆栈的抽象数据类型可以描述如下：“一个可以存储无限数量元素的容器，并且可以按照与插入顺序相反的顺序从最新的元素开始依次删除元素”。
进一步来讲，通过分解容器上可执行的操作可以得到堆栈的另一种描述：“堆栈是一个支持如下两种主要方法的容器”。
● 插入元素。
● 删除元素。如果堆栈不为空，那么最后插入的元素将从堆栈中被删除并返回。
尽管以上描述还是不那么通俗易懂，但是要比前一种描述更清晰，也更模块化。
这两种描述都足够抽象，也都具有一般性，足以让你在不同的编程语言、范式和系统[3]中实现堆栈。
[3] 原则上，系统并不是必须和计算机科学相关。例如，你可以把一堆需要检查的文件描述为系统。另外，洗一堆盘子这个经常在计算机科学课堂上见到的例子也可以视为一个系统。
不过在某些时候，我们还是得对数据结构进行具体的实现，这时就需要讨论下面这些细节了。
● 元素用什么方式来存储？
❏ 数组？
❏ 链表？
❏ 磁盘上的B树？
● 如何记录插入的顺序？（与上一个问题相关）
● 堆栈的最大尺寸是已知并且保持不变的吗？
● 堆栈是否可以包含多种类型的元素，还是所有元素都必须属于同一类型？
● 如果想在空的堆栈上执行删除操作，应该怎么办？（例如，应该返回null还是抛出错误呢？）
诸如这样的问题数不胜数，这里列举的问题仅为让你有个大致的了解。
定义抽象数据类型的关键在于列出其允许的一系列操作。这就相当于定义了一套API[4]，也可以说是与客户端的契约。
[4] 应用程序接口（Application Programming Interface）。
在需要对数据结构进行描述时，我们可以遵循一些简单的步骤，以确保提供的规范是全面且明确的。
● 指定数据结构的API ，并且确定方法的输入与输出。
● 描述数据结构的高阶行为。
● 详细描述具体实现的行为。
● 对数据结构的方法进行性能分析。
在本书中，我们都会先描述实际使用各种数据结构的具体情况，然后按照相同的流程来介绍它们。
在介绍第一种数据结构时（见第2章开头），我们还会对API描述的约定作进一步的详细解释。
算法和数据结构并不是同一件事。严格来说，它们并不是等效的。但是，我们通常在使用的时候会互换这两个术语。为了简便，后文我们会用数据结构这个术语来指代“数据结构及其所有相关的方法”。
有很多方法可以用来说明这两个术语之间的区别，但是笔者特别喜欢下面这个比喻：数据结构好比名词，而算法好比动词。
笔者之所以喜欢这个比喻，是因为这个比喻不仅表明了它们的不同行为，还暗示了它们之间的依赖性。例如，要在英语中构建一个有意义的短语，就需要同时包含名词和动词，还需要给出主语（或宾语）以及将要执行（或承受）的动作。
数据结构和算法是相互联系的，就好比一张纸的正反两面。
● 数据结构是基础，是一种通过组织内存区域来表示数据的方法。
● 算法是过程，是用来对数据进行转换的一系列指令。
如果没有用来对数据进行转换的算法，数据结构就只是存放在内存芯片里的一堆二进制数；而如果没有可以操作的数据结构，则大多数算法甚至不会出现。
除此之外，每种数据结构还隐式地定义了其中可以执行的算法。例如，用来向数据结构中添加元素的方法以及从中获取或删除元素的方法。
实际上，一些数据结构的定义就是为了能让某些算法更高效地运行而出现的，例如哈希表以及按键进行搜索的算法[5]。
[5] 你可以在附录C里找到有关这个主题的更多信息。
因此，我们可以把算法和数据结构当作同义词来使用，毕竟在这个上下文中提到其中一个时总会暗示另一个。例如，在描述数据结构时，如果要让描述是有意义且准确的，就必须同时描述数据结构的方法（算法）。
读到这里，你可能想问：“我还需要自行编写数据结构吗？”
通常来说，你应该很少会遇到“只能从头开始编写一种新的数据结构”这种情况。如今，就大多数编程语言来说，找到一个包含常见数据结构实现的库还是很容易的。此外，这些库的编写者都是懂得如何对性能进行优化或是能解决安全问题的专家。
实际上，本书的主要目标是让你熟悉各种工具，并且通过训练让你能够识别出可以使用这些工具改进代码的机会。在较高层次上了解这些工具的内部工作方式是学习过程中的重要组成部分。但是，在某些特殊情况下，你还是会需要动手编写代码。例如，你使用了一种没有太多可用库的全新编程语言，或者你需要自定义一种数据结构来解决特殊问题，等等。
因此，是否要为数据结构编写你自己的实现取决于许多因素。其中一个因素就是，你需要的数据结构有多高级以及你使用的编程语言有多主流。
为了说明这一点，让我们以聚类为例。
如果你使用的是像Java或Python这样的主流语言，那么通常你能找到许多包含k均值算法且值得信赖的库。k均值算法是一种非常简单的聚类算法。
如果你使用的是像Nim或Rust这样的新兴语言，那么你可能很难找到一个由团队实现的、进行过全面测试的并且会不断得到维护的开源库。
另外，如果你需要的是像DeLiClu这样的高级聚类算法，那么即便使用的是Java或Python语言，也很难找到可以信任的且可以直接放在生产环境中运行的实现。
需要了解这些算法的内部工作方式的另一个因素是，你需要对某种算法进行自定义。这可能是因为你需要针对现实环境进行优化。例如，你需要一些特别的类似支持多线程运行且保证线程安全这样的属性，或者需要一种略有不同的行为。
也就是说，即使你只专注我们在前面所呈现的内容（只是了解应该什么时候以及如何使用这些数据结构），也足以让你的编码技能提升一个层次。下面让我们通过一个例子来说明算法在现实世界中的重要性，并介绍我们是如何对算法进行描述的。
恭喜，你被选中为火星定居点的首个居民！不过，火星上并没有商店，不能随便购物。鉴于这种情况，你只能自己种植农作物以获取食物。但是，在最初的几个月里，你可以依靠随身携带的食物来维持自己的生命。
不过，你能携带的食物有这样一个问题：货运箱的总重量不能超过1000kg，这是一个硬性限制。
更麻烦的是，你只能从下面这组已经打包在盒子里的食物中进行选择。
● 土豆，800kg。
● 大米，300kg。
● 面粉，400kg。
● 花生酱，20kg。
● 番茄罐头，300kg。
● 豆类，300kg。
● 草莓酱，50kg。
水是不限量的，但是对于上面的每一种食物，你只能选择要不要带，而不能拆分并重新打包。显然，你不会只带土豆（就像《火星救援》里那样），而是会对要放进货运箱里的东西有所选择。
对于探险队来说，他们期望你在逗留期间能够保持良好的身体状态和充沛的精力。因此，要带什么食物的主要选择标准是食物的营养价值。如果用食物的总热量（总卡路里，1卡路里 = 4.19焦耳）来表示其营养价值，那么每一种可带食物的总卡路里如表1.1所示。
表1.1 每一种可带食物的重量及其总卡路里
| 食物 |
重量/kg |
总卡路里[6]/cal |
|---|---|---|
| 土豆 |
800 |
1 501 600 |
| 面粉 |
400 |
1 444 000 |
| 大米 |
300 |
1 122 000 |
| 豆类 |
300 |
690 000 |
| 番茄罐头 |
300 |
237 000 |
| 草莓酱 |
50 |
130 000 |
| 花生酱 |
20 |
117 800 |
[6] 为便于计算，对于食物的总热量，本书保留了总卡路里（单位：卡，1卡 = 4.19焦耳）这一说法。——编辑注。
实际上，你的选择并不能改变实际可以携带的食物（尽管你的抗议可以理解，但任务控制部门在这一点上绝不会让步），真正重要的是每个盒子的重量及其所能提供的总卡路里。
我们的问题可以抽象为：“在不能对任何元素进行分割的情况下，从一个集合中选择任意数量的元素，使得它们的总重量不超过1 000kg并且提供的热量最高。”
问题已经明确了，接下来我们就可以开始寻找解决方案了。
装箱的一种方式是，优先选择内有总卡路里最高的食物的盒子，也就是重达800kg的一整盒土豆。
但是，这样做会导致大米和面粉无法被放进货运箱，而且它们两者的总卡路里远远超过你可以在剩余的200kg内放进的其他任何食物组合。按照这种策略，你可以获得的最高热量是1 749 400卡路里（选择土豆、草莓酱和花生酱）。
因此，看起来最自然的策略——贪心算法（greedy algorithm）[7]，会在每个步骤里选择目前最优的选项——并不能带来最好的结果。为了得到更好的答案，你需要再仔细考虑一下这个问题。
[7] 贪心算法是解决问题的一种策略，通过在每个步骤里做出局部最优选择来尝试找到最优解。贪心算法虽然只能针对一小类问题找到最佳解决方案，但是也可被用来作为获得近似（次优）解决方案的启发式算法。
是时候集思广益了。为此，你召集了整个物流团队一起寻找解决方案。
很快，有人建议应该查看每千克食物的平均卡路里而不是一整盒食物的总卡路里。于是，你为表1.1新添加了一列，并基于这一列中的值进行了相应的排序，如表1.2所示。
表1.2 将表1.1按照每千克食物的平均卡路里进行排序的结果
| 食物 |
重量/kg |
总卡路里/cal |
每千克食物的平均卡路里/cal |
|---|---|---|---|
| 花生酱 |
20 |
117 800 |
5890 |
| 大米 |
300 |
1 122 000 |
3740 |
| 面粉 |
400 |
1 444 000 |
3610 |
| 草莓酱 |
50 |
130 000 |
2600 |
| 豆类 |
300 |
690 000 |
2300 |
| 土豆 |
800 |
1 501 600 |
1877 |
| 番茄罐头 |
300 |
237 000 |
790 |
接下来，我们可以试着从上至下挑选单位重量卡路里最高的食物，最后得到包含花生酱、大米、面粉和草莓酱的组合——总共能提供2 813 800卡路里。
这比第一个结果要好很多。但是，稍加注意你就能发现，在选择花生酱之后，我们就不能再带上豆类了；而如果携带豆类的话，则还能进一步增加货运箱里食品的总热量。不过，至少你不用再被迫接受《火星救援》里的食物了，因为这次火星上没有土豆。
在进行若干小时的集思广益之后，你打算放弃寻找更好的解决方案了。你发现要解决这个问题，得到更优解决方案的唯一办法就是逐一检查每种食物以确定要不要携带。唯一能做到这一点的方法就是枚举出所有可能的解决方案，并剔除超出重量阈值的解决方案，然后从剩下的解决方案中挑选出最好的那个。这就是所谓的暴力（brute force）算法，是一种代价非常高昂的算法。
对于每种食物，你都可以选择是携带还是留下，因此可能的解决方案有27 = 128种。显然，你并不太愿意逐一尝试这100多种解决方案。几小时之后，你已经筋疲力尽，但也理解了为什么这种算法被称为暴力算法，并且至少解决了这个问题。
然后消息传开了。在收到一些未来定居者的投诉之后，任务控制部门打来了电话，告诉你清单里会额外增加25种新的食物，包括糖、橙子、大豆和马麦酱等。
看完你给出的计算组合，所有人都倍感沮丧，因为现在有大约40亿种不同的组合需要尝试。
显然，这时你需要一个计算机程序来帮助你实施计算，以得出最佳决策。
你会在接下来的几小时内编写相关的代码。但是，即使用上了计算机程序，你也需要花费很长的时间（若干小时）才能得到结果。紧接着，你发现自己的算法需要假设所有定居者的饮食习惯相同，但是实际上，其中的一部分人对某些食物过敏。比如，有25%的人不能吃麸质食物，还有更多的人声明他们对马麦酱过敏。因此，你必须根据不同人的过敏情况分别运行这个算法若干次。更糟的是，任务控制部门为了让有过敏反应的人也能吃得足够丰富，正在考虑为食品清单额外添加30种食物。如果真的决定了要这样做，那么我们最终会有62种食物可选，所编写的程序将不得不遍历超过数十亿种可能的组合。你尝试运行了一下这个程序，发现一天之后这个程序仍在运行，并且离得到结果还很远。
团队打算放弃找到最佳组合，回到吃土豆这个方案。这时，有人想起发射团队中某个人的桌子上有一本算法书。
你给发射团队打了电话，他们马上反馈这是一个0-1背包问题。坏消息是，0-1背包问题属于NP完全问题[8]，从而意味着这个问题很难解决，因为不会有“很快速的”（能在多项式时间内完成的）算法能计算出这个问题的最优解。
[8] NP完全（NP-complete）问题是这样一组问题，它们的任何解都可以被快速（在多项式时间内）验证，但尚不存在有效的方法能找到这个解。根据定义，NP完全问题无法在经典的确定型机器（例如我们将在第2章中定义的RAM模型）上，在多项式时间内得到答案。
不过好消息是，对于0-1背包问题，有一个伪多项式[9]解决方案。这是一种使用动态编程（dynamic programming）的解决方案[10]，所要花费的时间与背包的最大容量成正比。更好的办法是让货运箱的容量变得有限，于是这个解决方案需要执行的步骤数量就等于可能的填充容量乘以食物种类的数量。因此，假设最小单位是1kg，那么只需要执行1000 × 62步，就能得到答案了。这相比262这个数要好太多了！在重写算法之后，新算法在几秒内就能找到最佳解决方案。
[9] 对于伪多项式算法，最坏情况下的运行时间（多项式时间）还取决于输入的值，而不仅仅取决于输入的大小。例如，对于0-1背包问题，输入是n个元素（重量和值的组合），背包的容量为C。多项式算法的复杂度仅由元素的数量n决定，而伪多项式算法的复杂度还取决于（或者仅取决于）背包的容量C。
[10] 动态编程是一种解决具有某种特征的复杂问题的策略。这种特性是指，要计算出最终解决方案，就需要对子问题进行多次递归调用。这种策略会通过把问题分解为更简单的子问题的集合来得到最终解决方案，并且这些子问题的解决方案会被保存起来，从而保证只被计算或解决一次。
于是，你可以把这个算法当作一个黑盒，直接把它插入程序中而不用再关心更多的细节。但是，这一决择与你的职业发展密切相关，因此你还是应该对这个算法的工作原理进行更深入的了解。
对于最初的例子来说，明显可以找到的最佳组合是大米、面粉和豆类，总计3 256 000卡路里。与第一次尝试相比，这已经是一个非常好的结果了！
最初的例子其实很简单（只有7种食物），因此你可能直接猜到了最佳组合。如果是这样的话，你可以试着计算在面对更接近实际情况的上百种不同的食物时，需要多少年才能手动找到最佳解决方案！
这个解决方案已经很不错了，因为在各种限制下，这已经是我们能够找到的最佳解决方案了。
但是，真正的算法专家会怎么做呢？假设在准备环节，恰好有一位专家在航天基地访问，并且受邀帮助我们计算节省燃料的最佳路线。午休时，有人非常自豪地告诉专家你们如何出色地解决了打包食物的问题。专家随后问道：“为什么不把盒子拆开呢？”
答案可能是“从来没有拆开过盒子”，或是“这些食物在供应商那里已经打包好了，重新打包需要花费更多的时间和金钱”。
接下来，这位专家就会解释道：“如果我们可以把包装盒拆开，那么0-1背包问题（属于NP完全问题）就会变成无限制背包问题。通常来说，无限制背包问题的线性时间[11]的贪婪解决方案，甚至都要比0-1背包问题的最佳解决方案更好一些。”
[11] 线性时间需要假设食物列表是有序的，否则就会产生线性对数时间的复杂度。
简单来说，我们可以把这个问题转换为其他更容易解决的问题，从而使得打包在货运箱里的食物能提供尽可能多的卡路里。于是，问题就变成了“在可以对元素进行分割的情况下，从一个集合中选择任意数量的元素，使得它们的总重量不超过1000千克并且提供的热量最高。”
再者说，即使需要更多的花销来重新打包所有食物也是值得的，因为这样做能得到更好的结果。
具体来说，如果可以选择打包各种食物的一部分，就可以简单地从卡路里含量最高的食物（在本例中为花生酱）开始打包。当发现不能把一个盒子里的所有食物都打包进去时，只需要打包其中一部分以填满整个货运箱就行了。因此，最终重新打包所有食物甚至都不是必需的，只需重新打包一种食物就行了。
于是，最佳解决方案是打包花生酱、大米、面粉、草莓酱和230kg的豆类，共计3 342 800卡路里。
未来的火星定居者能够维持生存的能力还是不错的，也不会因为只吃土豆、花生酱和草莓酱而沮丧了。
从计算的角度看，我们从不正确的算法（采用最高总数和最高比例的贪婪解决方案），过渡到了正确但不可行的算法（枚举出所有可能组合的暴力解决方案），最后得到了一种非常灵活且更高效的解决方案。
同样重要甚至更重要的是，我们打破了常规来思考这个问题。我们通过删除一些约束条件简化了问题，进而找到一种更简单的算法和更好的解决方案。这个过程实际上是一条黄金法则，即“持续彻底地研究需求，思考是否需要它们，并且在可能的情况下尝试删除它们。”这些可能的情况包括：删除这些需求能够带来价值至少相同的解决方案，或者可以用更低的成本实现价值稍低的解决方案。当然在这个过程中，也有一些必须考虑的其他方面的问题（例如各个层面的法律和安全性），因此某些约束条件是不能删除的。
如前所述，在描述算法的过程中，接下来要做的是详细描述这个解决方案并给出实现方法的指南。
这里我们省略了0-1背包问题的动态规划算法的具体步骤。原因是：首先，这是一种算法，而不是数据结构；其次，这种算法在大量文献里都有相应的描述；最后，我们在本章中提到它，只是为了说明避免选择使用错误的算法和数据结构是多么重要，以及概述在第2章中介绍问题及其解决方案时所要遵循的过程。
● 算法应该基于输入和输出以及用来处理输入并产生预期输出的一系列指令来进行定义。
● 数据结构是抽象数据类型的具体实现，由保存数据的结构和一组操作这些数据的算法组成。
● 对问题进行抽象意味着创建清晰的问题陈述，然后讨论问题的解决方案。
● 合理且高效地收拾行囊可能会很困难（尤其是如果打算去火星的话）。但是，只要有算法和合适的数据结构，（几乎）没有什么是不可能的！
在这一部分，我们旨在为稍后即将讨论的更高级的内容奠定基础。我们将重点关注那些能为更基础的数据结构提供改进的高级数据结构。例如，其中会提到应该如何改进二叉堆（让树变得平衡），以及应该如何解决像跟踪一个或一组事物这样的问题。
这部分内容将通过各种示例来证明对数据进行操作的方法其实有很多种。开发人员需要明白，可以选择的最佳方法取决于上下文和需求。因此，我们需要查看需求、检查上下文，并在解决问题时学会质疑我们已掌握的知识，进而针对所面临的具体问题找到最佳解决方案。
第2章介绍二叉堆的高级变体d叉堆（d-way heap），以及这一部分剩余各章中用来介绍各种主题的编撰结构。
第3章通过树堆（treap）进一步探讨堆的高级用法。树堆是二叉搜索树和堆的混合体，可以在不同的上下文中为你提供帮助。
第4章将主题切换到了布隆过滤器（Bloom filter）。这是哈希表的一种高级形式，可在节省内存的同时，将查找操作的平摊时间复杂度维持在常数。
第5章介绍一些用来跟踪不交集（disjoint set）的替代数据结构。不交集是构建无数高级算法所必需的基石，已被用在若干实际的应用中。
第6章展示了两种在存储和查找字符串方面都优于通用容器的数据结构：trie以及被称为压缩前缀树的基数树。
第7章将基于前6章介绍的数据结构，构建一个能有效处理缓存的组合数据结构——LRU缓存（LRU-cache），还将详细讨论LRU缓存的变体——LFU缓存（LFU-cache），以及如何在多线程环境中同步共享容器的问题。
