如何在O(n)线性时间内将二叉堆转换为二项队列？

嘿，这个问题我之前也琢磨过——用逐个删除堆顶元素再插入二项队列的方法确实行不通，因为每次删除堆顶是O(lg n)，n次下来就是O(n lg n)，完全达不到线性时间的要求。不过咱们可以换个思路，直接从二叉堆的结构出发，拆分构建二项树，而不是挨个提取元素，这样就能做到O(n)时间复杂度。

先明确几个前提：我假设你说的二叉堆是大顶堆（小顶堆逻辑完全一致，只是合并时的比较方向反过来），而且是用数组存储的完全二叉树（这是二叉堆的标准实现方式，索引i的左孩子是2i+1，右孩子是2i+2，父节点是floor((i-1)/2)）。二项队列的核心是由若干棵大小为2的幂、且每个幂次最多出现一次的二项树组成，每棵树都满足堆性质。

具体步骤如下：

1. 先把二叉堆转成层序数组（如果还不是的话） #

如果你的二叉堆已经是数组存储的，这一步直接跳过就行。如果是链式存储的完全二叉树，先做一次层序遍历，把元素按顺序放进数组A[0...n-1]里，A[0]就是堆顶元素。

2. 从后往前遍历数组，构建并合并二项树 #

我们从数组的最后一个元素开始往前扫，同时维护一个二项树列表——列表里的每棵树大小都是2的幂，而且没有重复大小的树（这刚好符合二项队列的要求）。

对每个元素A[i]，我们这么操作：

• 先建一棵只包含A[i]的二项树，大小是2^0=1。
• 接着检查当前列表里有没有和它大小一样的二项树：
  • 如果有，就把这两棵树合并成一棵更大的二项树（大小直接翻倍）。合并的时候要注意堆性质：大顶堆的话，把较小的那个根节点挂到较大的根节点下面当子节点；小顶堆就反过来。
  • 重复这个合并步骤，直到列表里没有相同大小的树为止。
• 把最终的这棵树加入列表（如果合并后大小变了，就替换掉原来的两棵树）。

为啥这一步是线性时间？你可以类比二进制进位——每个元素最多被合并log n次，但所有元素的合并总次数加起来是O(n)级别的，就像二进制数加1时，进位次数不会超过位数，但整体所有数的进位总和是线性的。

3. 最终的列表就是二项队列 #

等遍历完所有元素，列表里的每棵二项树大小都是不同的2的幂，而且都满足堆性质，这就是我们要的二项队列了。

举个直观的例子：
假设二叉堆的数组是[10, 8, 5, 3, 2]（n=5，二进制是101）：

• 遍历到2（索引4）：建一棵大小1的树，列表变成[B₀(2)]
• 遍历到3（索引3）：建一棵大小1的树，和列表里的B₀合并成B₁（根是3，子节点是2），列表变为[B₁(3)]
• 遍历到5（索引2）：建一棵大小1的树，列表变成[B₁(3), B₀(5)]
• 遍历到8（索引1）：建一棵大小1的树，和B₀合并成B₁（根是8，子节点是5），现在列表里有两棵B₁，再合并成B₂（根是8，子节点是3和5，3的子节点是2），列表变为[B₂(8)]
• 遍历到10（索引0）：建一棵大小1的树，列表变成[B₂(8), B₀(10)]

最终的二项队列就包含一棵大小4的二项树和一棵大小1的二项树，完全符合要求，而且整个过程是线性时间完成的。

关键提醒 #

• 合并二项树的时候一定要守住堆性质，不然最后得到的二项队列就不满足要求了。
• 从后往前遍历是因为二叉堆数组里后面的元素都是叶子或深度大的节点，这样构建合并的时候，不会重复处理上层节点，效率更高。

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