二叉堆
# 二叉堆
二叉堆是一种特殊的完全二叉树。它分为两种类型:最大堆和最小堆。
最大堆:任何一个父节点的值都大于或等于它的子节点的值。
最小堆:任何一个父节点的值都小于或等于它的子节点的值。
二叉堆通常通过数组来实现。对于数组中的任意一个元素,设其索引为 i ,则:
它的父节点的索引为 (i - 1) / 2 (当 i 为 0 时,该节点为根节点,无父节点)。
它的左子节点的索引为 2*i + 1 。
它的右子节点的索引为 2*i + 2 。
# 操作
二叉堆主要支持以下操作:
插入(Insert):将新元素加到堆的末尾,然后上浮到正确位置。
删除最大元 / 最小元(Delete...
more...
迭代加深与双向搜索
# 迭代加深搜索
迭代加深搜索(Iterative Deepening Depth-First Search, IDDFS)是一种结合了深度优先搜索(DFS)和广度优先搜索(BFS)的优势的搜索算法。它通过逐步增加搜索深度的方式,实现了在保持空间效率的同时找到最短路径的目的。这种方法特别适合于解决状态空间巨大,但目标深度未知的搜索问题。
# 例子
假设有一个简单的树形结构,我们要找到从根节点到目标节点的最短路径。树的结构如下:
A
/ | \
B C D
/| |
E F G
目标是找到从 A 到 G 的最短路径。
# 迭代加深搜索步骤
深度限制为 1:首先,搜索深度设为...
more...
快速幂
快速幂(Fast Power)是一种高效计算指数运算的算法。它利用指数的二进制表示来降低计算的时间复杂度。
假设要计算 a 的 n 次幂(a^n),其中 n 为非负整数。传统的方法是将 a 连乘 n 次,时间复杂度为 O (n)。而通过快速幂算法,我们可以将时间复杂度降低到 O (logn)。
快速幂算法的基本思想如下:
将指数 n 表示为二进制形式,例如 n=11 表示为 1011。
从二进制的最低位开始,依次处理每一位。
如果当前位为 1,则将结果累乘上底数 a。
每处理完一位,将底数 a 自乘,即 a=a^2。
继续处理下一位,直到所有位都被处理完毕。
下面是一个使用 C++...
more...
归并排序
归并排序(Merge Sort)是一种常见的排序算法,基于分治策略。它将待排序的数组分成两个子数组,分别对这两个子数组进行排序,然后将排好序的子数组合并成一个有序的数组。
归并排序的基本思想如下:
将待排序的数组不断地二分,直到每个子数组只包含一个元素。
对每个子数组进行排序,可以使用递归调用归并排序来完成这一步骤。
将排好序的子数组进行合并,得到一个有序的数组。合并过程中,比较两个子数组的第一个元素,将较小的元素放入新的数组中,并移动指针到下一个元素。
重复步骤 3,直到所有子数组都合并为一个有序的数组。
下面是一个使用 C++ 实现的归并排序的示例代码:
#include...
more...
离散化
离散化是一种将具有一定范围的连续数据映射到有限的离散值集合中的过程。在算法和数据处理中,离散化常用于将连续的数值转换成离散的区间或类别,以便进行进一步的计算或分析。
离散化的主要目的是简化数据的表示和计算,并将连续数据转换为离散的形式,以方便处理。它可以用于数据压缩、数据聚类、特征提取等多个领域。
# 离散化方法
以下是两种常见的离散化方法:
等宽离散化(Equal Width Discretization):将数据划分为相等宽度的区间。这个方法适用于数据分布比较均匀的情况,每个区间的取值范围是相同的。例如,将一个数据范围从 0 到 100 划分为 10 个区间,每个区间的宽度为...
more...
差分
差分是一种用于处理数组或序列 “区间增减” 操作的技术,它可以让我们在 O (1) 的时间复杂度内完成对一个区间内所有元素的增加或减少操作,而直接更新整个区间的元素则可能需要 O (n) 的时间复杂度。差分技术常与前缀和技术配合使用,前缀和用于快速查询区间和,而差分用于高效地修改区间值。
# 差分数组
对于一个给定的数组 arr ,其差分数组 diff 定义为每个位置上的元素与前一个位置上元素的差值,即 diff[i] = arr[i] - arr[i-1] 。为了方便处理,我们通常假设 diff[0] = arr[0] 。
差分数组的主要作用是快速进行区间增减操作。如果我们想要将 arr...
more...