数据结构——堆

1. 堆的概念

堆是一种特殊的树，满足如下条件：

1. 完全二叉树：除了最后一层，其他层节点个数都是满的，最后一层的节点都集中在左侧连续位置。

   

2. 堆中每一个节点的值都必须大于等于（或小于等于）其左右节点的值。

   • 每个节点都大于等于其左右节点的叫大根堆。
   • 每个节点都小于等于其左右节点的叫小根堆。

堆和二叉搜索树的区别是：二叉搜索树的要求更为严格，它要求某个节点大于（小于）左侧节点小于（大于）右侧节点，而堆只要求某个节点大于（小于）左右两侧节点即可，因此同一组数据可以构建多种不同形态的堆。

2. 堆的表示

堆是完全二叉树，因此大部分时候使用数组来存储堆。

如上图，我们使用len来表示数组长度，i表示当前节点，我们可以总结出如下规律：

3. 堆的构建

3.1 堆化

堆化指的是对数组元素顺序进行调整，以满足堆的特性，这个调整过程叫做堆化。

堆化分两种：

• 从下往上（上浮）

  当前元素不断向上和父节点比较大小：

  • 大顶堆：当前元素比父节点大，交换，让大的节点上去
  • 小顶堆：当前元素比父节点小，交换，让小的节点上去

  

• 从上往下（下沉）

  当前元素不断向下和两个孩子节点比较大小

  • 大顶堆：当前元素与子节点中较大的比，比子节点小交换，让小的节点下去
  • 小顶堆：当前元素与子节点中较小的比，比子节点大交换，让大的节点下去

  

3.2 构建堆的思路

通过上小节我们了解到，堆化是对有孩子节点的节点进行的操作，因此我们只需要对二叉树的每个非孩子节点进行堆化即可得到堆。根据2.堆的表示那节总结的规律可知最后一个非叶子节点的索引为Math.floor(len / 2) - 1，因此我们对需要对数组从此索引开始向0遍历，依次对节点进行堆化即可得到一个堆。

4. 堆的代码实现

这里以大根堆为例，下面我们通过代码实现一个简单的大根堆类，其中包括堆的初始化，插入元素，删除堆顶元素这三个功能。

class Heap {constructor(arr) {this.arr = arr;this.heapify();}/** * 堆化 */heapify() {for (let i = Math.floor(this.arr.length / 2) - 1; i >= 0; i--) {this.sink(this.arr, i);}}/** * * @param {Array} arr * @param {Number} i * arr[i]节点的下沉操作，即自顶向下堆化 */sink(arr, i) {// 当左孩子节点的索引合规while (2 * i + 1 < arr.length) {let j = 2 * i + 1; // 初始化将最大孩子节点指针指向左孩子if (j + 1 < arr.length && arr[j + 1] > arr[j]) {// 如果当前节点的右孩子比左孩子更大 最大孩子节点指针指向右孩子j++;}if (arr[i] > arr[j]) {// 当前节点的左右儿子都 <= 当前节点，停止下沉break;}// 下沉——交换值[arr[i], arr[j]] = [arr[j], arr[i]];// 下沉——更新当前操作的节点ii = j;}}/** * * @param {Number} val * 向堆中插入值为val的元素，val插入数组最后一位，自底向上堆化 */insert(val) {this.arr.push(val);let i = this.arr.length - 1; // 初始化当前操作的节点 即插入节点的索引while (i > 0) {let j = Math.floor((i - 1) / 2); // 父节点的索引if (this.arr[i] <= this.arr[j]) {// 当前节点小于等于父节点 停止上浮break;}// 上浮——交换[this.arr[i], this.arr[j]] = [this.arr[j], this.arr[i]];// 上浮——更新当前操作的节点ii = j;}}/** * * 删除堆顶元素 */delete() {let len = this.arr.length;// 将最后一个元素值和堆顶互换[this.arr[len - 1], this.arr[0]] = [this.arr[0], this.arr[len - 1]];// 删除最后一个元素this.arr.pop();// 下沉this.sink(this.arr, 0);}}

验证结果：

let heap = new Heap([1, 6, 5, 6, 88, 3, 5, 10]);console.log(heap.arr);// [88, 10, 5, 6, 6, 3, 5, 1]heap.insert(100);console.log(heap.arr);// [100, 88, 5, 10, 6, 3, 5, 1, 6]heap.delete();heap.delete();heap.delete();heap.delete();console.log(heap.arr);// [ 6, 5, 5, 1, 3 ]

根据结果可以看到完全符合大根堆的要求。

参考:

1. 数据结构与算法之 —— 堆(Heap)和堆排序
2. LeetCode｜如何建立一个堆｜大顶堆｜小顶堆｜必会