学习JavaScript数据结构与算法（第3版）-洛伊安妮·格罗纳

元数据

学习JavaScript数据结构与算法（第3版）

• 
• 书名： 学习JavaScript数据结构与算法（第3版）
• 作者： 洛伊安妮·格罗纳
• 简介： 本书首先介绍了JavaScript语言的基础知识（包括ECMAScript和TypeScript），其次讨论了数组、栈、队列、双端队列和链表等重要的数据结构，随后分析了集合、字典和散列表的工作原理，接下来阐述了递归的原理、什么是树以及二叉堆和堆排序，然后介绍了图、DFS和BFS算法、各种排序（冒泡排序、选择排序、插入排序、归并排序、快速排序、计数排序、桶排序和基数排序）和搜索（顺序搜索、二分搜索和内插搜索）算法以及随机算法，接着介绍了分而治之、动态规划、贪心算法和回溯算法等高级算法以及函数式编程，最后还介绍了如何计算算法的复杂度。
• 出版时间 2019-05-20 00:00:00
• ISBN： 9787115510174
• 分类： 计算机-编程设计
• 出版社： 人民邮电出版社
• PC地址：https://weread.qq.com/web/reader/99732570718ff67e997e35b

高亮划线

2.1.2 使用Babel.js

📌 Babel是一个JavaScript转译器，也称为源代码编译器。它将使用了ECMAScript语言特性的JavaScript代码转换成只使用广泛支持的ES5特性的等价代码。 ⏱ 2020-07-03 20:18:08

2.2.1 用let替代var声明变量

📌 对于非对象类型的变量，比如数、布尔值甚至字符串，我们不可以改变变量的值。当遇到对象时，只读的const允许我们修改或重新赋值对象的属性，但变量本身的引用（内存中的引用地址）不可以修改，也就是不能对这个变量重新赋值。 ⏱ 2020-07-03 20:24:00

2.2.7 使用类进行面向对象编程

📌 只需要使用class关键字，声明一个有constructor函数和诸如printIsbn等其他函数的类。 ⏱ 2020-10-10 15:18:18

📌 要声明get和set函数，只需要在我们要暴露和使用的函数名前面加上get或set关键字（行{2}和行{3}）。我们可以用相同的名字声明类属性，或者在属性名前面加下划线（行{1}），让这个属性看起来像是私有的。 ⏱ 2020-10-10 15:25:12

📌 _name并非真正的私有属性， ⏱ 2020-10-10 15:25:40

2.2.9 模块

📌 暴露出了这两个函数 ⏱ 2020-07-03 20:49:31

📌 只有被导出的成员才对其他模块或文件可见。 ⏱ 2020-07-03 20:49:37

2.3 介绍TypeScript

📌 TypeScript是一个开源的、渐进式包含类型的JavaScript超集，由微软创建并维护。 ⏱ 2020-07-03 20:58:17

📌 让开发者增强JavaScript的能力并使应用的规模扩展变得更容易 ⏱ 2020-07-03 20:58:31

📌 为JavaScript变量提供类型支持 ⏱ 2020-07-03 20:59:13

2.3.1 类型推断

📌 TypeScript有一个类型推断机制，也就是说TypeScript会根据为变量赋的值自动给该变量设置一个类型。 ⏱ 2023-01-09 23:40:25

📌 如果声明了一个变量但没有设置其初始值，推荐为其设置一个类型 ⏱ 2020-10-10 16:16:35

2.3.2 接口

📌 第一种就像给变量设置一个类型，如下所示。 ⏱ 2020-12-16 16:28:55

📌 第二种TypeScript接口的概念和面向对象编程相关，与其他面向对象语言（如Java、C#和Ruby等）中的概念是一样的。 ⏱ 2020-12-16 16:29:02

📌 该接口的行为在JavaScript中并不存在，但它在进行一些工作（如开发排序算法）时非常有用。 ⏱ 2020-12-16 16:29:39

📌 另一个对数据结构和算法有用的强大TypeScript特性是泛型这一概念。我们修改一下Comparable接口， ⏱ 2020-12-16 16:29:45

3.3.1 在数组末尾插入元素

📌 还有一个push方法，能把元素添加到数组的末尾。通过push方法，我们能添加任意个元素。 ⏱ 2020-07-03 21:50:53

3.7.2 迭代器函数

📌 JavaScript内置了许多数组可用的迭代方法 ⏱ 2020-10-11 22:58:33

📌 假设数组中的值是从1到15；如果数组里的元素可以被2整除（偶数），函数就返回true，否则返回false ⏱ 2020-10-11 22:58:37

📌 every方法会迭代数组中的每个元素，直到返回false。 ⏱ 2020-10-11 23:01:02

📌 数组numbers的第一个元素是1，它不是2的倍数（1是奇数），因此isEven函数返回false，然后every执行结束。 ⏱ 2020-10-11 23:00:58

📌 它和every的行为相反，会迭代数组的每个元素，直到函数返回true。 ⏱ 2020-10-11 23:01:07

📌 如果要迭代整个数组，可以用forEach方法。它和使用for循环的结果相同 ⏱ 2020-10-11 23:01:12

📌 数组myMap里的值是：[false, true, false, true, false, true, false, true, false,true, false, true, false, true, false]。它保存了传入map方法的isEven函数的运行结果。 ⏱ 2020-10-12 15:57:21

📌 还有一个filter方法，它返回的新数组由使函数返回true的元素组成。 ⏱ 2020-10-12 15:57:34

3.7.4 排序元素

📌 在b大于a时，这段代码会返回负数，反之则返回正数。如果相等的话，就会返回0。也就是说返回的是负数，就说明a比b小，这样sort就能根据返回值的情况对数组进行排序。 ⏱ 2020-10-13 20:07:25

📌 我们声明了一个用来比较数组元素的函数，使数组按升序排序。 ⏱ 2020-10-13 20:07:34

📌 是根据字符对应的ASCII值来比较的 ⏱ 2020-10-12 18:44:05

3.7.5 搜索

📌 indexOf方法返回与参数匹配的第一个元素的索引；lastIndexOf返回与参数匹配的最后一个元素的索引。 ⏱ 2020-10-13 20:24:34

📌 find和findIndex方法接收一个回调函数，搜索一个满足回调函数条件的值。 ⏱ 2020-10-13 20:25:34

📌 如果数组里存在某个元素，includes方法会返回true，否则返回false。 ⏱ 2020-10-13 20:25:27

3.7.6 输出数组为字符串

📌 输出数组为字符串 ⏱ 2020-10-13 20:26:48

📌 现在，我们学习最后两个方法：toString和join。 ⏱ 2020-10-13 20:26:51

第4章 栈

📌 有两种类似于数组的数据结构在添加和删除元素时更为可控，它们就是栈和队列。 ⏱ 2020-10-13 20:39:18

4.2 栈数据结构

📌 栈是一种遵从后进先出（LIFO）原则的有序集合。 ⏱ 2020-10-13 20:39:45

4.3 创建一个基于JavaScript对象的Stack类

📌 创建一个Stack类最简单的方式是使用一个数组来存储其元素。在处理大量数据的时候（这在现实生活中的项目里很常见），我们同样需要评估如何操作数据是最高效的。在使用数组时，大部分方法的时间复杂度是O(n) ⏱ 2020-10-13 21:09:19

📌 O(n)的意思是，我们需要迭代整个数组直到找到要找的那个元素，在最坏的情况下需要迭代数组的所有位置，其中的n代表数组的长度。如果数组有更多元素的话，所需的时间会更长。另外，数组是元素的一个有序集合，为了保证元素排列有序，它会占用更多的内存空间。 ⏱ 2020-10-13 21:09:32

📌 如果我们能直接获取元素，占用较少的内存空间，并且仍然保证所有元素按照我们的需要排列，那不是更好吗？ ⏱ 2020-10-13 21:09:42

📌 对于使用JavaScript语言实现栈数据结构的场景，我们也可以使用一个JavaScript对象来存储所有的栈元素，保证它们的顺序并且遵循LIFO原则。我们来看看如何实现这样的行为。 ⏱ 2020-10-13 21:11:28

4.3.5 创建toString方法

📌 对于使用对象的版本，我们将创建一个toString方法来像数组一样打印出栈的内容。 ⏱ 2020-10-13 21:23:19

4.4 保护数据结构内部元素

📌 在创建别的开发者也可以使用的数据结构或对象时，我们希望保护内部的元素，只有我们暴露出的方法才能修改内部结构 ⏱ 2020-10-13 21:37:41

📌 对于Stack类来说，要确保元素只会被添加到栈顶，而不是栈底或其他任意位置（比如栈的中间）。 ⏱ 2020-10-13 21:37:45

4.4.1 下划线命名约定

📌 一部分开发者喜欢在JavaScript中使用下划线命名约定来标记一个属性为私有属性。 ⏱ 2020-10-13 21:42:26

📌 不过这种方式只是一种约定，并不能保护数据，而且只能依赖于使用我们代码的开发者所具备的常识。 ⏱ 2020-10-13 21:42:30

4.4.2 用ES2015的限定作用域Symbol实现类

📌 ES2015新增了一种叫作Symbol的基本类型，它是不可变的，可以用作对象的属性。 ⏱ 2020-10-13 21:44:18

📌 这种方法创建了一个假的私有属性，因为ES2015新增的Object.getOwnProperty-Symbols方法能够取到类里面声明的所有Symbols属性 ⏱ 2020-10-13 21:53:23

📌 并且，_items属性是一个数组，可以进行任意的数组操作，比如从中间删除或添加元素（使用对象进行存储也是一样的）。但我们操作的是栈，不应该出现这种行为。 ⏱ 2020-10-13 21:54:45

4.4.3 用ES2015的WeakMap实现类

📌 有一种数据类型可以确保属性是私有的，这就是WeakMap ⏱ 2020-10-13 21:55:48

📌 WeakMap可以存储键值对，其中键是对象，值可以是任意数据类型。 ⏱ 2020-10-22 11:31:15

4.4.4 ECMAScript类属性提案

📌 TypeScript提供了一个给类属性和方法使用的private修饰符。然而，该修饰符只在编译时有用 ⏱ 2020-10-22 11:45:43

4.5 用栈解决问题

📌 要把十进制转化成二进制，我们可以将该十进制数除以2（二进制是满二进一）并对商取整，直到结果是0为止。 ⏱ 2020-10-22 11:55:49

5.1 队列数据结构

📌 队列是遵循先进先出（FIFO，也称为先来先服务）原则的一组有序的项。队列在尾部添加新元素，并从顶部移除元素。最新添加的元素必须排在队列的末尾 ⏱ 2020-10-22 14:55:22

5.1.1 创建队列

📌 为了写出一个在获取元素时更高效的数据结构，我们将使用一个对象来存储我们的元素 ⏱ 2020-10-22 15:15:50

📌 你会发现Queue类和Stack类非常类似，只是添加和移除元素的原则不同。 ⏱ 2020-10-22 15:14:47

📌 此外，由于我们将要从队列前端移除元素，同样需要一个变量来帮助我们追踪第一个元素。 ⏱ 2020-10-22 15:15:37

📌 此处一个非常重要的细节是新的项只能添加到队列末尾。 ⏱ 2020-10-22 15:33:13

5.2 双端队列数据结构

📌 由于双端队列同时遵守了先进先出和后进先出原则，可以说它是把队列和栈相结合的一种数据结构。 ⏱ 2020-10-22 15:35:08

5.2.1 创建Deque类

📌 我们可以设置一个负值的键，同时更新用于计算双端队列长度的逻辑，使其也能包含负键值。这种情况下，添加一个新元素的操作仍然能保持最低的计算成本 ⏱ 2020-10-22 15:35:54

5.3.1 循环队列——击鼓传花游戏

📌 这其中的一种叫作循环队列。循环队列的一个例子就是击鼓传花游戏（hot potato） ⏱ 2020-10-22 16:02:45

5.3.2 回文检查器

📌 同时移除所有的空格 ⏱ 2020-10-22 16:50:27

5.3.3 JavaScript任务队列

📌 当我们在浏览器中打开新标签时，就会创建一个任务队列。这是因为每个标签都是单线程处理所有的任务，称为事件循环。 ⏱ 2020-10-22 16:53:22

第6章 链表

📌 你会学习如何实现和使用链表这种动态的数据结构，这意味着我们可以从中随意添加或移除项，它会按需进行扩容。 ⏱ 2020-10-22 17:36:30

6.1 链表数据结构

📌 相对于传统的数组，链表的一个好处在于，添加或移除元素的时候不需要移动其他元素。 ⏱ 2020-10-22 17:41:34

📌 在数组中，我们可以直接访问任何位置的任何元素，而要想访问链表中间的一个元素，则需要从起点（表头）开始迭代链表直到找到所需的元素。 ⏱ 2020-10-22 17:42:41

📌 JavaScript还不支持真正的私有属性， ⏱ 2020-10-22 18:32:27

6.3 循环链表

📌 循环链表可以像链表一样只有单向引用，也可以像双向链表一样有双向引用 ⏱ 2020-10-23 11:59:05

6.3.1 在任意位置插入新元素

📌 不同之处在于我们需要将循环链表尾部节点的next引用指向头部节点 ⏱ 2020-10-23 11:59:18

6.4 有序链表

📌 有序链表是指保持元素有序的链表结构。除了使用排序算法之外，我们还可以将元素插入到正确的位置来保证链表的有序性。 ⏱ 2020-10-23 14:11:15

6.5 创建StackLinkedList类

📌 之所以使用双向链表而不是链表，是因为对栈来说，我们会向链表尾部添加元素（行{2}），也会从链表尾部移除元素（行{3}）。 ⏱ 2020-10-24 10:13:55

6.6 小结

📌 你还学习了链表相比数组最重要的优点，那就是无须移动链表中的元素，就能轻松地添加和移除元素。 ⏱ 2020-10-24 10:14:35

📌 当你需要添加和移除很多元素时，最好的选择就是链表，而非数组。 ⏱ 2020-10-24 10:14:40

📌 这是一种存储唯一元素的数据结构。 ⏱ 2020-10-24 10:14:54

7.2 创建集合类

📌 我们使用对象而不是数组来表示集合（items）。 ⏱ 2020-10-24 10:16:18

📌 JavaScript的对象不允许一个键指向两个不同的属性，也保证了集合里的元素都是唯一的。 ⏱ 2020-10-24 10:16:25

7.2.1 has(element)方法

📌 Object原型有hasOwnProperty方法。该方法返回一个表明对象是否具有特定属性的布尔值。in运算符则返回表示对象在原型链上是否有特定属性的布尔值。 ⏱ 2020-10-24 10:17:38

📌 Object.prototype.hasOwnProperty.call ⏱ 2020-10-24 10:17:47

7.2.5 values方法

📌 Object.values()方法返回了一个包含给定对象所有属性值的数组 ⏱ 2020-10-24 10:44:37

7.3 集合运算

📌 集合是数学中基础的概念，在计算机领域也非常重要。它在计算机科学中的主要应用之一是数据库，而数据库是大多数应用程序的根基。 ⏱ 2020-10-24 10:45:19

7.3.2 交集

📌 迭代较小集合（行{7}）来计算出两个集合的共有元素并返回。 ⏱ 2020-10-24 10:56:38

7.4 ECMAScript 2015——Set类

📌 ES2015的Set的values方法返回Iterator（第3章提到过），而不是值构成的数组 ⏱ 2020-10-24 10:58:55

📌 扩展运算符 ⏱ 2020-10-24 11:05:43

📌 有一种计算并集、交集和差集的简便方法，就是使用扩展运算符，它包含在ES2015中， ⏱ 2020-10-24 11:06:32

📌 整个过程包含三个步骤：(1) 将集合转化为数组；(2) 执行需要的运算；(3) 将结果转化回集合。 ⏱ 2020-10-24 11:07:07

📌 并集 ⏱ 2020-10-24 11:07:22

📌 那么我们对setA使用扩展运算符（…setA）会将它的值转化为一个数组（展开它的值），然后对setB也这样做。 ⏱ 2020-10-24 11:07:30

📌 在本示例中验证了元素是否也存在于setB中。返回的数组会用来初始化结果集合。 ⏱ 2020-10-24 11:09:26

8.1.1 创建字典类

📌 我们将要存储的是[键，值]对。 ⏱ 2020-10-24 11:31:21

📌 在字典中，理想的情况是用字符串作为键名，值可以是任何类型（从数、字符串等原始类型，到复杂的对象） ⏱ 2020-10-24 11:32:18

8.2 散列表

📌 散列算法的作用是尽可能快地在数据结构中找到一个值 ⏱ 2020-12-16 11:43:32

8.2.4 处理散列表中的冲突

📌 有时候，一些键会有相同的散列值。不同的值在散列表中对应相同位置的时候，我们称其为冲突 ⏱ 2020-11-08 21:53:09

📌 使用一个数据结构来保存数据的目的显然不是丢失这些数据，而是通过某种方法将它们全部保存起来。因此，当这种情况发生的时候就要去解决。处理冲突有几种方法：分离链接、线性探查和双散列法。在本书中，我们会介绍前两种方法。 ⏱ 2020-11-08 21:54:04

📌 分离链接法包括为散列表的每一个位置创建一个链表并将元素存储在里面。它是解决冲突的最简单的方法，但是在HashTable实例之外还需要额外的存储空间。 ⏱ 2020-11-08 21:57:16

📌 我们在之前的测试代码中使用分离链接并用图表示的话，输出结果将会是如下这样 ⏱ 2020-11-08 21:56:25

📌 当想向表中某个位置添加一个新元素的时候，如果索引为position的位置已经被占据了，就尝试position+1的位置。如果position+1的位置也被占据了，就尝试position+2的位置，以此类推，直到在散列表中找到一个空闲的位置 ⏱ 2020-11-08 22:19:22

8.2.5 创建更好的散列函数

📌 插入和检索元素的时间（即性能），以及较低的冲突可能性 ⏱ 2020-12-16 11:59:41

📌 djb2HashCode方法包括初始化一个hash变量并赋值为一个质数（行{2}——大多数实现都使用5381 ⏱ 2020-12-16 12:00:15

9.1 理解递归

📌 递归是一种解决问题的方法，它从解决问题的各个小部分开始，直到解决最初的大问题。递归通常涉及函数调用自身。 ⏱ 2020-11-08 22:46:13

📌 因此，每个递归函数都必须有基线条件，即一个不再递归调用的条件（停止点），以防止无限递归。 ⏱ 2020-11-08 22:46:30

9.3.3 记忆化斐波那契数

📌 还有第三种写fibonacci函数的方法，叫作记忆化。记忆化是一种保存前一个结果的值的优化技术，类似于缓存。 ⏱ 2020-11-08 23:11:43

📌 在上面的代码中，我们声明了一个memo数组来缓存所有的计算结 ⏱ 2020-11-08 23:12:01

第10章 树

📌 它对于存储需要快速查找的数据非常有用。 ⏱ 2020-11-13 09:56:19

10.2 树的相关术语

📌 位于树顶部的节点叫作根节点（11）。它没有父节点。树中的每个元素都叫作节点，节点分为内部节点和外部节点。至少有一个子节点的节点称为内部节点（7、5、9、15、13和20是内部节点）。没有子元素的节点称为外部节点或叶节点（3、6、8、10、12、14、18和25是叶节点）。 ⏱ 2020-11-13 10:00:01

📌 节点的一个属性是深度，节点的深度取决于它的祖先节点的数量。比如，节点3有3个祖先节点（5、7和11），它的深度为3。 ⏱ 2020-11-09 12:00:59

📌 树的高度取决于所有节点深度的最大值 ⏱ 2020-11-09 12:00:48

10.3 二叉树和二叉搜索树

📌 二叉树中的节点最多只能有两个子节点：一个是左侧子节点，另一个是右侧子节点。 ⏱ 2020-11-13 10:04:22

📌 二叉搜索树（BST）是二叉树的一种，但是只允许你在左侧节点存储（比父节点）小的值，在右侧节点存储（比父节点）大的值。上一节的图中就展现了一棵二叉搜索树。 ⏱ 2020-11-09 12:01:57

10.3.1 创建BinarySearchTree类

📌 和链表一样，我们将通过指针（引用）来表示节点之间的关系（树相关的术语称其为边）。 ⏱ 2020-11-13 10:08:34

📌 对于树，使用同样的方式（也使用两个指针），但是一个指向左侧子节点，另一个指向右侧子节点 ⏱ 2020-11-13 10:08:41

📌 不同于在之前的章节中将节点本身称作节点或项，我们将会称其为键（行{1}）。键是树相关的术语中对节点的称呼。 ⏱ 2020-11-13 10:08:52

📌 在树中，它不再是head，而是root（行{1}）。 ⏱ 2020-11-13 10:09:48

10.3.2 向二叉搜索树中插入一个键

📌 注意在这里，由于键可能是复杂的对象而不是数，我们使用传入二叉搜索树构造函数的compareFn函数来比较值。 ⏱ 2020-11-13 10:35:25

10.4 树的遍历

📌 访问树的所有节点有三种方式：中序、先序和后序。 ⏱ 2020-11-13 10:40:58

10.4.1 中序遍历

📌 inOrderTraverse方法接收一个回调函数作为参数。回调函数用来定义我们对遍历到的每个节点进行的操作 ⏱ 2020-11-13 10:42:49

📌 首先要检查以参数形式传入的节点是否为null（行{2}——这就是停止递归继续执行的判断条件，即递归算法的基线条件）。 ⏱ 2020-12-16 14:56:45

10.4.2 先序遍历

📌 先序遍历是以优先于后代节点的顺序访问每个节点的 ⏱ 2020-11-13 11:17:36

📌 先序遍历会先访问节点本身（行{1}），然后再访问它的左侧子节点（行{2}），最后是右侧子节点（行{3}），而中序遍历的执行顺序是：{2}、{1}和{3}。 ⏱ 2020-11-13 11:17:56

10.4.3 后序遍历

📌 后序遍历的一种应用是计算一个目录及其子目录中所有文件所占空间的大小。 ⏱ 2020-11-13 11:25:15

10.5.3 移除一个节点

📌 如果我们找到了要找的键（键和node.key相等），就需要处理三种不同的情况。 ⏱ 2020-11-12 18:22:53

📌 ，但是它有一个父节点，需要通过返回null来将对应的父节点指针赋予null值（行{11}） ⏱ 2020-11-12 18:23:06

📌 父节点总是会接收到函数的返回值。 ⏱ 2020-11-12 18:23:33

📌 移除有一个左侧或右侧子节点的节点 ⏱ 2020-11-12 18:24:57

📌 这种情况下，需要跳过这个节点，直接将父节点指向它的指针指向子节点。 ⏱ 2020-11-12 18:25:02

📌 当找到了要移除的节点后，需要找到它右边子树中最小的节点（它的继承者——行{18}）。 ⏱ 2020-11-12 18:28:07

📌 用它右侧子树中最小节点的键去更新这个节点的值（行{19} ⏱ 2020-11-12 18:28:13

10.6.1 Adelson-Velskii-Landi树（AVL树）

📌 AVL树是一种自平衡树。添加或移除节点时，AVL树会尝试保持自平衡 ⏱ 2020-11-13 11:56:55

📌 任意一个节点（不论深度）的左子树和右子树高度最多相差1。添加或移除节点时，AVL树会尽可能尝试转换为完全树。 ⏱ 2020-11-13 11:57:00

📌 在AVL树中插入或移除节点和BST完全相同。然而，AVL树的不同之处在于我们需要检验它的平衡因子，如果有需要，会将其逻辑应用于树的自平衡。 ⏱ 2020-11-13 11:57:57

📌 节点的高度是从节点到其任意子节点的边的最大值。 ⏱ 2020-11-13 11:58:10

📌 ，需要对每个节点计算右子树高度（hr）和左子树高度（hl）之间的差值，该值（hr－hl）应为0、1或-1。 ⏱ 2020-11-13 12:00:04

第11章 二叉堆和堆排序

📌 我们将要学习一种特殊的二叉树，也就是堆数据结构，也叫作二叉堆 ⏱ 2020-11-17 11:29:56

11.1 二叉堆数据结构

📌 它是一棵完全二叉树，表示树的每一层都有左侧和右侧子节点（除了最后一层的叶节点），并且最后一层的叶节点尽可能都是左侧子节点，这叫作结构特性。 ⏱ 2020-11-17 19:32:00

📌 二叉堆不是最小堆就是最大堆。最小堆允许你快速导出树的最小值，最大堆允许你快速导出树的最大值。所有的节点都大于等于（最大堆）或小于等于（最小堆）每个它的子节点。这叫作堆特性。 ⏱ 2020-11-17 19:32:08

📌 尽管二叉堆是二叉树，但并不一定是二叉搜索树（BST ⏱ 2020-11-17 19:32:20

11.1.1 创建最小堆类

📌 第二种是使用一个数组，通过索引值检索父节点、左侧和右侧子节点的值 ⏱ 2020-11-17 19:47:38

📌 ❑ 它的左侧子节点的位置是2 * index+1（如果位置可用）；❑ 它的右侧子节点的位置是2 * index+2（如果位置可用）；❑ 它的父节点位置是index / 2（如果位置可用）。 ⏱ 2020-11-17 19:47:46

📌 表示我们将要将这个值和它的父节点进行交换，直到父节点小于这个插入的值。 ⏱ 2020-11-17 19:48:27

📌 有一个公开的问题表示解构操作比正常的赋值操作性能更差。 ⏱ 2020-11-18 20:22:53

📌 在最小堆中，最小值总是位于数组的第一个位置（堆的根节点） ⏱ 2020-11-18 20:23:49

📌 在移除后，我们将堆的最后一个元素移动至根部并执行siftDown函数，表示我们将交换元素直到堆的结构正常。 ⏱ 2020-11-18 20:25:46

📌 下移操作表示将元素和最小子节点（最小堆）和最大子节点（最大堆）进行交换 ⏱ 2020-11-18 20:26:24

📌 我们要检验它的值是否和element相同（传入siftDown方法——行{7}）——和自己交换是没有意义的！如果不是，就将它和最小的element交换（行{8}），并且重复这个过程（行{9}）直到element被放在正确的位置上。 ⏱ 2020-11-18 20:26:30

11.2 堆排序算法

📌 (1) 用数组创建一个最大堆用作源数据。 ⏱ 2020-11-18 19:15:56

📌 最大的值会被存储在堆的第一个位置。我们要将它替换为堆的最后一个值 ⏱ 2020-11-18 20:29:00

📌 最后，我们将堆的根节点下移并重复步骤2直到堆的大小为1。 ⏱ 2020-11-18 20:29:13

📌 堆排序算法不是一个稳定的排序算法，也就是说如果数组没有排好序，可能会得到不一样的结果。 ⏱ 2020-11-18 20:29:41

12.1 图的相关术语

📌 一个图G=(V, E)由以下元素组成。❑ V：一组顶点❑ E：一组边，连接V中的顶点 ⏱ 2020-11-18 20:30:24

12.2.1 邻接矩阵

📌 不是强连通的图（稀疏图）如果用邻接矩阵来表示，则矩阵中将会有很多0，这意味着我们浪费了计算机存储空间来表示根本不存在的边。 ⏱ 2020-11-18 20:34:58

12.2.2 邻接表

📌 我们也可以使用一种叫作邻接表的动态数据结构来表示图。 ⏱ 2020-11-18 20:35:31

12.2.3 关联矩阵

📌 关联矩阵通常用于边的数量比顶点多的情况，以节省空间和内存 ⏱ 2020-11-18 20:45:50

12.4 图的遍历

📌 有两种算法可以对图进行遍历：广度优先搜索（breadth-first search, BFS）和深度优先搜索（depth-firstsearch, DFS）。 ⏱ 2020-11-20 14:03:45

📌 图遍历算法的思想是必须追踪每个第一次访问的节点，并且追踪有哪些节点还没有被完全探索。对于两种图遍历算法，都需要明确指出第一个被访问的顶点。 ⏱ 2020-11-20 14:04:49

12.4.1 广度优先搜索

📌 广度优先搜索算法会从指定的第一个顶点开始遍历图，先访问其所有的邻点（相邻顶点），就像一次访问图的一层。 ⏱ 2020-11-20 14:06:38

📌 给定一个图G和源顶点v，找出每个顶点u和v之间最短路径的距离（以边的数量计）。 ⏱ 2020-11-20 14:07:08

读书笔记

本书评论

书评 No.1

⏱ 2021-01-28 16:38:34