Learning Path
浏览 数据结构 相关教程与章节。
主流编程语言、数据结构、设计模式、正则与基础算法。
教程
45
相邻节点迭代器 图论中最常见的操作就是遍历邻边，通过一个顶点遍历相关的邻边。邻接矩阵的遍历邻边的时间复杂度为 O(V)，邻接表可以直接找到，效率更高。 邻接矩阵迭代: [mycode4 type='java'] ... public Iterable adj(int v) { assert v >= 0 && v < n; Vector adjV = new Vector..
寻路算法 图的寻路算法也可以通过深度优先遍历 dfs 实现，寻找图 graph 从起始 s 点到其他点的路径，在上一小节的实现类中添加全局变量 from数组记录路径，from[i] 表示查找的路径上i的上一个节点。 首先构造函数初始化寻路算法的初始条件，from = new int[G.V()] 和 from = new int[G.V()]，并在循环中设置默认值，visited 数组全部为false，from 数组全部为 -1 值，后..
广度优先遍历与最短路径 广度优先遍历从某个顶点 v 出发，首先访问这个结点，并将其标记为已访问过，然后顺序访问结点v的所有未被访问的邻接点 {vi,..,vj} ，并将其标记为已访问过，然后将 {vi,...,vj} 中的每一个节点重复节点v的访问方法，直到所有结点都被访问完为止。我们可以分为三个步骤： （1）使用一个辅助队列 q，首先将顶点 v 入队，将其标记为已访问，然后循环检测队列是否为空。 （2）如果队列不为空，则取出队列第一..
图论基础和表示 一、概念及其介绍 图论(Graph Theory)是离散数学的一个分支，是一门研究图(Graph)的学问。图是用来对对象之间的成对关系建模的数学结构，由“节点”或“顶点”(Vertex）以及连接这些顶点的“边”（Edge）组成。值得注意的是，图的顶点集合不能为空，但边的集合可以为空。图可能是无向的，这意味着图中的边在连接顶点时无需区分方向。否则，称图是有向的。下面左图是一个典型的无向图结构，右图则属于有向图。本章节介绍的..
索引堆及其优化 一、概念及其介绍 索引堆是对堆这个数据结构的优化。索引堆使用了一个新的 int 类型的数组，用于存放索引信息。相较于堆，优点如下： 优化了交换元素的消耗。 加入的数据位置固定，方便寻找。 二、适用说明 如果堆中存储的元素较大，那么进行交换就要消耗大量的时间，这个时候可以用索引堆的数据结构进行替代，堆中存储的是数组的索引，我们相应操作的是索引。 三、结构图示 我们需要对之前堆的代码实现进行改造，换成直接操..
堆的 shift down 本小节将介绍如何从一个最大堆中取出一个元素，称为 shift down，只能取出最大优先级的元素，也就是根节点，把原来的 62 取出后，下面介绍如何填补这个最大堆。 第一步，我们将数组最后一位数组放到根节点，此时不满足最大堆的定义。 调整的过程是将这个根节点 16 一步一步向下挪，16 比子节点都小，先比较子节点 52 和 30 哪个大，和大的交换位置。 继续比较 16 的子节点 28 和 41，41..
堆的 shift up 本小节介绍如何向一个最大堆中添加元素，称为 shift up。假设我们对下面的最大堆新加入一个元素52，放在数组的最后一位，52大于父节点16，此时不满足堆的定义，需要进行调整。 首先交换索引为 5 和 11 数组中数值的位置，也就是 52 和 16 交换位置。 此时 52 依然比父节点索引为 2 的数值 41 大，我们还需要进一步挪位置。 这时比较 52 和 62 的大小，52 已经比..
优化堆排序 上一节的堆排序，我们开辟了额外的空间进行构造堆和对堆进行排序。这一小节，我们进行优化，使用原地堆排序。 对于一个最大堆，首先将开始位置数据和数组末尾数值进行交换，那么数组末尾就是最大元素，然后再对W元素进行 shift down 操作，重新生成最大堆，然后将新生成的最大数和整个数组倒数第二位置进行交换，此时倒数第二位置就是倒数第二大数据，这个过程以此类推。 整个过程可以用如下图表示： Java 实例代码 源码包下载..
基础堆排序 一、概念及其介绍 堆排序（Heapsort）是指利用堆这种数据结构所设计的一种排序算法。堆是一个近似 完全二叉树的结构，并同时满足堆积的性质：即子结点的键值或索引总是小于（或者大于）它的父节点。 二、适用说明 我们之前构造堆的过程是一个个数据调用 insert 方法使用 shift up 逐个插入到堆中，这个算法的时候时间复杂度是 O(nlogn)，本小节介绍的一种构造堆排序的过程，称为 Heapify，算法时间复杂..
堆的基本存储 一、概念及其介绍 堆(Heap)是计算机科学中一类特殊的数据结构的统称。堆通常是一个可以被看做一棵完全二叉树的数组对象。堆满足下列性质： 堆中某个节点的值总是不大于或不小于其父节点的值。 堆总是一棵完全二叉树。 二、适用说明 堆是利用完全二叉树的结构来维护一组数据，然后进行相关操作，一般的操作进行一次的时间复杂度在 O(1)~O(logn) 之间，堆通常用于动态分配和释放程序所使用的对象。 若为优先队列的使用场景，..
插入排序 插入排序（Insertion Sort），一般也被称为直接插入排序，对于少量元素的排序，它是一个有效的算法。 插入排序是一种最简单的排序方法，它的基本思想是将一个记录插入到已经排好序的有序表中，从而一个新的、记录数增 1 的有序表。在其实现过程使用双层循环，外层循环对除了第一个元素之外的所有元素，内层循环对当前元素前面有序表进行待插入位置查找，并进行移动。 工作原理 插入排序的核心思想是 “构建有序序列”。它将待排序的数组..
归并排序 归并排序（英语：Merge sort，或mergesort），是建立在归并操作上的一种有效的排序算法。 归并排序是采用分治法(Divide and Conquer）的一个非常典型的应用。将已有序的子序列合并，得到完全有序的序列；即先使每个子序列有序，再使子序列段间有序。若将两个有序表合并成一个有序表，称为二路归并。 想象一下，你要整理一副完全打乱的扑克牌。一个高效的方法是：先把这副牌分成两小堆，分别把每一小堆整理好，最后再把这..
随机化快速排序 $(function() { $('.math').each(function() { renderMathInElement(this, { // 自定义选项，如果需要的话 delimiters: [ { left: '\\(', right: '\\)..
希尔排序 希尔排序（Shell Sort）是插入排序的一种高效改进版本，由 Donald Shell 于 1959 年提出。 希尔排序的核心思想是通过将原始列表分割成多个子序列，先对每个子序列进行插入排序，然后逐步缩小子序列的间隔，最终对整个列表进行一次标准的插入排序。这种方法使得元素能够大跨度地移动，从而在早期阶段消除大量的逆序对，显著提升了排序效率。 想象一下整理一副乱序的扑克牌。插入排序就像一张一张地拿起牌，插入到手中已排序牌堆..
排序算法衍生问题 当我们掌握了冒泡排序、快速排序等基础排序算法后，会发现排序不仅仅是把数据排好序这么简单。 在实际编程和面试中，许多问题都是排序算法的变体或衍生问题。 理解这些衍生问题，能帮助我们更深刻地掌握排序算法的本质，并提升解决复杂问题的能力。 本文将探讨几个经典的排序算法衍生问题，通过分析它们的核心思想、解决方案和实际应用，帮助你建立更系统的算法思维。 什么是排序算法衍生问题？ 排序算法衍生问题指的是那些不直接要求排序，但解决..
并查集基础 一、概念及其介绍 并查集是一种树型的数据结构，用于处理一些不相交集合的合并及查询问题。并查集的思想是用一个数组表示了整片森林（parent），树的根节点唯一标识了一个集合，我们只要找到了某个元素的的树根，就能确定它在哪个集合里。 二、适用说明 并查集用在一些有 N 个元素的集合应用问题中，我们通常是在开始时让每个元素构成一个单元素的集合，然后按一定顺序将属于同一组的元素所在的集合合并，其间要反复查找一个元素在哪个集合中。这..
并查集路径压缩 并查集里的 find 函数里可以进行路径压缩，是为了更快速的查找一个点的根节点。对于一个集合树来说，它的根节点下面可以依附着许多的节点，因此，我们可以尝试在 find 的过程中，从底向上，如果此时访问的节点不是根节点的话，那么我们可以把这个节点尽量的往上挪一挪，减少数的层数，这个过程就叫做路径压缩。 如下图中，find(4) 的过程就可以路径压缩，让数的层数更少。 节点 4 往上寻找根节点时，压缩第一步，树的层数就减少..
并查集快速合并 对于一组数据，并查集主要支持两个动作： union(p,q) - 将 p 和 q 两个元素连接起来。 find(p) - 查询 p 元素在哪个集合中。 isConnected(p,q) - 查看 p 和 q 两个元素是否相连接在一起。 在上一小节中，我们用 id 数组的形式表示并查集，实际操作过程中查找的时间复杂度为 O(1)，但连接效率并不高。本小节，我们将用另外一种方式实现并查集。把每一个元素，看做是一个..
并查集快速查找 本小节基于上一小节并查集的结构介绍基础操作，查询和合并和判断是否连接。 查询元素所在的集合编号，直接返回 id 数组值，O(1) 的时间复杂度。 [mycode4 type='java'] ... private int find(int p) { assert p >= 0 && p < count; return id[p]; } ... [/myco..
并查集 rank 的优化 上一小节介绍了并查集基于 size 的优化，但是某些场景下，也会存在某些问题，如下图所示，操作 union(4,2)。 根据上一小节，size 的优化，元素少的集合根节点指向元素多的根节点。操作完后，层数变为4，比之前增多了一层，如下图所示： 由此可知，依靠集合的 size 判断指向并不是完全正确的，更准确的是，根据两个集合层数，具体判断根节点的指向，层数少的集合根节点指向层数多的集合根节点，如下图所示，这..
并查集 size 的优化 按照上一小节的思路，我们把如下图所示的并查集，进行 union(4,9) 操作。 合并操作后的结构为： 可以发现，这个结构的树的层相对较高，若此时元素数量增多，这样产生的消耗就会相对较大。解决这个问题其实很简单，在进行具体指向操作的时候先进行判断，把元素少的集合根节点指向元素多的根节点，能更高概率的生成一个层数比较低的树。 构造并查集的时候需要多一个参数，sz 数组，sz[i] 表示以 i 为..