为什么要使用PQ？我们学到的最后一个 ADT 是二叉搜索树，它使我们能够高效搜索，只需要 logN 时间。这是因为我们可以在搜索的每一步中剔除一半的元素。如果我们更关心快速找到最小或最大元素而不是快速搜索怎么办？ 同时，二叉树中，我们不允许存在两个具有相同的值的情况重新，因此就有了PQ。 优先级队列接口要理解这个抽象数据类型，请考虑一袋物品。您可以向这个袋子中添加物品，也可以从中移除物品等等。唯一的限制是您只能与这个袋子中的最小的物品进行交互。 123456789101112/** (Min) Priority Queue: Allowing tracking and removal of * the smallest item in a priority queue. */public interface MinPQ<Item> { /** Adds the item to the priority queue. */ public void add(Item x); /** Returns the smallest item in the ...

本文由GPT翻译，原文链接为: 原文 数学天花板：你的认知瓶颈在哪里？本·奥林 思考 2015年4月8日 4分钟 某天下午，我的系主任在教职工休息室里碰到了我，提出了一个发人深思的问题。 （他后来承认，他只是好奇是否能够在这个博客上玩傀儡。答案是一个响亮的“是的”：我像一个傀儡一样跳舞。） 那么，我们有天花板吗？ 传统的正统说：“绝对有。”有高智商和低智商。有“数学人”和“非数学人”。有些孩子就是“懂得了”；而其他人则不是。 试着问问成年人有关他们的数学教育：他们把它看作是某种NCAA锦标赛。每个人都会被淘汰，问题只是你能在游戏中坚持多久。“我处理不了代数”意味着第一轮的淘汰。“我在多元微积分停下了”意味着“嘿，我没赢，但我为进入最后四强而自豪。” 但是教师们中间有一个新的正统观念，那就是“绝对没有”。 你得欣赏这种乐观主义，这种大众主义。（看看你椅子下面——每个人都得到了一本范畴论教材！）但我认为你也得像我的朋友Karen一样怀疑。 Karen，我们有天花板吗？ Karen很努力。Karen会问问题。Karen相信自己。但Karen仍然觉得某些数学超出了她的能 ...

目前的问题到目前为止，我们已经了解了一些数据结构，以便有效地搜索数据结构中是否存在项目。我们研究了二叉搜索树，然后使用 2-3 棵树使它们平衡。 然而，这些结构存在一些限制（是的，甚至是 2-3 棵树） 他们要求项目具有可比性。您如何决定新项目在 BST 中的位置？你必须回答“你比根小还是大”的问题？对于某些对象来说，这个问题可能没有意义。 它们给出的复杂度为 Θ(logN) 。这个好吗？绝对地。但也许我们可以做得更好。 第一次尝试： DataIndexedIntegerSet目前，我们只尝试改进上面的问题#2（将复杂性从 Θ(logN) 提高到 Θ(1) 。我们不会担心问题#1（可比性）事实上，我们只会考虑存储和搜索 int 。 这里有一个想法：让我们创建一个类型为 boolean 且大小为 20 亿的 ArrayList。让一切默认为假。 add(int x) 方法只是将 ArrayList 中的 x 位置设置为 true。这需要 Θ(1)Θ(1) 时间。 contains(int x) 方法只是返回 ArrayList 中的 x 位置是 true 还是 false 。这 ...

Reading: 11. 平衡树 ·拥抱61B — 11. Balanced Trees · Hug61B (gitbooks.io) 当我们随机插入 BST 时，平均深度和高度预计为Θ(*logN*) . 但是，我们并不总是能够以随机顺序插入 BST。如果我们的数据是实时的呢？然后，我们将被迫按照数据到达我们的顺序进行插入。 下面我们将了解一棵始终保持平衡的树！ B-trees / 2-3 trees / 2-3-4 treescs61b 2019 lec17 ds3 2-3 trees, 2-3-4 trees - Google 幻灯片 BST 的问题在于我们总是插入叶节点。这就是导致高度增加的原因。 当我们开始插入节点时，我们可能会破坏平衡结构。所以，让我们想出一种方法，在添加新节点时保持树的平衡！ 疯狂的想法：我们永远不要添加叶子节点！当我们插入时，让我们只添加到当前的叶节点。这样，高度永远不会增加。 但是，您能看到这种插入方案的潜在问题吗？如果我们搜索 19，那么我们将向下遍历到包含它的节点，我们仍然必须像查看数组一样查看该节点才能到达 19 元素。这 ...

Lab 7: BSTMap | CS 61B Spring 2021 (datastructur.es) 创建一个 BSTMap 类，它使用 BST（二叉搜索树）作为其核心数据结构来实现 Map61B 接口。您必须在名为 BSTMap.java 的文件中执行此操作。您的实现需要实现 Map61B 中给出的所有方法，但 remove 、 iterator 和 keySet 除外。对于这些方法，您应该抛出一个 UnsupportedOperationException 在创建 BSTMap 类并实现 Map61B 的所有方法之前，您的代码不会编译。您可以一次实现一个方法，方法是编写所有必需方法的方法签名，但为实现抛出 UnsupportedOperationExceptions ，直到您真正开始编写它们。 您的 BSTMap 还应该添加一个附加方法 printInOrder() （Map61B 接口中未给出），该方法按 Key 递增的顺序打印出 BSTMap。我们不会测试此方法的结果，但您会发现这对测试您的实现很有帮助！ 资源 Lecture 16 slides. 讲座 16 幻灯片。 ...

Slides:cs61b 2020 lec16 ds2 adts, sets, maps, binary search trees - Google 幻灯片 Reading:10.2 Trees · Hug61B (gitbooks.io) ADTs 抽象数据类型（ADT）仅通过其操作进行定义，而不是通过其实现。 这意味着ADT定义了一组操作或行为，而不涉及具体的实现细节。 例如，在proj1a中，我们开发了一个ArrayDeque和一个LinkedListDeque，它们具有相同的方法，但这些方法的编写方式非常不同。在这种情况下，我们说ArrayDeque和LinkedListDeque是Deque ADT的实现。从这个描述中，我们可以看出ADT和接口在某种程度上是相关的。 ADT强调的是数据和操作的抽象描述，而接口强调的是行为和操作的规范定义。 在概念上，Deque是一个接口，ArrayDeque和LinkedListDeque是其实现。在代码中，为了表达这种关系，我们让ArrayDeque和LinkedListDeque类从Deque接口继承。 一些常用的ADT包括 ...

slide:cs61b 2020 lec14 ds1 disjoint sets - Google 幻灯片 Reading:9.1 Introduction · Hug61B (gitbooks.io) code:Case Study: Union-Find (princeton.edu) Disjoint Sets简介如果两个集合没有共同元素，则称它们为不相交集合。一个不相交集合（或者称为并查集）数据结构用于追踪固定数量的元素，这些元素被划分为多个不相交集合。该数据结构具有两个操作： connect(x, y): 连接 x 和 y。也称为 union。 isConnected(x, y): 如果 x 和 y 连接（即属于同一集合），则返回true。 不相交集合数据结构有一定数量的元素，每个元素最初都位于自己的子集中。通过对某些元素 x 和 y 调用 connect(x, y)，我们可以将子集合并在一起。 例如，假设我们有四个元素，我们将它们称为 A、B、C、D。初始时，每个元素都在自己的集合中： 调用 connect(A, B) 后： 请注意，子集 A 和 B 被合并。让我们 ...

高效编程效率有两种形式： 1.） 编程成本。 开发您的程序需要多长时间？ 读取、修改和维护代码的难易程度如何？ 2.） 执行成本（从下周开始）。 您的程序需要多少时间才能执行？ 您的程序需要多少内存？ 61B 中讨论了一些有用的 Java 特性： 包（Packages） 优点：组织，使事物成为包私有。 缺点：过于具体。 静态类型检查（Static type checking）。 优点：早期检查错误，更像是一篇故事。 缺点：不够灵活，（强制转换等） 继承（Inheritance） 优点：代码重用。 缺点： “Is a”，，调试路径变得烦人，不能实例化，要实现接口的每个方法。 封装首先，我们将定义一些术语： 模块：一组方法，作为整体一起执行某个任务或一组相关任务。 封装的：如果模块的实现完全隐藏，只能通过文档化的接口访问，则称其为封装的。 API（应用程序编程接口）ADT（抽象数据结构）的API是构造函数和方法列表以及每个方法的简短描述。 API由语法和语义规范组成。 编译器验证是否符合语法。 也就是说，API中指定的一切都存在。 测试有助于验证语 ...