-
插入节点 删除堆顶 建堆 复杂度 堆是一棵完全二叉树,使用数组实现堆,堆分为两种: 最大堆:父节点大于任意子节点(因此堆顶为最大值) 最小堆:父节点小于任意子节点(因此堆顶为最小值) 对于第i个节点(i从0开始计数): 父节点:(i-1)/2 左子节点:2i+1 右子节点:2i+2 若包含sz个节点,则第一个非叶子节点的序号为(sz - 2) / 2 插入节点 插入节点时,进行下列操作: 将元素添加到数组末尾;(相当于叶节点接入堆中) 和父节点进行比较,如果大于父节点(以最大堆为例),则与父节点交换,一直比较交换到根节点 1/******************************************** 2 * 向堆中插 …
阅读更多 -
两种特殊二叉树 二叉树定理 前中后序遍历 递归版 迭代版 两种特殊二叉树 满二叉树(下图左):除叶子节点外的所有分支节点都含有2个非空子节点的二叉树 完全二叉树(下图右):除了最后一层,其余层都是“满”的,这样的二叉树是完全二叉树 二叉树定理 1)任意二叉树度数为2节点的个数等于叶节点个数减1 当只有1个节点时,度为0。每派生出1度,就会多出1个节点。派生出的度和派生出的节点数一定相等。那么就得出了总度数和节点总数的关系: 节点总数 = 总度数 + 1 设度数为2的节点数为X2,度数为1的节点数为X1,度数为0的节点数为X0。可以得出如下关系式: X2 + X1 + X0 = 2X2 + X1 + 1,推出 X2 = X0 - 1 …
阅读更多 -
槽总数的选择 关键码范围较小 关键码范围较大 简单的哈希函数 冲突解决策略 开哈希法 闭哈希法 哈希:把关键码值映射到表中的位置来访问记录的过程 哈希函数:将关键码值映射到位置的函数 槽:哈希表中的一个位置 冲突:不同的关键码经过哈希函数哈希后,映射到相同槽的情况 探查序列:冲突解决策略的闭哈希方法中,如果基位置冲突,需要根据探查函数查找下一个空槽,这个过程产生的序列加上基位置组成了某个关键码的探查序列 基本聚集:在探查函数的设计中,如果不同基位置关键码产生的探查序列发生重合,会导致对剩余空槽的选择概率不均等 。产生的后果是会导致很长的探查序列。这种现象就是基本聚集 二次聚集:基位置相同的关键码,产生的探查序列一样。如果哈希函数在 …
阅读更多 -
内排序 1.插入排序(稳定) 2.冒泡排序(稳定) 3.选择排序(不稳定) 4.shell排序(不稳定) 5.快速排序(不稳定) 6.归并排序(稳定) 7.堆排序(不稳定) 外排序 1.多路归并 稳定性:相同的元素在排序前和排序后的前后位置是否发生改变,没有改变则排序是稳定的,改变则排序是不稳定的 ——八大排序算法的稳定性 1.插入排序 逐个处理待排序的记录,每个记录与前面已排序已排序的子序列进行比较,将它插入子序列中正确位置 代码 1template<class Elem> 2void inssort(Elem A[],int n) 3{ 4 for(int i = 1;i < n;i++) 5 for(int j = i;j …
阅读更多 -
总结自《算法》(第4版) 平衡查找树 2-3查找树 1. 查找 2. 插入 3. 2-3树构造实例 红黑树 1. 保存颜色信息 2. 旋转操作 3. 插入 4. 颜色变换 5. 旋转与颜色变换过程总结 6. 红黑树的性质 B树与B+树 B树简介 B树中检索关键码 B树中插入关键码 B+树简介 B+树中检索关键码 B+树中插入关键码 B+树中删除关键码 平衡查找树 一般的二插查找树如果节点有序插入,树的高度会是n,因此无法实现logn的查找,平衡查找树保证树的高度平衡,因此不管节点插入顺序如何,都可以满足logn的查找 2-3查找树 一棵2-3查找树或为一棵空树,或由以下节点组成: 2-节点:含有1个键(及其对应的值)和2条链接,左 …
阅读更多 -
题目来源:《剑指offer》、leetcode、lintcode、hihocoder、《王道程序员求职宝典》 一 二 三 四 五 六 七 八 九 十 数组 字符串 链表 树 栈和队列 数学 图 设计 海量数据 C/C++基础 一.数组 二分查找 Leetcode35:查找插入位置(二分查找 easy) 《剑指offer》面试题11:旋转数组的最小数字(二分查找) Leetcode33:旋转数组中查找数字(二分查找 medium) Leetcode81:旋转数组中查找数字II(二分查找 medium) 《剑指offer》面试题53(题目一):有序数组中查找数字的范围(二分查找) 《剑指offer》面试题53(题目二):缺失的数字(二 …
阅读更多 -
图的表示 1.邻接矩阵 2.邻接表 图的遍历 DFS(深度优先遍历) BFS(广度优先遍历) 拓扑排序 最小生成树 Prim算法 图可以用G=(V,E)来表示,每个图都包括一个顶点集合V和一个边集合E,顶点总数记为|V|,边总数记为|E| 稀疏图:边数较少的图 密集图:边数较多的图 完全图:包含所有可能边的图 带权图:边上标有权的图 邻接点:一条边所连的两个顶点 简单路径:路径上不包含重复顶点的图 回路:将某个顶点连接到本身,且长度大于等于3的路径 无环图:不带回路的图 图的表示 图有两种常用的表示方法: 邻接矩阵 邻接表 1.邻接矩阵 使用一个二维矩阵来表示图: (i,j)=1,表示顶点i到顶点j之间有一条边(非带权图) …
阅读更多