插入节点 删除堆顶 建堆 复杂度 堆是一棵完全二叉树，使用数组实现堆，堆分为两种： 最大堆：父节点大于任意子节点（因此堆顶为最大值） 最小堆：父节点小于任意子节点（因此堆顶为最小值） 对于第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之间有一条边（非带权图） …

阅读更多