最小堆js

最小堆（Min Heap）是一種特殊的完全二叉樹，堆頂的元素是整個樹中最小的元素。在JavaScript中，我們可以使用數組來實現最小堆。下面是一個簡單的最小堆實現示例：

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

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

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

  add(element) {
    this.heap.push(element);
    this.bubbleUp(this.heap.length - 1);
  }

  removeMin() {
    if (this.isEmpty()) {
      return null;
    }
    const min = this.heap[0];
    this.heap[0] = this.heap.pop();
    this.sinkDown(0);
    return min;
  }

  bubbleUp(index) {
    while (index > 0) {
      const parentIndex = Math.floor((index - 1) / 2);
      if (this.heap[index] < this.heap[parentIndex]) {
        [this.heap[index], this.heap[parentIndex]] = [
          this.heap[parentIndex],
          this.heap[index],
        ];
        index = parentIndex;
      } else {
        break;
      }
    }
  }

  sinkDown(index) {
    while (true) {
      let childIndex = this.getLeftChildIndex(index);
      if (childIndex >= this.heap.length) {
        break;
      }
      let smallerChildIndex = this.getRightChildIndex(index);
      if (smallerChildIndex < this.heap.length &&
          this.heap[smallerChildIndex] < this.heap[childIndex]) {
        childIndex = smallerChildIndex;
      }
      if (this.heap[index] <= this.heap[childIndex]) {
        break;
      }
      [this.heap[index], this.heap[childIndex]] = [
        this.heap[childIndex],
        this.heap[index],
      ];
      index = childIndex;
    }
  }

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

  getRightChildIndex(index) {
    return 2 * index + 2;
  }
}

const minHeap = new MinHeap();
minHeap.add(10);
minHeap.add(1);
minHeap.add(5);
console.log(minHeap.removeMin()); // 1
console.log(minHeap.removeMin()); // 5
console.log(minHeap.removeMin()); // 10
console.log(minHeap.isEmpty()); // true

在這個實現中，add 方法用於將新元素添加到堆中，並通過 bubbleUp 方法將新元素向上調整到正確的位置。removeMin 方法用於移除堆頂的最小元素，並通過 sinkDown 方法將最後一個元素移動到堆頂，然後進行必要的調整。bubbleUp 和 sinkDown 方法實現了堆的調整過程，確保堆的特性始終保持。

注意，這個實現沒有考慮堆的大小限制，也沒有提供 peek 方法來獲取堆頂元素而不移除它。這些可以根據需要進行擴展。