O(n)时间复杂度建堆时单个元素最大比较次数相关疑问

问题1：单个元素的最大比较次数 #

你提到的O(n)建堆是二叉堆的自底向上构建方法，核心是从最后一个非叶子节点开始，倒序对每个节点执行下沉（heapify）操作。
在整个建堆过程中，单个元素涉及的最大比较次数是 2⌊log₂n⌋：

• 每次下沉操作处理某节点时，最多需要做2次比较：先比较该节点的左右孩子找到较大值，再和当前节点的值对比判断是否需要交换
• 一个元素最多会移动⌊log₂n⌋层（堆的总高度），每移动一层最多关联2次比较，所以总比较次数上限是2倍的堆高度。

问题2：左子树叶子节点能否移动到右子树叶子位置 #

答案是不可能，不需要2logn次的跨子树比较，原因很简单：
自底向上建堆的所有操作都是父子节点之间的交换，没有跨子树的直接交换逻辑：

1. 下沉操作只会让被处理的节点在自己的子树范围内向下移动，永远不会跑到兄弟节点的子树中
2. 下层元素被交换到上层之后，没有后续操作会让它再向下移动到其他子树：因为建堆的处理顺序是从下到上，上层节点处理完成后，不会再对已经升到上层的下层元素执行下沉操作。
   举个简单例子：左子树的叶子就算是整个堆的最大值，最多只会被逐层交换到根节点，不会再下沉到右子树的任意位置，更不可能到右子树的叶子节点。

内容的提问来源于stack exchange，提问作者tonythestark