一：什么是堆 堆结构-->数组对象 可以视为一棵完全二叉树 树中每个节点中存放该节点中值的那个元素相对应\green{树中每个节点中存放该节点中值的那个元素相对应}树中每个节点中存放该节点中值的那个元素相对应 a[i]-->下标iii是节点编号，a[i]是该节点编号对应的值 二：堆的性质 1.大根堆1.\BLUE{大根堆}1.大根堆[1] 除根结点外每个节点iii，a[父亲(i)]>=a[i] 即 除根结点外，所有节点的值都不超过其父节点值 堆中最大的元素存在根节点中 2.小根堆2.\PURPLE{小根堆}2.小根堆[2] 除根结点外每个节点iii，a[父亲(i)]<a[i] 即 除根结点外，所有节点的值都不小于其父节点值 堆中最小的元素存在根节点中 （代码以小根堆为例） 三：PUT PUT操作：在堆中<加入>一个元素 1.在堆尾加入一个元素，并把节点设为设为<当前结点> 四：GET GET：<返回>堆顶的值，并删除堆顶 ------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------ 1. 大根堆 ↩︎ 2. 小根堆 ↩︎

性质1 在二叉树的第iii层最多有2i−12^{i-1}2i−1个节点(i>=1i>=1i>=1)。 第一层最多1个节点，第2层最多2个节点…… 性质2 深度为kkk的二叉树至多有2k−12^k-12k−1个节点(k>=1k>=1k>=1) (等比公式) 性质3 对任意一个二叉树，如果其叶子结点数量为n0n_0n0 ，度为二的结点数为n2n_2n2 ，则n0=n2+1n_0 = n_2+1n0 =n2 +1 性质4 具有n(n>=0)n(n>=0)n(n>=0)个结点的完全二叉树深度为ceil(log2n)+1ceil(log_2n) + 1ceil(log2 n)+1