vue+ts实现最小堆

在Vue和TypeScript中实现最小堆可以通过以下步骤进行：

1. 首先，创建一个名为`MinHeap`的类来表示最小堆。在该类中，我们需要定义一个数组来存储堆的元素。

2. 在`MinHeap`类中，我们需要实现以下方法：
- `insert(value: number)`：将一个新的值插入到堆中。
- `removeMin()`：从堆中删除并返回最小值。
- `getMin()`：返回堆中的最小值。
- `size()`：返回堆的大小。
- `isEmpty()`：检查堆是否为空。

3. 在`MinHeap`类中，我们还需要实现以下辅助方法：
- `swap(index1: number, index2: number)`：交换数组中两个索引位置的元素。
- `getParentIndex(index: number)`：返回给定索引的父节点索引。
- `getLeftChildIndex(index: number)`：返回给定索引的左子节点索引。
- `getRightChildIndex(index: number)`：返回给定索引的右子节点索引。
- `hasParent(index: number)`：检查给定索引是否有父节点。
- `hasLeftChild(index: number)`：检查给定索引是否有左子节点。
- `hasRightChild(index: number)`：检查给定索引是否有右子节点。

4. 在`MinHeap`类中，我们需要实现以下辅助方法来维护堆的性质：
- `heapifyUp()`：将新插入的值上移，以保持堆的性质。
- `heapifyDown()`：将根节点下移，以保持堆的性质。

下面是一个示例的实现：

class MinHeap {
  private heap: number[];

  constructor() {
    this.heap = [];
  }

  insert(value: number) {
    this.heap.push(value);
    this.heapifyUp();
  }

  removeMin(): number | undefined {
    if (this.isEmpty()) return undefined;

    const minValue = this.heap[0];
    const lastValue = this.heap.pop();

    if (this.size() > 0) {
      this.heap[0] = lastValue;
      this.heapifyDown();
    }

    return minValue;
  }

  getMin(): number | undefined {
    return this.isEmpty() ? undefined : this.heap[0];
  }

  size(): number {
    return this.heap.length;
  }

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

  private swap(index1: number, index2: number) {
    [this.heap[index1], this.heap[index2]] = [this.heap[index2], this.heap[index1]];
  }

  private getParentIndex(index: number): number {
    return Math.floor((index - 1) / 2);
  }

  private getLeftChildIndex(index: number): number {
    return index * 2 + 1;
  }

  private getRightChildIndex(index: number): number {
    return index * 2 + 2;
  }

  private hasParent(index: number): boolean {
    return this.getParentIndex(index) >= 0;
  }

  private hasLeftChild(index: number): boolean {
    return this.getLeftChildIndex(index) < this.size();
  }

  private hasRightChild(index: number): boolean {
    return this.getRightChildIndex(index) < this.size();
  }

  private heapifyUp() {
    let index = this.size() - 1;

    while (this.hasParent(index) && this.heap[index] < this.heap[this.getParentIndex(index)]) {
      const parentIndex = this.getParentIndex(index);
      this.swap(index, parentIndex);
      index = parentIndex;
    }
  }

  private heapifyDown() {
    let index = 0;

    while (this.hasLeftChild(index)) {
      let smallerChildIndex = this.getLeftChildIndex(index);

      if (this.hasRightChild(index) && this.heap[this.getRightChildIndex(index)] < this.heap[smallerChildIndex]) {
        smallerChildIndex = this.getRightChildIndex(index);
      }

      if (this.heap[index] < this.heap[smallerChildIndex]) {
        break;
      } else {
        this.swap(index, smallerChildIndex);
      }

      index = smallerChildIndex;
    }
  }
}

使用示例：

const minHeap = new MinHeap();
minHeap.insert(5);
minHeap.insert(3);
minHeap.insert(8);
minHeap.insert(1);

console.log(minHeap.getMin()); // 输出：1

console.log(minHeap.removeMin()); // 输出：1
console.log(minHeap.removeMin()); // 输出：3

console.log(minHeap.getMin()); // 输出：5

console.log(minHeap.size()); // 输出：2
console.log(minHeap.isEmpty()); // 输出：false