如何构造最小化叶节点值深乘积和的O(nlogn)时间复杂度二叉树？

这个问题本质上是构造哈夫曼树（Huffman Tree），哈夫曼算法正是专门用于最小化加权路径长度（即题目中的∑A_i*d_i）的经典算法，且时间复杂度恰好为O(n log n)。

核心思路 #

哈夫曼树的构建逻辑是：每次选取权重最小的两个节点（初始时每个数组元素都是一个单独的叶节点），将它们合并为一个新的中间节点（权重为两个子节点的权重之和），重复这个过程直到所有节点合并成一棵完整的树。最终得到的树的加权路径长度就是所有可能二叉树中的最小值。

算法步骤（基于最小堆实现） #

• 初始化最小堆：将数组中的每个整数作为单独的叶节点，插入到最小堆（优先队列）中。堆的排序依据是节点的权重（即数组元素的值）。
• 循环合并节点：
  当堆中元素数量大于1时，重复以下操作：
  1. 从堆中取出权重最小的两个节点（记为node1和node2）。
  2. 创建一个新的中间节点，其权重为node1.weight + node2.weight，将node1和node2分别作为该中间节点的左右子节点（左右顺序不影响最终的加权路径长度）。
  3. 将这个新的中间节点插入回最小堆。
• 生成最终树：堆中最后剩下的节点就是树的根节点，此时整棵树即为满足要求的非平衡二叉树。

时间复杂度分析 #

• 初始化堆：若使用二叉堆，可在O(n)时间完成初始化；即使采用标准插入方式，时间复杂度也为O(n log n)，不影响整体复杂度。
• 合并操作：共需执行n-1次合并，每次合并包含两次堆顶提取（O(log n)）和一次插入（O(log n)），总时间为O(n log n)。
• 整体时间复杂度为O(n log n)，完全符合题目要求。

示例验证 #

假设输入数组为[5, 3, 8, 2]：

1. 初始堆元素：[2, 3, 8, 5]（按权重升序排列）
2. 第一次合并：取出2和3，合并为权重5的中间节点，堆变为[5, 5, 8]
3. 第二次合并：取出5和5，合并为权重10的中间节点，堆变为[8, 10]
4. 第三次合并：取出8和10，合并为权重18的根节点，堆仅剩该节点。
   最终加权路径长度计算：22 + 32 +52 +81 = 4+6+10+8=28，这是所有可能二叉树中的最小值。

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