javaScript实现堆

站长

2023年03月15日 19:57 · 阅读数 51

说在前面

计算机领域里，到处都是算法，算法的运用是如此常见，如此自然，如此平凡，乃至像空气一样，会被绝大多数人，甚至是计算机专业的人忽视。从我们打开计算机（或者手机，平板电脑）开始，一系列算法就开始运转起来。从操作系统的调度算法，帮助我们顺畅地使用操作系统；到网络连接过程中各种协议的运转，帮助我们畅游信息世界；从我们使用搜索引擎，一个简单的关键字就可以在毫秒级别的时间返回数以亿计的信息，按照优先级排列展现到我们眼前；到浏览器将枯燥的html, css和js文本转换成直观的网页，供我们轻松阅读浏览；从看似平凡的文字处理工具帮助我们排版，修订；到图像工具中各种神奇的滤镜帮助我们磨皮修片；从游戏，影视作品中炫酷的特效；到最新的交互科技——无论是AR还是VR，越来越普遍的应用，算法无处不在。说实话，现在，我的这个“学习计算机，必须要懂算法”的观点在逐渐转变。这是因为，计算机的软件行业也在渐渐走向成熟。软件行业已经慢慢成熟到了：如果不会算法，也完全可以有所作为的程度。这也是很多人觉得算法没必要的一个主要原因。但是，大家一定要提醒自己。虽然我说学习算法对你来说不一定有用，但与此相对应的，要想取得成功，就一定有别的什么，是有用的。算法不是技术领域的唯一的核心竞争力，但无论是一个人，一个企业，还是做一份事业，都需要有核心竞争力。什么都没有，肯定是不行的。

说到算法，一定离不开数据结构，所以对于一些基础的数据结构，我们还是要掌握的，今天就让我们一起先来看看堆。

什么是堆？

堆的定义

堆的数据结构是完全二叉树或一堆数组，因为堆在逻辑上是一棵完全二叉树，在物理结构上是一个一维数组。堆将根节点最大的堆叫做最大堆或大根堆，根节点最小的堆叫做最小堆或小根堆。常见的堆有二叉堆、斐波那契堆等。堆是非线性数据结构，相当于一维数组,有两个直接后继。堆就是用数组实现的二叉树，所以它没有使用父指针或者子指针。堆根据“堆属性”来排序，“堆属性”决定了树中节点的位置。

堆的性质

1、堆中某个节点的值总是不大于或不小于其父节点的值；
2、堆总是一棵完全二叉树

堆的常用用途：

构建优先队列
支持堆排序
快速找出一个集合中的最小值（或者最大值）

实现思路

使用数组实现堆

堆总是一棵完全二叉树，如下图： javaScript实现堆

根据堆的这个性质，我们可以使用数组来实现，我们只需要记住父子节点之间的关系即可，假设一个节点的下标为 n,我们可以得到以下信息：

1、父节点下标

fatherIdx = Math.floor((n - 1) / 2);

2、左子节点下标

leftInd = n * 2 + 1;

3、右子节点下标

rightInd = (n + 1) * 2 = leftInd + 1;

所以我们可以直接将该二叉树转换为数组来进行存储，根据以上公式我们可以快速的在数组中找到每个元素的父子元素。

javaScript实现堆

初始化

初始化一个空数组用于存储堆数据，接受传入一个自定义比较函数，并将传入用于初始化的数据插入堆数组中。

/**
 *  堆初始化
 *  @param Array array 用于初始化的数组
 *  @param Function compareFun 自定义比较函数
 *  */
constructor(array = [], compareFun = null) {
    this.queue = [];
    if (compareFun) {
        this.compareFun = compareFun;
    }
    for (let index = 0; index < array.length; index++) {
        this.push(array[index]);
    }
}

插入元素

将元素插入到堆数组的最后，因为堆中某个节点的值总是不大于或不小于其父节点的值,所以我们需要根据其比较函数来对堆数组进行调整，将底部插入的元素进行上浮操作，直到满足堆的性质：堆中某个节点的值总是不大于或不小于其父节点的值。

我们以小顶堆为例：

1.如果我们发现插入的新元素之后，新插入的元素比起父节点元素值要小，这样就破坏了我们的堆结构，这样就不构成小顶堆。因此我们需要对该结构进行调整。
2.由于堆的物理结构是一个数组，所以我们可以通过数组下标的形式找到我们孩子节点的父节点。前面我们已经知道父节点与子节点的下标关系为fatherIdx = Math.floor((n - 1) / 2);。当我们找到父节点时，我们进行大小比较，如果子节点小于父节点，此时就要进行交换元素。再让子节点到父节点的位置，重新计算父节点。如果子节点大于父节点，此时即说明调整结束。
3.持续循环比较，如果子节点已经上浮到堆顶，说明向上调整结束。

javaScript实现堆

push(node) {
    this.queue.push(node);
    this.swim();
}
//上浮
swim() {
    let curIdx = this.queue.length - 1;
    let fatherIdx = Math.floor((curIdx - 1) / 2);
    while (this.compareFun(this.queue[fatherIdx], this.queue[curIdx])) {
        [this.queue[curIdx], this.queue[fatherIdx]] = [
            this.queue[fatherIdx],
            this.queue[curIdx],
        ];
        curIdx = fatherIdx;
        fatherIdx = Math.floor((curIdx - 1) / 2);
    }
}

获取堆顶元素值

因为每次插入一个元素的时候我们我们都会对其进行一个上浮操作，所以数组第一个元素就是符合规则的栈顶元素，我们只需要判断堆是否为空，不为空则返回数组的第一个元素即可。

front() {
    if (this.queue.length == 0) return null;
    return this.queue[0];
}

弹出堆顶元素

我们要弹出堆顶元素,实际上就是要删除堆顶的数据，但是我们并不能直接删除堆顶的数据。如果直接删除堆顶的数据，就会破坏堆结构，并且复原的复杂度较高。在这里我们介绍一种方法不仅解决了删除堆的问题，并且复杂度较低。

1、首先我们要将堆顶的数据跟最后一个数据交换，然后删除数组最后一个数据，再进行向下调整算法。
2、向下调整算法具体步骤(过程步骤如下图)：
- a.我们将堆顶元素和数组最后一个元素交换后，此时堆顶的元素是数组的最后一个元素，我们要进行向下调整。定义 parent 为堆顶元素，查找 2 个子节点中较小的一个节点作为孩子节点。由于堆是数组结构实现，我们可以首先找到左孩子节点，让左孩子和右孩子进行比较，较小的作为 child 的最后值。
- b.如果孩子小于父亲，则交换，并继续往下调整。让 parent 到 child 的位置，再重新计算孩子。
- c.当孩子节点下标大于等于元素总个数时，循环结束。

注：循环过程中一旦成堆，则跳出循环。

pop() {
    if (this.queue.length == 0) return null;
    if (this.queue.length == 1) return this.queue.pop();
    const top = this.queue[0];
    this.queue[0] = this.queue.pop();
    this.sink();
    return top;
}
//下沉
sink() {
    let curIdx = 0;
    let minInd = this.getMinInd(curIdx);
    while (this.compareFun(this.queue[curIdx], this.queue[minInd])) {
    [this.queue[curIdx], this.queue[minInd]] = [
        this.queue[minInd],
        this.queue[curIdx],
    ];
    curIdx = minInd;
    minInd = this.getMinInd(curIdx);
    }
}
//获取较小的子元素下标
getMinInd(curIdx) {
    let leftInd = curIdx * 2 + 1;
    let rightInd = leftInd + 1;
    let minInd = leftInd;
    if (
        rightInd < this.queue.length &&
        this.compareFun(this.queue[leftInd], this.queue[rightInd])
    )
    minInd = rightInd;
    return minInd;
}

堆的分类

大顶堆

在上面实现的堆的基础上，我们传入自定义的比较函数即可：

// 大顶堆
const { Heap } = require("./heap");
class MaxHeap {
  constructor(array = []) {
    this.oHeap = new Heap(array, (a, b) => {
      return a < b;
    });
  }
  get queue() {
    return this.oHeap.queue;
  }
  front() {
    return this.oHeap.front();
  }
  pop() {
    return this.oHeap.pop();
  }
  push() {
    this.oHeap.push();
  }
}

小顶堆

在上面实现的堆的基础上，我们传入自定义的比较函数即可：

// 小顶堆
const { Heap } = require("./heap");
class MinHeap {
  constructor(array = []) {
    this.oHeap = new Heap(array, (a, b) => {
      return a > b;
    });
  }
  get queue() {
    return this.oHeap.queue;
  }
  front() {
    return this.oHeap.front();
  }
  pop() {
    return this.oHeap.pop();
  }
  push() {
    this.oHeap.push();
  }
}

堆的应用

堆排序

堆排序其实就是利用了堆的性质，先将所有元素构造一个堆，不断的弹出堆顶元素即可达到堆排序的效果。

const { MaxHeap } = require("@jyeontu/structure-jyeontu");
const list = [1, 3, 2, 4, 6, 3, 0, 9, 7];
const res = [];
const myMaxHeap = new MaxHeap(list);
while (myMaxHeap.front() != null) {
  res.push(myMaxHeap.pop());
}
console.log(res);
//[9, 7, 6, 4, 3, 3, 2, 1, 0]

我们也可以利用这个性质来给堆的实现代码添加一个单元测试：

const { Heap, MinHeap, MaxHeap } = require("../../src/Heap/index");
const assert = require("assert");
describe("Heap", function () {
  describe("checkMaxHeap", function () {
    it("checkOrder", function () {
      const list = [1, 3, 2, 4, 6, 3, 0, 9, 7];
      const orderList = [...list].sort((a, b) => a - b);
      const myMaxHeap = new MaxHeap(list);
      while (myMaxHeap.front() != null) {
        assert.equal(myMaxHeap.pop(), orderList.pop());
      }
    });
  });
  describe("checkMinHeap", function () {
    it("checkOrder", function () {
      const list = [1, 3, 2, 4, 6, 3, 0, 9, 7];
      const orderList = [...list].sort((a, b) => b - a);
      const myMinHeap = new MinHeap(list);
      while (myMinHeap.front() != null) {
        assert.equal(myMinHeap.pop(), orderList.pop());
      }
    });
  });
});

源码地址

Gitee： gitee.com/zheng_yongt…

使用

目前我已经将代码上传到了 npm 上，大家可以直接npm install @jyeontu/structure-jyeontu进行安装，安装完成之后即可直接使用，如下：

const { MaxHeap } = require("@jyeontu/structure-jyeontu");
const list = [1, 3, 2, 4, 6, 3, 0, 9, 7];
const res = [];
const myMaxHeap = new MaxHeap(list);
while (myMaxHeap.front() != null) {
  res.push(myMaxHeap.pop());
}
console.log(res);
//[9, 7, 6, 4, 3, 3, 2, 1, 0]

说在后面

🎉 这里是 JYeontu，现在是一名前端工程师，有空会刷刷算法题，平时喜欢打羽毛球 🏸 ，平时也喜欢写些东西，既为自己记录 📋，也希望可以对大家有那么一丢丢的帮助，写的不好望多多谅解 🙇，写错的地方望指出，定会认真改进 😊，在此谢谢大家的支持，我们下文再见 🙌。

转载自:https://juejin.cn/post/7210604962774958136