连接棒材的最低费用

题目

题目来源：力扣（LeetCode）

思路分析

每次选择剩余木棒中费用最少的两根进行连接，其实就是哈弗曼树权值求和的问题。求哈夫曼权值和，我们可以借助数组来做，不过最方便的还是借助优先队列。

• 首先将所有权值push进优先队列
• 循环遍历队列，每次取出队列两个最小值求和，同时将两个值的和push进队列，直到队列为空
• 结束循环，返回结果最小花费

/**
 * @param {number[]} sticks
 * @return {number}
 */
// dequeue是按照进⼊队列的先后顺序来取出元素。
// 在堆中，我们不是按照元素进⼊队列的先后顺序取出元素的，⽽是按照元素的优先级取出元素
var connectSticks = function (sticks) {
  let ans = 0;
  let p = new MinPriorityQueue();
  for (const x of sticks) {
    p.enqueue(x, x);
  }
  while (p.size() > 1) {
    let a = p.dequeue().element;
    a += p.dequeue().element;
    ans += a;
    p.enqueue(a, a);
  }
  return ans;
};