1. 认识堆结构

堆是一种特殊的完全二叉树
所有的节点都大于等于（大顶堆） 或 小于等于（小顶堆） 他的子节点
js 中通常使用数组表示堆
1. 左侧子节点的位置 2 * index + 1
2. 右侧子节点的位置 2 * index + 2
3. 父节点的位置 （index - 1）/ 2

2.堆的应用

堆能快速高效的找出最大值和最小值 O（1）
找出第 k 个最大（小）元素
1. 构建一个最小堆，并将元素依次插入堆中
2. 当堆的容量超过 K，就删除堆顶
3. 插入结束后，堆顶就是第 K 个最大元素

3. 堆结构的设计

接下来，让我们对堆结构进行设计，看看需要有哪些属性和方法。

堆结构常见的属性：

data：存储堆结构的元素，通常使用数组来实现
size：堆中当前元素的数量

堆结构常见的方法

insert(value)：在堆中插入一个新元素
extract/delete()：从堆中删除最大/最小元素
peek()：返回堆中的最大/最小元素
isEmpty()：判断堆是否为空
buildHeap(list)：通过一个列表来构造堆

明确了这些属性和方法之后，让我们来封装一个堆结构吧

4. 堆结构的封装

我们这里以最大堆为例

4.1 基础框架 v1 版

ts
class Heap<T> {
  // 属性
  data: T[] = [];
  private length: number = 0;

  // 私有工具方法
  private swap(i: number, j: number) {
    [this.data[i], this.data[j]] = [this.data[j], this.data[i]];
  }

  insert(value: T) {}

  extract(): T | undefined {
    return undefined;
  }

  peek(): T | undefined {
    return this.data[0];
  }

  size() {
    return this.length;
  }

  isEmpty() {
    return this.length === 0;
  }

  buildHeap(arr: T[]) {}
}

在上面的代码中，我们封装了一个 Heap 类作为堆的结构，在里面定义了一些属性和方法，这些属性和方法都是第三章中讲到的。

4.2 添加 insert 方法 v2 版

如果你想实现一个最大堆，那么可以从实现 insert 方法开始

因为每次插入元素后，需要对堆进行重构，以维护最大堆的性质
这种策略叫上滤


// 方法
insert(value: T) {
  // 1. 将元素放到数组的尾部
  this.data.push(value);
  this.length++;

  // 2. 维护最大堆的特性（最后位置的元素需要进行上滤操作）
  this.heapify_up();
}

private heapify_up() {
  let index = this.length - 1;
  let parentIndex = Math.floor((index - 1) / 2);
  while (index > 0) {
    if (this.data[index] <= this.data[parentIndex]) {
      break;
    }

    this.swap(index, parentIndex);

    index = parentIndex;
  }
}

在上面的代码中，我们新定义了一个私有方法 heapify_up，这是一个维护最大堆特性的方法。

4.3 添加 extract 方法 v3 版

删除操作也需要考虑在删除元素后的操作：

因为你每次删除元素后，需要对堆进行重构，以维护最大堆的特性
这种向下替换元素的策略叫做下滤

ts
private heapify_down(index: number) {
  while (2 * index + 1 < this.length) {
    // 1. 找到左右子节点
    let leftChildIndex = 2 * index + 1;
    let rightChildIndex = leftChildIndex + 1;

    // 2. 找到左右子节点节点较大的值
    let largeIndex = leftChildIndex;
    if (rightChildIndex < this.length && this.data[rightChildIndex] > this.data[leftChildIndex]) {
      largeIndex = rightChildIndex;
    }
    // 3. 较大的值和 index 位置进行比较
    if (this.data[index] >= this.data[largeIndex]) {
      break;
    }
    // 4. 交换位置
    this.swap(index, largeIndex);
    index = largeIndex;
  }
}

extract(): T | undefined {
  // 1. 判断元素的个数为 0 或者 1 的情况
  if (this.length === 0) return undefined;
  if (this.length === 1) {
    this.length--;
    return this.data.pop()!;
  }

  // 2. 提取并且需要返回的最大值
  const topValue = this.data[0];
  this.data[0] = this.data.pop()!;
  this.length--;

  // 3. 维护最大堆的特性：下滤操作
  this.heapify_down(0);

  return topValue;
}

在上面的代码中定义了一个私有方法 heapify_down，这个方法是用来维护最大堆的特性的（下滤操作）

4.4 添加 buildHeap 方法 v4 版

buildHeap 方法用于原地建堆，即指在建立堆的过程中，不使用额外的内存空间，直接在原有数组还是那个进行操作。

ts
constructor(arr: T[]) {
  this.buildHeap(arr)
}

buildHeap(arr: T[]) {
  this.data = arr;
  this.length = arr.length;

  let start = Math.floor((this.length - 1) / 2);
  for (let i = start; i >= 0; i--) {
    this.heapify_down(i);
  }
}

目录