数据结构部分

来源地址

一数据结构

在这里插入图片描述

1 堆和树之间的区别

区别就在于树是没有特定顺序的，你需要遍历整个树才能找到特定元素；而堆是有序的，你可以直接找到最大（或最小）的元素。

堆：假设你正在开发一个任务调度系统，需要根据任务的优先级进行调度。你可以使用一个最小堆来实现任务队列，将任务按照优先级插入到堆中，并始终保持最小优先级的任务在堆顶部。这样，每次从堆顶部取出任务时，你总是能够获取到当前最高优先级的任务进行处理。

树结构：计算机的文件系统通常被组织成树状结构。根目录是整个文件系统的起点，每个文件夹可以包含子文件夹和文件，从而形成层次结构。

2 所有数据结构都是基于数组、链表或二者的组合实现的

基于数组实现的数据结构也称“静态数据结构”，这意味着此类数据结构在初始化后长度不可变。相对应地，基于链表实现的数据结构也称“动态数据结构”，这类数据结构在初始化后，仍可以在程序运行过程中对其长度进行调整。
在这里插入图片描述

3 基本数据类型

就是整数，浮点，字符，布尔类型：基本数据类型以二进制的形式存储在计算机中。一个二进制位即为 1 比特。在绝大多数现代操作系统中，1 字节（byte）由 8 比特（bit）组成。

基本数据类型提供了数据的“内容类型”，而数据结构提供了数据的“组织方式”。例如以下代码，我们用相同的数据结构（数组）来存储与表示不同的基本数据类型，包括 int、float、char、bool 等。

4 列表=“动态数组”

在这里插入图片描述

5 双向队列

在队列中，我们仅能删除头部元素或在尾部添加元素。如图 5-7 所示，「双向队列 double-ended queue」提供了更高的灵活性，允许在头部和尾部执行元素的添加或删除操作。
在这里插入图片描述

双向列表的应用

我们知道，软件的“撤销”功能通常使用栈来实现：系统将每次更改操作 push 到栈中，然后通过 pop 实现撤销。然而，考虑到系统资源的限制，软件通常会限制撤销的步数（例如仅允许保存 50 步）。当栈的长度超过 50 时，软件需要在栈底（队首）执行删除操作。但栈无法实现该功能，此时就需要使用双向队列来替代栈。请注意，“撤销”的核心逻辑仍然遵循栈的先入后出原则，只是双向队列能够更加灵活地实现一些额外逻辑。

6 哈希表 = 散列表

我们向哈希表中输入一个键 key ，则可以在 O(1) 时间内获取对应的值 value，实现高效的元素查询
在这里插入图片描述

1）哈希表的简单实现，仅用数组

![在这里插入图片描述](https://img-blog.csdnimg.cn/direct/02f9cb
在哈希算法中，将哈希值对桶数量（数组的长度）capacity 取模，是为了确定该 key 在数组中的索引位置。

取模运算是一种数学运算，它计算某个数除以另一个数的余数。在这个场景中，我们使用取模运算是为了将哈希值映射到数组的有效范围内。

作用如下：

均匀分布：通过取模运算，我们可以将哈希值均匀地映射到桶数组的各个索引位置上。这样可以避免将大部分数据集中在某几个桶中，提高散列的均匀性。
确定索引位置：取模运算得到的结果就是一个具体的索引位置，在数组中可以直接通过该索引访问或存储元素。这样可以快速定位到对应的桶，提高查找、插入、删除等操作的效率。

举个例子来说明：
假设有一个桶数组，长度为10（即capacity=10），而某个 key 经过哈希函数计算后得到的哈希值为 27。如果我们直接将哈希值作为索引，那么该 key 对应的索引位置就超出了数组的长度。但如果我们对容量取模（27 % 10），则得到的结果为 7，表示该 key 应该放在数组的第 7 个位置上。

所以，对容量取模可以将哈希值映射到合适的索引位置，确保数据分布均匀且能够准确定位到对应的桶。

2）哈希冲突

两key对应一个值了，这时候就需要扩容哈希表
「负载因子 load factor」是哈希表的一个重要概念，其定义为哈希表的元素数量除以桶数量，用于衡量哈希冲突的严重程度，也常作为哈希表扩容的触发条件。例如在 Java 中，当负载因子超过 0.75时，系统会将哈希表扩容至原先的 2倍。

哈希表的存储可能如下所示：
桶1: 空
桶2: 学生A, 85
桶3: 学生B, 92
桶4: 空
桶5: 学生C, 78
桶6: 空
桶7: 空
桶8: 空
桶9: 空
桶10: 空

哈希冲突会导致查询结果错误，严重影响哈希表的可用性。为了解决该问题，每当遇到哈希冲突时，我们就进行哈希表扩容，直至冲突消失为止。此方法简单粗暴且有效，但效率太低，因为哈希表扩容需要进行大量的数据搬运与哈希值计算。为了提升效率，我们可以采用以下策略。

1、改良哈希表数据结构，使得哈希表可以在出现哈希冲突时正常工作。
2、仅在必要时，即当哈希冲突比较严重时，才执行扩容操作。
哈希表的结构改良方法主要包括“链式地址”和“开放寻址”。
在这里插入图片描述
开放寻址有三法

7 树

二叉树的基本单元是节点，每个节点（父节点）包含值、左子节点引用（指针）和右子节点引用。
![在这里插入图片描述](https://img-blog.csdnimg.cn/direct/683af95cb49f4463aa2e7a1ac4147077.png
插入和删除节点

遍历

在这里插入图片描述
前序遍历首先访问根节点，然后递归地遍历左子树和右子树
中序遍历先遍历左子树，然后访问根节点，最后遍历右子树
后序遍历先遍历左子树，然后遍历右子树，最后访问根节点

二叉搜索树

在这里插入图片描述

查找节点

从二叉树的根节点 root 出发，循环比较节点值 cur.val 和 num 之间的大小关系。

插入节点

也是先查找能插入节点的位置

删

在这里插入图片描述

AVL树

在这里插入图片描述

AVL树是一种自平衡二叉搜索树，它解决了普通二叉搜索树可能出现的性能问题。普通二叉搜索树在插入、删除操作频繁时，可能会变得不平衡，导致查找、插入、删除等操作的时间复杂度从O(logn)退化到O(n)，严重影响了性能。

AVL树通过引入平衡因子（balance factor）来保持树的平衡状态。每个节点都有一个平衡因子，用来表示左子树和右子树的高度差。平衡因子可以为-1、0或1。当插入或删除节点后，AVL树会通过旋转操作，即左旋和右旋，来重新调整树的结构，使得每个节点的平衡因子保持在[-1, 0, 1]的范围内。

AVL树的特点如下：

每个节点的左子树和右子树的高度差最多为1，保证了树的平衡性。
查找、插入和删除操作的时间复杂度为O(logn)，相较于普通二叉搜索树具有更好的性能保证。

通过保持树的平衡状态，AVL树能够提供快速的查找、插入和删除操作。然而，AVL树相对于普通二叉搜索树的平衡性要求更高，因为它需要频繁地进行旋转操作来维持平衡。这也使得AVL树在插入和删除操作时比较耗费时间。
在这里插入图片描述

8 堆

也是一种二叉树
堆（Heap）是一种特殊的树形数据结构，通常以完全二叉树的形式存在。它解决了在动态数据集中快速找到最大或最小元素的问题，并且能够高效地支持插入和删除操作。

堆有两种常见的形式：最大堆（Max Heap）和最小堆（Min Heap）。在最大堆中，父节点的值大于或等于其子节点的值；而在最小堆中，父节点的值小于或等于其子节点的值。

堆解决的问题是：

快速找到最大或最小元素：通过使用堆，可以保证根节点为最大（最大堆）或最小（最小堆）的元素。这样可以在O(1)的时间复杂度内找到最大或最小元素，而不需要遍历整个数据集。
高效支持插入和删除操作：堆具有自平衡的性质，当新元素插入或旧元素删除时，堆会自动进行调整，保持堆的性质。这样可以在O(logn)的时间复杂度内完成插入和删除操作，相较于其他排序或搜索算法更高效。

Top-k问题，选择堆是因为它的时间复杂度最小

在这里插入图片描述

def top_k_heap(nums: list[int], k: int) -> list[int]:
    """基于堆查找数组中最大的 k 个元素"""
    # 初始化小顶堆
    heap = []
    # 将数组的前 k 个元素入堆
    for i in range(k):
        heapq.heappush(heap, nums[i])
    # 从第 k+1 个元素开始，保持堆的长度为 k
    for i in range(k, len(nums)):
        # 若当前元素大于堆顶元素，则将堆顶元素出堆、当前元素入堆
        if nums[i] > heap[0]:
            heapq.heappop(heap)
            heapq.heappush(heap, nums[i])
    return heap