堆专题里有哪些冷门但实用的知识？

堆 堆是一棵树 其中有如下性质： 父亲总>=或<=它的所有儿子 \(>=\)的叫大根堆 \(<=\)的叫小根堆 所以根节点总是堆的最小或最大值 堆中任意一颗子树也是堆 二叉堆 如不说明，堆指二叉堆 二叉堆是一颗完全二叉树 所以容易存储 可以用数组 根节点为\(1\) 左子树为\(2i\) 右子树为\(2i+1\) 所以是连续的 很容易存储 二叉堆的操作： 设堆的节点个数为\(n\) 以小根堆为例 插入元素： 可以把元素插入到堆的最后，即\(n+1\)位置 那么有可能存在这个元素<它的父亲，所以需要进行向上调整 时间复杂度\(O(log(n+1))=O(logn)\) 删除根节点: 不能直接删除，会使得堆被分开，所以要找到最后一个元素n，把它和根节点1号的权值交换，然后把n号删除（或权值清空，要看具体实现） 但是最后一个元素往往较大，与根节点交换后往往会使得根节点>子节点，所以需要进行向下调整 为什么要选用最后一个元素与根交换,是因为最后一个下面没有元素了，可以直接删掉，如果与其它不是叶节点的节点交换，那么还是删不掉，因为下面还有点 而如果和不是\(n\)的其他叶节点交换，那么删掉后就不是完全二叉树了 时间复杂度： \(O（logn-log1)=O(logn)\) 调整某个点的权值： 可以增大或减小，然后要看是大还是小根堆 如果是小根堆，那么增大权值 对它上面的节点来说是符合性质的，因为下面大，上面不变，就相当于上面小于下面 对它下面的节点来说就可能不符合性质了，因为下面不变，上面大，就可能超过下面，所以要向下调整 减小权值时要向上调整 如果是大根堆，那么增大权值要向上调整 减小权值要向下调整 设节点编号为\(k\) 向上调整就是\(O(logk)￥ 向下调整就是\)O(logn-logk)$ 向上调整： 这是关键操作。