考虑一个包含n元素的二元最大堆。它的高度是O(log n)。当新元素插入到堆中时，它们将在堆中传播，以便始终满足max-heap属性。
新元素将作为最后一层的子元素添加。但是插入后，可能会违反max-heap属性。因此，将使用heapify方法。这将具有O(log n)的时间复杂度，即堆的高度。
但是我们能让它更有效率吗?
当执行多个插入和删除操作时，这个过程会使操作变慢。此外，严格要求每次插入后堆都应该是最大堆。
目的是降低heapify方法的时间复杂度。这只有在减少比较次数时才有可能。
目的是降低
heapify方法的时间复杂度。
这是一个遗憾，因为这是不可能的，相比
减少多次插入和删除的时间复杂度:
想象不立即插入n项堆，而是
构建一个辅助项堆(甚至是一个列表)。
在delete (extract?)选项下，从辅助元素(现在大小为k) "并根据需要进行向下或向上筛选如果k <<n。
如果辅助数据结构不明显小于主数据结构，则合并它们。
这样的思考导致了高级堆，如斐波那契、配对、布罗达尔……
插入操作在堆中的时间复杂度取决于进行比较的次数。可以想象使用一些开销来实现沿着叶子到根路径的智能二分查找。
但是，时间复杂度不是，只有是由比较次数决定的。时间复杂度由任何必须执行的工作决定，在这种情况下，写的次数也是0 (log𝑛)，并且不能减少写次数。插入操作需要改变值的节点数为0 (log𝑛)。减少比较次数并不足以降低复杂度。