一、问题定义不相交集数据结构（Disjoint Set Union，DSU），通常称为并查集（Union-Find），维护一组互不相交的动态集合 $S = {S_1, S_2, \ldots, S_k}$。每个集合有一个代表元（representative），通常是集合中的某个特定成员。 ...

一、引言：超越比较排序模型的优先队列1.1 比较模型的下界所有基于元素间比较的优先队列（二叉堆、二项堆、斐波那契堆等）的 insert、extractMin、decreaseKey 等操作，都存在 $\Omega(\log n)$ 的信息论下界。 但如果我们能够放弃”比较”的范式呢？如果键值来自一个 ...

一、引言：为什么我们需要斐波那契堆1.1 二叉堆的局限标准二叉堆（Binary Heap）支持以下操作的复杂度： insert：$O(\log n)$ findMin：$O(1)$ extractMin：$O(\log n)$ decreaseKey：$O(\log n)$ 对于 Dijkstr ...

一、为什么需要摊还分析1.1 最坏情况分析的问题传统的时间复杂度分析聚焦于单次操作的最坏情况。例如： 动态数组插入：最坏 $O(n)$（触发扩容时） 二叉堆插入：最坏 $O(\log n)$ 但这可能过分悲观。以动态数组为例，$n$ 次连续插入的最坏总时间并非 $n \times O(n) &# ...

一、贪心算法的核心思想与理论框架贪心算法（Greedy Algorithm）在每一步选择中都采取当前状态下看起来最优的选择，期望通过一系列局部最优决策最终达到全局最优解。贪心算法的精妙之处在于——对于满足特定性质的问题，这种”短视”的策略恰好能得到全局最优解；但对于另一些问题，贪心策略可能导致任意差 ...

一、动态规划的核心思想动态规划（Dynamic Programming，DP）是一种通过将复杂问题分解为子问题，并存储子问题的解以避免重复计算来求解最优化问题的算法设计技巧。DP这个名称本身有一定误导性——它并非特指某种”动态”的过程，而是Richard Bellman在20世纪50年代命名时，为了 ...

系列学习路线图flowchart TD A([数据结构与算法]) --> B[基础数据结构] subgraph B["基础数据结构"] b1["表·栈·队列"] & b2["树（BST·红黑树）"] & b3["散列 Hash Table"] & b4["优先队列· ...

一、堆的基本概念与数学性质堆（Heap）是一棵完全二叉树（除最后一层外每层都是满的，且最后一层的节点从左到右连续排列），且满足堆序性质：对于最大堆（Max-Heap），任意节点的值大于等于其所有子节点的值；对于最小堆（Min-Heap），任意节点的值小于等于其所有子节点的值。 堆的完全二叉树性质使其 ...

一、哈希表的基本原理与数学基础哈希表（Hash Table）是实现字典（Dictionary）抽象数据类型的最重要数据结构，它在平均情况下提供O(1)时间的插入、删除和查找操作。哈希表的核心思想是：通过哈希函数将键（Key）映射到数组中的索引（Index），从而可能直接定位到目标位置。 从数学角度看 ...

一、二叉树的遍历与Morris遍历二叉树是计算机科学中最重要的数据结构之一，掌握各种遍历方式及其性质是理解树的基础。 递归遍历（前序、中序、后序）是二叉树遍历的标准方式。时间复杂度O(N)，空间复杂度O(log N)（递归栈）到O(N)（链状退化）。 迭代遍历使用显式栈模拟递归： Morris遍历是 ...