好久没刷算法了，准备利用每天碎片化的时间，再次细致深入地刷一遍数据结构与算法相关知识，第一篇先介绍一下常见的数据结构，然后就开启狂刷算法系列~
1、前言
在计算机科学中，数据结构是一种在计算机程序中组织和存储数据的方式，以便可以有效地访问和使用数据。数据结构提供了一种管理大量数据的方法，可以有效地搜索、排序、插入和删除数据。
数据结构可以分为两种类型：原始数据结构和非原始数据结构。原始数据结构是编程语言中可用的最基本的数据结构，例如整数、浮点数、字符和布尔值。非原始数据结构是使用原始数据类型构建的复杂数据结构，例如数组、链表、堆栈、队列、树、图和哈希表。
为特定任务选择数据结构取决于要处理的数据类型和数量、需要对数据执行的操作以及程序的效率要求。有效地使用数据结构可以大大提高程序的性能，使其更快，内存效率更高。数据结构是在计算机中组织数据以便有效使用数据的一种特殊方式。这个想法是为了减少不同任务的空间和时间复杂性。
数据结构在我们的日常生活中有许多不同的用途。有许多不同的数据结构用于解决不同的数学和逻辑问题。通过使用数据结构，可以在相对较短的时间内组织和处理大量数据。通常，我们会在不同情况下使用的不同数据结构。其大致的分类如下：
- 线性数据结构：数据结构中的数据元素是按顺序或线性排列的，每个元素都与它的上一个和下一个相邻的元素相连，这种数据结构被称为线性数据结构。 线性数据结构的例子有数组、堆栈、队列、链表等。
- 静态数据结构：静态数据结构有一个固定的内存大小。访问静态数据结构中的元素比较容易。这种数据结构的一个例子是数组。
- 动态数据结构：在动态数据结构中，其大小是不固定的。它可以在运行期间随机更新，这可能被认为是关于代码的内存（空间）复杂性的有效方法。这种数据结构的例子有队列、堆栈等。
- 非线性数据结构：数据元素不是按顺序或线性放置的数据结构被称为非线性数据结构。在一个非线性数据结构中，我们不能只在一次运行中遍历所有的元素。非线性数据结构的例子是树和图。
例如，我们可以使用数组数据结构来存储一个具有相同数据类型的项目列表：
有时候，人们会混淆数据类型和数据结构，让我们看一下数据类型和数据结构之间的一些区别：
| 数据类型 | 数据结构 |
| 数据类型是可以赋值的变量形式。它定义特定变量将仅分配给定数据类型的值。 | 数据结构是不同种类数据的集合。整个数据可以使用一个对象来表示，并且可以在整个程序中使用。 |
| 它可以持有价值，但不能持有数据。因此，它是无数据的。 | 它可以在单个对象中保存多种类型的数据。 |
| 数据类型的实现称为抽象实现。 | 数据结构实现称为具体实现。 |
| 在数据类型的情况下没有时间复杂性。 | 在数据结构对象中，时间复杂度起着重要作用。 |
| 在数据类型的情况下，不存储数据的值，因为它只代表可以存储的数据类型。 | 而在数据结构的情况下，数据及其值获取计算机主内存中的空间。此外，数据结构可以在一个对象中保存不同种类和类型的数据。 |
| 数据类型示例有 int、float、double 等。 | 数据结构的例子有栈、队列、树等。 |
数据的结构和算法的综合是相互关联的。数据表示必须易于理解，以便开发人员和用户能够高效地实施操作。数据结构提供了一种组织、检索、管理和存储数据的简便方法。
选择一个好的数据结构可以有效地执行各种关键操作。高效的数据结构还使用最少的内存空间和执行时间来处理该结构。
数据结构是计算机科学和编程中的基本概念。以下是它们为何重要的一些原因：
- 高效的数据处理： 数据结构提供了一种组织和存储数据的方式，可以有效地检索、操作和存储数据。例如，使用哈希表存储数据可以提供对数据的恒定时间访问。
- 内存管理： 正确使用数据结构有助于减少内存使用并优化资源使用。例如，使用动态数组可以比使用静态数组更有效地使用内存。
- 代码可重用性： 数据结构可以用作各种算法和程序中的构建块，从而更容易重用代码。
- 抽象： 数据结构提供了一个抽象级别，使程序员可以专注于数据的逻辑结构和可以对其执行的操作，而不是数据如何存储和操作的细节。
- 算法设计： 许多算法依赖特定的数据结构来高效运行。了解数据结构对于设计和实现高效算法至关重要。
总体而言，数据结构对于以高效且有效的方式管理和操作数据至关重要。它们是计算机科学中的一个基本概念，广泛用于编程和软件开发中。
数据的结构和算法的综合是相互关联的。数据表示必须易于理解，以便开发人员和用户能够高效地实施操作。
数据结构提供了一种组织、检索、管理和存储数据的简便方法。这是数据需求的列表：
- 高效的数据访问和操作： 数据结构支持快速访问和操作数据。例如，数组允许使用索引对元素进行恒定时间访问，而哈希表允许根据键快速访问元素。如果没有数据结构，程序将不得不按顺序搜索数据，从而导致性能下降。
- 内存管理： 数据结构允许通过动态分配和释放内存来有效地使用内存。例如，链表可以根据需要为每个元素动态分配内存，而不是预先分配固定数量的内存。这有助于避免内存浪费并实现高效的内存管理。
- 代码可重用性：数据结构可以在不同的程序和项目中重用。例如，通用堆栈数据结构可用于需要 LIFO（后进先出）功能的多个程序中，而不必每次都重写相同的代码。
- 算法优化： 数据结构通过实现高效的数据访问和操作来帮助优化算法。例如，二叉搜索树允许快速搜索和插入元素，使其成为实现搜索和排序算法的理想选择。
- 可扩展性： 数据结构使程序能够有效地处理大量数据。例如，哈希表可以存储大量数据，同时根据键提供对元素的快速访问。
2、数组
数组是一种线性数据结构，它是存储在连续内存位置的项目的集合。这个想法是将多个相同类型（在有些语言中也可以是不同类型）的元素存储在一个地方。它允许在相对较短的时间内处理大量数据。数组的第一个元素的下标为 0。数组中可以进行不同的操作，例如搜索、排序、插入、遍历、反转和删除。
2.1 数组的特征
数组具有各种特征，如下所示：
- 数组使用基于索引的数据结构，这有助于使用索引轻松识别数组中的每个元素。
- 如果用户想要存储相同数据类型的多个值，则可以有效地利用数组。
- 数组还可以通过将数据存储在二维数组中来处理复杂的数据结构。
- 数组还用于实现其他数据结构，如堆栈、队列、堆、哈希表等。
- 数组中的搜索过程可以很容易地完成。
2.2 数组操作
- 初始化： 数组可以在声明时用值初始化，也可以在稍后使用赋值语句初始化。
- 访问元素： 数组中的元素可以通过它们的索引来访问，索引从 0 开始，直到数组的大小减一。
- 搜索元素： 可以使用线性搜索或二进制搜索算法在数组中搜索特定元素。
- 排序元素： 数组中的元素可以使用冒泡排序、插入排序或快速排序等算法按升序或降序排序。
- 插入元素： 可以在特定位置将元素插入到数组中，但此操作可能很耗时，因为它需要移动数组中的现有元素。
- 删除元素： 可以通过移动元素之后的元素来填充数组中的元素，从而从数组中删除元素。
- 更新元素： 可以通过为特定索引分配新值来更新或修改数组中的元素。
- 遍历元素： 可以按顺序遍历数组中的元素，每个元素访问一次。
这些是对数组执行的一些最常见的操作。使用的具体操作和算法可能会根据问题的要求和使用的编程语言而有所不同。
2.3 数组的应用
- 数组用于解决矩阵问题。
- 数据库记录也是用数组来实现的。
- 它有助于实现排序算法。
- 它还用于实现其他数据结构，如堆栈、队列、堆、哈希表等。
- 数组可用于 CPU 调度。
- 可以用作计算机中的查找表。
- 数组可用于语音处理，其中每个语音信号都是一个数组。
- 电脑的屏幕也是用数组显示的。这里我们使用多维数组。
- 该阵列用于许多管理系统，如图书馆、学生、议会等。
- 该数组用于在线订票系统。手机上的联系人由这个数组显示。
- 在像在线国际象棋这样的游戏中，玩家可以存储他过去的动作以及当前的动作。
2.4 数组的实际应用
- 数组经常用于存储数据以进行数学计算。
- 它用于图像处理。
- 它还用于记录管理。
- 书页也是数组的真实示例。
2.5 数组的优缺点
优点
- 易于创建和使用
- 复杂数据结构的基础构建块
缺点
- 固定长度
- 昂贵的插入/删除或重新排序值
- 排序效率低下
2.6 推荐阅读
3、队列
队列是一种线性数据结构，它遵循执行操作的特定顺序。顺序是 先进先出（FIFO），即首先存储的数据项将首先被访问。在这种情况下，输入和检索数据不仅仅从一端完成。队列的一个例子是资源的任何消费者队列，其中先来的消费者首先得到服务。对队列执行不同的操作，如反转队列（使用或不使用递归）、反转队列的前 K 个元素等。在队列中执行的一些基本操作是入队、出队、前置、后置等。
3.1 队列的特征
队列具有各种不同的特征，如下所示：
队列是一个 FIFO（先进先出） 结构。
要删除队列的最后一个元素，必须删除队列中新元素之前插入的所有元素。
队列是相似数据类型元素的有序列表。
3.2 队列的应用
队列用于处理网站流量。
它有助于维护媒体播放器中的播放列表。
队列在操作系统中用于处理中断。
它有助于为单个共享资源（如打印机、CPU 任务调度等）上的请求提供服务。
它用于数据的异步传输，例如管道、文件 IO 和套接字。
队列用于操作系统中的作业调度。
在社交媒体中上传多张照片或视频队列被使用。
发送电子邮件队列数据结构被使用。
为了一次处理网站流量，使用了队列。
在Windows操作系统下，切换多个应用程序。
3.3 队列操作
队列是实现先进先出 (FIFO) 原则的线性数据结构。以下是对队列执行的一些常见操作：
Enqueue : 可以将元素添加到队列的后面，将新元素添加到队列的末尾。
Dequeue：可以通过执行 dequeue 操作从队列中删除前面的元素，有效地删除添加到队列中的第一个元素。
Peek：可以检查前面的元素，而无需使用 peek 操作将其从队列中删除。
IsEmpty：可以进行检查以确定队列是否为空。
Size：队列中元素的数量可以使用大小操作来确定。
这些是对队列执行的一些最常见的操作。使用的具体操作和算法可能会根据问题的要求和使用的编程语言而有所不同。队列通常用于调度任务、管理进程之间的通信等应用程序中。
3.4 队列的实际应用
队列的真实示例是单车道单行道，其中先进入的车辆将先离开。
在售票窗口的队列中可以看到一个更真实的例子。
商店中的收银台也是队列的一个例子。
自动扶梯上的人
3.5 队列的优缺点
优点
动态尺寸
按接收顺序订购数据
运行时间短
缺点
只能检索最早的元素
3.6 推荐阅读
队列数据结构介绍
在 GeeksforGeeks 上练习队列问题
4、栈
堆栈是一种线性数据结构，它遵循执行操作的特定顺序。顺序是LIFO（后进先出）。只能从一端输入和检索数据。数据的输入和检索也称为堆栈中的压入和弹出操作。堆栈中可能有不同的操作，例如使用递归反转堆栈、排序、删除堆栈的中间元素等。
4.1 栈的特征
堆栈具有各种不同的特性，如下所示：
- 堆栈用于许多不同的算法，如汉诺塔、树遍历、递归等。
- Stack是通过数组或者链表来实现的。
- 它遵循后进先出操作，即先插入的元素将最后弹出，反之亦然。
- 插入和删除在一端执行，即从堆栈的顶部执行。
- 在栈中，如果为栈分配的空间已经满了，还有人试图添加更多的元素，就会导致栈溢出。
4.2 栈的应用
- 堆栈数据结构用于算术表达式的计算和转换。
- 堆栈用于递归。
- 它用于括号检查。
- 在反转字符串时，也会使用堆栈。
- 堆栈用于内存管理。
- 它还用于处理函数调用。
- 堆栈用于将表达式从中缀转换为后缀。
- 堆栈用于在字处理器中执行撤消和重做操作。
- 堆栈用于 JVM 等虚拟机。
- 该堆栈用于媒体播放器。用于播放下一首和上一首歌曲。
- 堆栈用于递归操作。
4.3 栈操作
堆栈是一种线性数据结构，它实现了后进先出 (LIFO) 原则。以下是对堆栈执行的一些常见操作：
- Push：可以将元素推入栈顶，将新元素添加到栈顶。
- Pop：可以通过执行 pop 操作从堆栈中删除顶部元素，有效地删除最后一个被压入堆栈的元素。
- Peek： 可以检查顶部元素，而无需使用 peek 操作将其从堆栈中删除。
- IsEmpty：可以进行检查以确定堆栈是否为空。
- Size：堆栈中元素的数量可以使用大小操作来确定。
这些是对堆栈执行的一些最常见的操作。使用的具体操作和算法可能会根据问题的要求和使用的编程语言而有所不同。堆栈通常用于诸如计算表达式、在计算机程序中实现函数调用堆栈等应用程序。
4.4 栈的实际应用
- 堆叠的现实生活示例是一层一层的餐盘。当您从堆中取出一个盘子时，您可以将该盘子拿到堆的顶部。但这正是最近添加到堆中的盘子。如果你想要堆底部的盘子，你必须移除它上面的所有盘子才能拿到它。
- 浏览器使用堆栈数据结构来跟踪以前访问过的站点。
- 手机通话记录也是使用栈数据结构。
4.5 栈的优缺点
优点：
- 简单易用：栈的实现很简单，因此易于使用和理解。
- 快速插入和删除：由于栈是一种顺序结构，插入和删除操作只需要在栈顶执行，因此速度很快。
- 内存管理：栈是自动分配和释放内存的，因此不需要程序员手动管理内存。
- 递归：栈的结构使其很适合实现递归算法。
缺点：
- 大小固定：栈的大小通常是固定的，因此如果栈的大小不足以容纳所有元素，就会出现栈溢出的问题。
- 只能访问栈顶元素：栈只能访问栈顶元素，如果要访问其他元素，就需要先弹出栈顶元素。
- 静态存储分配：栈采用静态存储分配，因此在编译时就需要确定栈的大小，无法动态调整。如果栈的大小不够，可能会导致程序出错或崩溃。
- 不支持随机访问：栈是一种顺序结构，因此只能按顺序访问元素，不支持随机访问。
- 不支持并发访问：栈是一种单线程数据结，无法并发访问，因此在多线程环境使用受限。
4.5 推荐阅读
5、链表
链表是一种线性数据结构，其中元素不存储在连续的内存位置。链表中的元素使用指针链接，如下图所示：
链表的类型：
- 单链表
- 双向链表
- 循环链表
- 双向循环链表
5.1 链表的特点
链表具有多种特征，如下所示：
- 链表使用额外的内存来存储链接。
- 在链表的初始化过程中，不需要知道元素的大小。
- 链表用于实现栈、队列、图等。
- 链表的第一个节点称为 Head。
- 最后一个节点的下一个指针总是指向 NULL。
- 在链表中，插入和删除很容易。
- 链表的每个节点都包含一个指针/链接，它是下一个节点的地址。
- 链表可以随时轻松地收缩或增长。
5.2 链表操作
链表是一种线性数据结构，其中每个节点包含一个值和对下一个节点的引用。以下是对链表执行的一些常见操作：
- 初始化： 一个链表可以通过创建一个引用第一个节点的头节点来初始化。每个后续节点都包含一个值和对下一个节点的引用。
- 插入元素： 可以在链表的头部、尾部或特定位置插入元素。
- 删除元素：可以通过更新前一个节点的引用指向下一个节点，从链表中删除元素，有效地从列表中删除当前节点。
- 搜索元素：可以通过从头节点开始并跟随对下一个节点的引用直到找到所需元素来搜索链表以查找特定元素。
- 更新元素：可以通过修改特定节点的值来更新链表中的元素。
- 遍历元素： 可以遍历链表中的元素，从头节点开始，沿着对下一个节点的引用，直到到达链表的末尾。
- 反转链表：可以通过更新每个节点的引用来反转链表，使它们指向前一个节点而不是下一个节点。
这些是对链表执行的一些最常见的操作。使用的具体操作和算法可能会根据问题的要求和使用的编程语言而有所不同。
5.3 链表的应用
- 链表用于实现栈、队列、图等。
- 链表用于对长整数执行算术运算。
- 它用于表示稀疏矩阵。
- 它用于文件的链接分配。
- 它有助于内存管理。
- 它用于表示多项式操作，其中每个多项式项表示链表中的一个节点。
- 链接列表用于显示图像容器。用户可以访问过去、当前和下一个图像。
- 它们用于存储访问页面的历史记录。
- 它们用于执行撤消操作。
- 链接用于软件开发，它们指示标签的正确语法。
- 链接列表用于显示社交媒体提要。
5.4 链表的实际应用
- 在循环调度中使用链表来跟踪多人游戏的轮次。
- 它用于图像查看器。上一个和下一个图像是链接的，因此可以通过上一个和下一个按钮访问。
- 在音乐播放列表中，歌曲链接到上一首和下一首歌曲。
5.5 链表的优缺点
优点
- 高效插入和删除新元素
- 比重组数组要简单
缺点
- 比数组使用更多的内存
- 检索特定元素效率低下
- 向后遍历列表效率低下
5.6 推荐阅读
6、树
树是一种非线性的分层数据结构，其中元素以树状结构排列。在树中，最顶端的节点称为根节点。每个节点包含一些数据，数据可以是任何类型。它由中心节点、结构节点和通过边连接的子节点组成。不同的树数据结构允许更快、更容易地访问数据，因为它是非线性数据结构。一棵树有各种术语，如节点、根、边、树的高度、树的度等。
有不同类型的 Tree-like：
6.1 树的特征
该树具有各种不同的特征，如下所示：
- 树也称为递归数据结构。
- 在一棵树中，根的高度可以定义为从根节点到叶节点的最长路径。
- 在一棵树中，还可以计算从顶部到任何节点的深度。根节点的深度为 0。
6.2 树的应用
- 堆是一种树状数据结构，使用数组来实现，用来实现优先级队列。
- B-Tree 和 B+ Tree 用于在数据库中实现索引。
- 语法树有助于编译器设计中的扫描、解析、代码生成和算术表达式的评估。
- KD Tree是一种空间划分树，用于组织K维空间中的点。
- 生成树用于计算机网络中的路由器。
6.3 树操作
树是一种非线性数据结构，由通过边连接的节点组成。以下是对树执行的一些常见操作：
- 插入：可以将新节点添加到树中以创建新分支或增加树的高度。
- 删除：可以通过更新父节点的引用来删除对当前节点的引用，从而从树中删除节点。
- 搜索：从根节点开始，根据当前节点的值遍历树，直到找到想要的节点，即可在树中搜索元素。
- 遍历：可以通过几种不同的方式遍历树中的元素，包括按顺序、前序和后序遍历。
- 高度：树的高度可以通过计算从根节点到最远叶节点的边数来确定。
- 深度：节点的深度可以通过计算从根节点到当前节点的边数来确定。
- Balancing：可以对树进行平衡，保证树的高度最小化，节点分布尽可能均匀。
这些是对树执行的一些最常见的操作。使用的具体操作和算法可能会根据问题的要求和使用的编程语言而有所不同。树通常用于搜索、排序和存储分层数据等应用程序。
6.4 树的实际应用
- 在现实生活中，树数据结构有助于游戏开发。
- 它还有助于在数据库中建立索引。
- 决策树是一种高效的机器学习工具，常用于决策分析。它具有类似流程图的结构，有助于理解数据。
- 域名服务器也使用树形数据结构。
- 树最常见的用例是任何社交网站。
6.5 树的优缺点
优点
- 存储分层关系的理想选择
- 动态尺寸
- 快速插入和删除操作
- 在二叉搜索树中，插入的节点会立即排序
- 二进制搜索树可以有效地进行搜索：长度仅为O（height）
缺点
- 缓慢重新排列节点
- 子节点不保留有关父节点的信息
- 二进制搜索树不如更复杂的哈希表快
- 如果未使用平衡子树实现，则二叉搜索树可以退化为线性搜索（扫描所有元素）
6.6 推荐阅读
7、图
图是一种非线性数据结构，由顶点（或节点）和边组成。它由一组有限的顶点和一组连接一对节点的边组成。该图用于解决最具挑战性和最复杂的编程问题。它有不同的术语，如路径、度数、相邻顶点、连通分量等。
7.1 图的特征
该图具有各种不同的特征，如下所示：
- 从一个顶点到所有其他顶点的最大距离被认为是该顶点的偏心率。
- 具有最小偏心率的顶点被认为是图形的中心点。
- 所有顶点的偏心率的最小值被认为是连通图的半径。
7.2 图的应用
- 该图用于表示计算流程。
- 它用于建模图形。
- 操作系统使用资源分配图。
- 也用于万维网，其中网页代表节点。
7.3 图的操作
图是由节点和边组成的非线性数据结构。以下是对图执行的一些常见操作：
- 添加顶点： 可以将新顶点添加到图中以表示新节点。
- 添加边： 可以在顶点之间添加边来表示节点之间的关系。
- 删除顶点：可以通过更新相邻顶点的引用来删除对当前顶点的引用，从而从图中删除顶点。
- Remove Edge：可以通过更新相邻顶点的引用来删除对当前边的引用来删除边。
- 深度优先搜索 (DFS) ：可以通过以深度优先的方式访问顶点，使用深度优先搜索来遍历图。
- Breadth-First Search (BFS)： 通过以广度优先的方式访问顶点，可以使用广度优先搜索来遍历图。
- 最短路径： 两个顶点之间的最短路径可以使用Dijkstra算法或A*算法等算法来确定。
- 连通分量：图的连通分量可以通过查找彼此相连但不与图中任何其他顶点相连的顶点集来确定。
- 循环检测：可以通过在深度优先搜索期间检查后边来检测图中的循环。
这些是对图形执行的一些最常见的操作。使用的具体操作和算法可能会根据问题的要求和使用的编程语言而有所不同。图通常用于计算机网络、社交网络和路由问题等应用程序中。
7.4 图的实际应用
- 现实世界中最常见的图示例之一是 Google 地图，其中城市作为顶点，连接这些顶点的路径作为图的边。
- 社交网络也是图的一个真实示例，其中网络上的每个人都是一个节点，他们在网络上的所有友谊都是图的边。
- 图还用于研究物理和化学中的分子。
7.5 图的优缺点
优点
- 可以通过文字快速传达视觉效果
- 可以用于建模多种主题，只要它们包含关系结构
缺点
- 在更高的级别上，将文本转换为图像可能会很耗时
- 可能很难看到现有边或给定顶点已连接多少条边
7.6 推荐阅读
8、堆
堆是一种特殊的基于树的数据结构，其中的树是一棵完全二叉树。通常，堆可以有两种类型：
- Max-Heap： 在 Max-Heap 中，存在于根节点的键必须是存在于其所有子节点的键中最大的。对于该二叉树中的所有子树，相同的属性必须递归地为真。
- Min-Heap： 在 Min-Heap 中，存在于根节点的键必须是存在于其所有子节点的键中的最小值。对于该二叉树中的所有子树，相同的属性必须递归地为真。
8.1 堆的特征
- 系统为激活组中的每个堆分配一个唯一的堆标识符。默认堆的堆标识符始终为零。由程序或过程调用的存储管理可绑定 API 使用堆标识符来标识它要操作的堆。可绑定 API 必须在拥有堆的激活组中运行。
- 堆的大小会动态扩展以满足分配请求。堆的最大大小为 (4GB – 512KB) 。如果分配总数（在任何时候）不超过128 000 ，则这是最大堆大小。
- 堆中任何单个分配的最大大小限制为 (16MB – 64KB) 。
8.2 堆的操作
- Heapify： 从数组创建堆的过程。
- Insert： 在现有堆中插入一个元素的过程，时间复杂度为
O(log N)。 - Delete： 删除堆顶元素或优先级最高的元素，然后组织堆并返回时间复杂度为
O(log N)的元素。 - Peek： 检查或查找堆中最优先的元素（最大和最小堆的最大或最小元素）。
8.3 堆的应用
- 优先级队列： 优先级队列可以使用二叉堆高效实现，因为它支持O(log N) 时间的 insert()、delete() 和 extractmax()、decreaseKey() 操作。
- Binomial Heap和Fibonacci Heap是二叉堆的变体。这些变体也在O(log N) 时间内执行联合，这是二叉堆中的 O(N) 操作。
- 顺序统计： 堆数据结构可用于高效地查找数组中第 k 个最小（或最大）元素。您可以查看这篇gfg文章以了解有关第 k 个最小或最大元素的更多信息。
8.4 堆的优缺点
优点
- 快速访问最大/最小元素 (
O(1)) - 高效的插入和删除操作（
O（log n）） - 灵活的大小
- 可以有效地实现为数组
- 适用于实时应用
缺点
- 不适合搜索除最大/最小值以外的元素（最坏情况下为
O(n)） - 维护堆结构的额外内存开销
- 比非优先队列操作的数组和链表等其他数据结构慢。
9、哈希表
哈希是一种使用哈希函数将键和值映射到哈希表中的技术或过程。这样做是为了更快地访问元素。映射的效率取决于所使用的散列函数的效率。
让哈希函数 H(x) 将值 x 映射到数组中索引 x%10 处。例如，如果值列表是 [11, 12, 13, 14, 15]，它将分别存储在数组或哈希表中的位置 {1, 2, 3, 4, 5}。
哈希表的优缺点
优点
- 键可以采用任何形式，而数组的索引必须为整数
- 高效的搜索功能
- 每次搜索的操作次数不变
- 插入或删除操作的固定成本
缺点
- 冲突：两个键转换为相同的哈希码或两个哈希码指向相同的值时引起的错误。
- 这些错误可能很常见，并且经常需要对哈希函数进行全面检查。
10、矩阵
矩阵表示按行和列顺序排列的数字集合。有必要将矩阵的元素括在圆括号或方括号中。
具有 9 个元素的矩阵如下所示：
这个矩阵[M]有3行和3列。矩阵[M]的每个元素都可以用其行号和列号来表示。例如，a23 = 6。
11、Trie
Trie 是一种 k 元搜索树，用于存储和搜索集合中的特定键。使用 Trie，可以将搜索复杂性带到最佳限制（密钥长度）。
定义：Trie（源自检索）是一种多向树数据结构，用于在字母表上存储字符串。它用于存储大量字符串。使用尝试可以有效地完成模式匹配。
Trie 显示诸如 allot、alone、ant 和 are、bat、bad 之类的词。这个想法是所有共享公共前缀的字符串都应该来自一个公共节点。尝试用于拼写检查程序。
- 预处理模式提高了模式匹配算法的性能。但是，如果文本非常大，那么为了高效搜索，最好预处理文本而不是模式。
trie是一种数据结构，它支持在时间上与模式大小成比例的模式匹配查询。
如果我们将键存储在二叉搜索树中，平衡良好的 BST 需要的时间与M * log N成正比，其中M是最大字符串长度，N是树中键的数量。使用 Trie，可以在O(M) 时间内搜索密钥。然而，惩罚是对 Trie 的存储要求。
Trie是一种高效的信息检索Trie val数据结构。使用 Trie，可以将搜索复杂性带到最佳限制（密钥长度）。如果我们将键存储在二叉搜索树中，则平衡良好的 BST 需要的时间与 M * log N 成正比，其中 M 是最大字符串长度，N 是树中键的数量。使用 Trie，我们可以在 O(M) 时间内搜索密钥。但是，惩罚是对 Trie 存储要求。
