简述

这里的堆都是二叉堆, 是一种优先队列(priority queue), 但他不是队列那种链式结构, 而是树型结构.
它满足以下两个性质

1. 完全二叉树

在一颗二叉树中，若除最后一层外的其余层都是满的，并且最后一层要么是满的，要么在右边缺少连续若干节点，则此二叉树为完全二叉树（Complete Binary Tree）。具有n个节点的完全二叉树的深度为 \(\begin{matrix} log_{2}n+1 \end{matrix}\) 深度为k的完全二叉树，至少有 \(\begin{matrix} 2^{k-1} \end{matrix}\) 个节点，至多有 \(\begin{matrix} 2^{k}-1 \end{matrix}\) 个节点。

2. 父节点大于(小于)子节点; 大于的是最大堆, 小于的是最小堆.

它和队列一样只有两个操作

1. 插入(insert)
2. 从头部移出一项(pop)

但在这两个操作之后,为了维持上述属性, 还会以下自处理

1. 上浮(swim), 一般在插入(insert)后, 如果插入元素小于(最小堆)父元素, 交换其位置, 循环至满足性质;
2. 下沉(sink), 一般在取走头(pop)后, 用末尾元素填充头部, 如果填充元素大于(最小堆)子元素, 交换其位置,循环至满足性质;

简述

栈也是一种线性存储结构, 但它只能从栈顶压入, 栈顶弹出数据, 也就是后进先出LIFO(Last In First Out).请和队列(Queue)区分开.

简述

队列也是一种线性存储结构, 但它只能从队尾添加数据, 队头取出数据, 也就是先进先出FIFO(First In First Out). 请和栈(Stack)区分开.

好气，我这种windows一把梭，中午一小时装三台开发机的人，捣鼓了一天mac，装了个有道=- =

chocolatey是window平台的包管理工具，我们可以用其完成开发环境的快速搭建
官网地址

1
2
3
4
5
6
7
8
9

var list = [2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97, 101]

function helper(a: string): number {
    let ret = 1
    for (let i = 0; i < a.length; i++) {
        ret *= list[a[i].charCodeAt(0) - 'a'.charCodeAt(0)]
    }
    return ret
}

利用质数映射字母，求出乘积。

参考资料

维基(中文)
维基(英文)
算法导论(第三版)第13章
删除理解1 删除理解2

简述

红黑树(RBT)是一种自平衡的二叉搜索树(BST), 首先看BST的定义

二叉查找树，也称有序二叉树（ordered binary tree），或已排序二叉树（sorted binary tree），是指一棵空树或者具有下列性质的二叉树：

• 若任意节点的左子树不空，则左子树上所有结点的值均小于它的根结点的值；
• 若任意节点的右子树不空，则右子树上所有结点的值均大于它的根结点的值；
• 任意节点的左、右子树也分别为二叉查找树。
• 没有键值相等的节点（no duplicate nodes）。

如图

在这些基础上再加上以下五条性质

1. 每个结点要么是红的要么是黑的。
2. 根结点是黑的。
3. 每个叶结点（叶结点即指树尾端NIL指针或NULL结点）都是黑的。
4. 如果一个结点是红的，那么它的两个儿子都是黑的。
5. 对于任意结点而言，其到叶结点树尾端NIL指针的每条路径都包含相同数目的黑结点。

最下面应试还有一层叶子节点(nil), mermaid毕竟是画流程图的, 画树还是有点勉强