减少比较次数的高效HEAPIFY方法

目标是降低 heapify 方法

这很遗憾,因为与

减少多次插入和删除的时间复杂性 :

想象一下,不插入 n 项目堆立即,
建立一个辅助列表(甚至一个列表)。
在删除(提取?)时,从辅助项中放置一个项目(现在为大小 k )“在现场清空”,并根据需要进行筛选 如果k<<n 。
如果辅助数据结构没有明显小于主数据结构,请合并它们。

这样的思考导致了像Fibonacci这样的高级堆, pairing ,Brodal

堆中插入操作的时间复杂性取决于进行的比较次数。可以想象使用一些开销来实现沿着叶到根路径的智能二进制搜索。

然而,时间复杂性不是 只有 由比较次数决定。时间复杂性由 任何 必须执行的工作,在这种情况下 写入 也是O(log),并且写入次数无法减少。

插入操作需要更改其值的节点数为O(log)。减少比较次数不足以降低复杂性。