题目描述

用大顶堆来模拟优先队列 —— 比如每次取到数组中的最值，操作之后，把操作后的数再放入堆，继续取扔可以取到最值

参考了廉鑫的题解 (opens new window)👍

思路

堆数据结构👇

第二个参数是一个回调函数，用来确定是大顶堆还是小顶堆

• 当传入(a, b) => a > b 这样的回调函数时，则是大顶堆
• 当传入(a, b) => a < b这样的回调函数时，则是小顶堆

除了构造函数外，MyHeap这个类有四个函数

• heapify —— 构造堆
• push —— 往堆里添加元素
• pop —— 弹出堆顶元素，并返回它的值 —— 用来获取最值
• swap —— 交换值

代码实现

class MyHeap {
  constructor(arr, cmp) {
    // 拿到数据和回调函数
    // 看构造大顶堆还是小顶堆
    this.arr = arr;
    this.compare = cmp;

    // 构造
    // 数组长度-1的位置往前构造即可 —— 后面的节点没有左右子节点
    for (let i = Math.floor(arr.length) - 1; i >= 0; i--) {
      this.heapify(i);
    }
  }

  // 初始化构造堆
  heapify(index) {
    let cur = index;
    let left = index * 2 + 1;
    let right = index * 2 + 2;
    // 左右节点都要比较，要取二者的最值
    // 所以不能用if else
    if (left < this.arr.length && this.compare(this.arr[left], this.arr[cur])) {
      cur = left;
    }

    if (
      right < this.arr.length &&
      this.compare(this.arr[right], this.arr[cur])
    ) {
      cur = right;
    }
    // 不相等证明要交换了
    if (cur != index) {
      this.swap(cur, index);
      // 然后继续从修改后的index构造
      this.heapify(cur);
    }
  }
  // 入堆
  // 放到末尾，一直与他的父节点进行比较，如果满足比较条件，就继续往上，直到比较到根节点
  // 一旦不满足比较条件，就跳出循环了，不用继续往上了
  push(val) {
    this.arr.push(val);
    let index = this.arr.length - 1;
    let father = Math.floor((index + 1) / 2) - 1;

    while (father >= 0) {
      if (this.compare(val, this.arr[father])) {
        this.swap(index, father);
        index = father;
        father = Math.floor((index + 1) / 2) - 1;
        // father = ((index + 1) >> 1) - 1;
      } else {
        break;
      }
    }
  }

  // 出堆
  // 要通过把堆顶元素放到堆末尾，删掉末尾元素实现
  // 然后要把放到堆顶的元素重新构造，保持堆的结构
  pop() {
    this.swap(0, this.arr.length - 1);
    let p = this.arr.pop();
    this.heapify(0);
    return p;
  }

  // 交换
  swap(a, b) {
    [this.arr[a], this.arr[b]] = [this.arr[b], this.arr[a]];
  }
}

给你一个正整数数组 nums 。每一次操作中，你可以从 nums 中选择 任意 一个数并将它减小到 恰好 一半。（注意，在后续操作中你可以对减半过的数继续执行操作）

请你返回将 nums 数组和 至少 减少一半的 最少 操作数。

我们利用这个类构造一个大顶堆就可以解决上面这个问题了☝️

var halveArray = function (nums) {
  // 优先队列 —— PriorityQueue

  let sum = nums.reduce((pre, cur) => {
    return cur + pre;
  }, 0);
  let half = sum / 2;
  let heap = new MyHeap(nums, (a, b) => a > b);

  let cnt = 0;
  while (sum > half) {
    let now = heap.pop();
    now /= 2;
    cnt++;
    sum -= now;
    heap.push(now);
  }
  return cnt;
};

const res = halveArray([16, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1]);
console.log("结果为: ", res);

// 结果为: 4