22k 字 20 分钟

# 程序员常用的 10 中算法 # 二分查找 (非递归) # 二分查找 (非递归) 介绍 前面我们讲过了二分查找算法，是使用递归的方式 (非递归也写了因为会所以提前写了)。下面我们讲解二分查找算法的非递归方式。 二分查找法只适用于从有序的数列中进行查找 (比如数组和字母等)，将数列排序后再进行查找。 二分查找法的运行时间为对数数据 O (log2N)，即查找到需要的目标位置最多只需要 log2N 步，假设从 [0,99] 的队列 (100 个数，即 n=100) 中寻到目标数 30，则需要查找步数为 log2100，即最多需要查找 7 次 (2^6 < 100 <...
39k 字 35 分钟

# 树结构基础部分 # 二叉树 为什么需要树这种数据结构 数组存储方式的分析 优点：通过下标方式访问元素，速度快。对于有序数组，还可使用二分查找提高检索速度。 缺点：如果要检索具体某个值，或者插入值 (按一定顺序) 会整体移动，效率较低 [示意图]。 链式存储方式的分析 优点：在一定程度上对数组存储方式有优化 (比如：插入一个数值节点，只需要将插入节点，链接到链表中即可， 删除效率也很好)。 缺点：在进行检索时，效率仍然较低，比如 (检索某个值，需要从头节点开始遍历) 【示意图】 树存储方式的分析 能提高数据存储，读取的效率，比如利用 二叉排序树 (Binary Sort...
3.3k 字 3 分钟

# 多路查找树 二叉树与 B 树 树 [B 树，B+ 树，B * 树](#B 树，B+ 树，B * 树) ​ 钢达姆机器人 # 二叉树与 B 树 二叉树的问题分析 二叉树的操作效率较高，但是也存在问题，请看下面的二叉树 层数：5 节点数量：31 计算方式：2 ^ 5 层数 - 1 = 31 二叉树需要加载到内存的，如果二叉树的节点少，没有什么问题，但是如果二叉树的节点很多 (比如 1 亿)，就存在如下问题： 问题 1：在构建二叉树时，需要多次进行 i/o 操作 (海量数据存在数据库或文件中)，节点海量，构建二叉树时，速度有影响。 问题...
15k 字 14 分钟

# 图 为什么要有图 前面我们学了线性表 和 树 线性表局限于一个直接前驱和一个直接后继的关系 树也只能有一个直接前驱也就是父节点 当我们需要表示多对多的关系时，这里我们就用到了图 # 图的举例说明 图是一种数据结构，其中节点可以具有零个或多个相邻元素。两个节点之间的连接称为 边。节点也可以称为顶点。如图： # 图常用的概念 顶点 (vertex) 边 (edge) 路径 无向图 (下图) 无向图：顶点之间的连接没有方向，比如 A - B，既可以是 A - B 也可以 B - A 路径：比如从 D - C 的路径有 D - B - C D - A - B - C 有向图...
728 字 1 分钟

@Configurationpublic class RedisConfig { @Bean @SuppressWarnings(value = { "unchecked", "rawtypes" }) public RedisTemplate<Object, Object> redisTemplate(RedisConnectionFactory connectionFactory) { RedisTemplate<Object,...
2k 字 2 分钟

# 堆排序 使用堆 实现排序 # 算法描述： heapify 建立大顶堆 将堆顶与堆低交换 (最大元素被交换到堆低)，缩小并下潜调整堆 重复第二步直至堆里剩一个元素 # 第一步：heapify 建立大顶堆 如下图的数组元素 我们使用 heapify 进行一个 堆化，现在是大顶堆了，父节点比孩子节点都大 此时 第一步就完成了 # 第二步：将 堆顶元素 跟 堆低元素 交换位置 交换完位置后让堆的 大小 缩小 1 并且 下潜 调整符合 大顶堆的特性 下图就是 将 7 堆顶元素和 1 堆低元素交换位置 然后又 进行下潜 调整为符合 大顶堆的特性后的样子，操作完后 堆的大小 缩小 1 的范围...
4.7k 字 4 分钟

# 堆 - heapify2 - 实现其它方法 /** * @author Dkx * @version 1.0 * @2024/1/2211:08 * @function * @comment * 大顶堆 */public class MaxHeap{ int array[]; int size; public MaxHeap(int capacity) { this.array = new int[capacity]; } /** * 如果实例化对象时传入的是一个普通数组那么我们就需要 进行 建堆 让这个数组符合 大顶堆的 特性 *...
2.5k 字 2 分钟

# 优先级队列 - 无序数组的实现 # 介绍： # 普通队列 一端进 一端出 ，FIFO 先进先出 # 优先级队列 一端进 一端出 ，它会按照队列中的优先级 出栈， 优先级高的 先 出栈 # 代码： 写了 三个类 主要是 PriorityQueue 中的逻辑代码 PriorityQueue public class PriorityQueue<E extends Priority> implements Queue<E>{ Priority[] array; int size; // 初始化 实例化 Priority 数组 并 设定...
2k 字 2 分钟

# 堆 - heapify1 我们看一个堆里面相对比较重要的方法叫 heapify 翻译过来叫 (建堆，堆化) 这是什么意思呢？比如说我想做一个大顶堆 ，给了一个 初始的数组 但是上面这个数组并不符合 大顶堆 的定义，因为大顶堆 要求 任意一个父节点它的值要比 两个孩子节点大 我们要把上面这个数组 调整成 符合大顶堆的 定义 这个过程我们就叫做 heapify (建堆) # 思路： 比如说准备了一个 空堆 我们向这个 空堆中添加元素， 如比我们先添加一个元素 2，如下图： 如果我们再加入一个元素 1 的话 那么跟之前一样 先跟父元素比较，如果比 父元素小那么就 符合条件...
6.8k 字 6 分钟

# 优先级队列 - 堆实现 - 大顶堆实现 # 堆实现 堆本质上就是一种树，堆的方式也有很多种，通常使用的是完全二叉树实现。 计算机科学中，堆是一种基于数的数据结构，通常用完全二叉树实现。堆的特性如下： 在大顶堆中，任意节点 C 与它的父节点 P 符合 P.value$$\geq$$ C.value 而小顶堆中，任意节点与 C 与它的父节点 P 符号 P.value $$\leq$$ C.value 最顶层的节点 (没有父节点) 称之为 root 根节点 # 那到底什么叫完全二叉树呢？ 我们对照上面图进行解释： 首先我们看什么叫 二叉 ，所谓的 二叉 就是 树中每个节点...